# Hashing

 Question 1
An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let $k$ be the number of keys, $m$ be the number of slots in the hash table, and $k \gt m$.
Which one of the following is the best hashing strategy to counteract the adversary?
 A Division method, i.e., use the hash function $h(k) = k\; mod \; m$ B Multiplication method, i.e., use the hash function $h(k) = \left \lfloor m(kA -\left \lfloor kA \right \rfloor ) \right \rfloor$, where $A$ is a carefully chosen constant. C Universal hashing method. D If $k$ is a prime number, use Division method. Otherwise, use Multiplication method
GATE CSE 2023   Data Structure
Question 1 Explanation:
 Question 2
Suppose we are given $n$ keys, $m$ hash table slots, and two simple uniform hash functions $h_1$ and $h_2$. Further suppose our hashing scheme uses $h_1$ for the odd keys and $h_2$ for the even keys. What is the expected number of keys in a slot?
 A $\frac{m}{n}$ B $\frac{n}{m}$ C $\frac{2n}{m}$ D $\frac{n}{2m}$
GATE CSE 2022   Data Structure
Question 2 Explanation:

 Question 3
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.
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 3 Explanation:
 Question 4
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 4 Explanation:
 Question 5
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 5 Explanation:

There are 5 questions to complete.

### 3 thoughts on “Hashing”

1. Ques no 1 point 5 please remove the last line ,it is changing the meaning of the question.