# Hashing

 Question 1
Consider a dynamic hashing approach for 4-bit integer keys:

1. There is a main hash table of size 4.
2. The 2 least significant bits of a key is used to index into the main hash table.
3. Initially, the main hash table entries are empty.
4. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table. entry is organized as a binary tree that grows on demand.
5. First, the 3rd least significant bit is used to divide the keys into left and right subtrees based on the 4th least significant bit.
6. To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the 4th least significant bit.
7. A split is done only if it is needed, i.e., only when there is a collision.

Consider the following state of the hash table.

Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?
 A 5,9,4,13,10,7 B 9,5,10,6,7,1 C 10,9,6,7,5,13 D 9,5,13,6,10,14
GATE CSE 2021 SET-1   Data Structure
Question 1 Explanation:
 Question 2
In linear hashing, if blocking factor bfr, loading factor i and file buckets N are known, the number of records will be
 A r=i+bfr+N B r=i-bfr-N C r=i+bfr-N D r=i*bfr*N
ISRO CSE 2020   Data Structure
Question 2 Explanation:
 Question 3
Consider a double hashing scheme in which the primary hash function is $h_1(k)=k\; mod \; 23$, and the secondary hash function is $h_2(k)=1+(k\; mod \; 19)$. Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k=90 is_____________.
 A 21 B 15 C 13 D 17
GATE CSE 2020   Data Structure
Question 3 Explanation:
 Question 4
A hash table with 10 buckets with one slot pet per bucket is depicted here. The symbols, S1 to S7 are initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is:
$\begin{array}{|c|c|} \hline 0 & S 7 \\ \hline 1 & S 1 \\ \hline 2 & \\ \hline 3 & S 4 \\ \hline 4 & S 2 \\ \hline 5 & \\ \hline 6 & S 5 \\ \hline 7 & \\ \hline 8 & S 6 \\ \hline 9 & S 3 \\ \hline \end{array}$
 A 4 B 5 C 6 D 3
ISRO CSE 2018   Data Structure
Question 4 Explanation:
 Question 5
A Hash Function f defined as f(key)=keymod7. With linear probing while inserting the keys 37,38,72,48,98,11,56 into a table indexed from 0, in which location key 11 will be stored (Count table index 0 as $0^{th}$ location)?
 A 3 B 4 C 5 D 6
ISRO CSE 2016   Data Structure
Question 5 Explanation:
 Question 6
A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols S1 to S7 initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is

 A 4 B 5 C 6 D 3
ISRO CSE 2015   Data Structure
Question 6 Explanation:
 Question 7
Given a hash table T with 25 slots that stores 2000 elements, the load factor $\alpha$ for T is ____________.
 A 2000 B 25 C 80 D 160
GATE CSE 2015 SET-3   Data Structure
Question 7 Explanation:
 Question 8
Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?
 A h(i)= $i^{2}$ mod 10 B h(i)= $i^{3}$ mod 10 C h(i)=(11*$i^{2}$) mod 10 D h(i)=(12*i) mod 10
GATE CSE 2015 SET-2   Data Structure
Question 8 Explanation:
 Question 9
Consider a 13 element hash table for which f(key)=key mod 13 is used with integer keys. Assuming linear probing is used for collision resolution, at which location would the key 103 be inserted, if the keys 661, 182, 24 and 103 are inserted in that order?
 A 0 B 1 C 11 D 12
ISRO CSE 2014   Data Structure
Question 9 Explanation:
 Question 10
Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?
 A (97 x 97 x 97)/$100^{3}$ B (99 x 98 x 97)/$100^{3}$ C (97 x 96 x 95)/$100^{3}$ D (97 x 96 x 95)/(3! x $100^{3}$)
GATE CSE 2014 SET-3   Data Structure
Question 10 Explanation:
There are 10 questions to complete.