Hashing Techniques Questions and Answers

Q: Consider a hash table P[0, 1, ... , 10] that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is h(x) = (x + 7) mod 11.Consider the following sequence of insertions performed on P:1, 13, 22, 15, 11, 24Which of the following positions in the hash table is/are empty after these insertions are performed?

Of the positions listed, only 2 is empty.Insert each key with h(x) = (x + 7) mod 11, probing forward on a collision:1: h = 8, placed at 8.13: h = 20 mod 11 = 9, placed at 9.22: h = 29 mod 11 = 7, placed at 7.15: h = 22 mod 11 = 0, placed at 0.11: h = 18 mod 11 = 7; 7, 8 and 9 are full, placed at 10.24: h = 31 mod 11 = 9; 9, 10 and 0 are full, placed at 1.The occupied slots are 0, 1, 7, 8, 9 and 10, so slots 2 to 6 are empty. Positions 0, 10 and 1 are all filled, 10 and 1 only after probing past earlier keys.

Q: 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?

The expected number of keys in a slot is \(\frac{n}{m}\).Simple uniform hashing means each key lands in any given slot with probability \(\frac{1}{m}\), whichever of the two functions hashes it. Using \(h_{1}\) for odd keys and \(h_{2}\) for even keys does not change that probability, so by linearity of expectation a slot receives\[ n \cdot \frac{1}{m} = \frac{n}{m} \]keys on average. Equivalently, if half the keys are odd, each half contributes \(\frac{n}{2m}\), and the two halves add to \(\frac{n}{m}\). \(\frac{n}{2m}\) counts only one half, \(\frac{2n}{m}\) double-counts, and \(\frac{m}{n}\) is the reciprocal of the load factor.

Q: 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?

The best strategy is the universal hashing method.Any single fixed hash function can be defeated: an adversary who knows it can choose k keys that all hash to the same slot, giving \(\Theta(k)\) time per lookup. Universal hashing chooses the hash function at random, at run time, from a family in which any two distinct keys collide with probability at most 1/m. Since the adversary picks keys without knowing which function was drawn, the expected number of collisions for any key is at most about k/m, whatever keys were chosen.The division method and the multiplication method are both fixed, deterministic functions, so each can be attacked as above. Switching between them on whether k is prime is still deterministic, and the adversary controls the keys anyway.

Consider a hash table P[0, 1, ... , 10] that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is h(x) = (x + 7) mod 11.

Consider the following sequence of insertions performed on P:

1, 13, 22, 15, 11, 24

Which of the following positions in the hash table is/are empty after these insertions are performed?

A.0
B.10
C.2
D.1

Exam Year(s)

GATE CS - 2026,

Answer: C

Of the positions listed, only 2 is empty.

Insert each key with h(x) = (x + 7) mod 11, probing forward on a collision:

1: h = 8, placed at 8.
13: h = 20 mod 11 = 9, placed at 9.
22: h = 29 mod 11 = 7, placed at 7.
15: h = 22 mod 11 = 0, placed at 0.
11: h = 18 mod 11 = 7; 7, 8 and 9 are full, placed at 10.
24: h = 31 mod 11 = 9; 9, 10 and 0 are full, placed at 1.

The occupied slots are 0, 1, 7, 8, 9 and 10, so slots 2 to 6 are empty. Positions 0, 10 and 1 are all filled, 10 and 1 only after probing past earlier keys.

Discuss in Forum

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}\)

Exam Year(s)

GATE CS - 2022,

Answer: B

The expected number of keys in a slot is \(\frac{n}{m}\).

Simple uniform hashing means each key lands in any given slot with probability \(\frac{1}{m}\), whichever of the two functions hashes it. Using \(h_{1}\) for odd keys and \(h_{2}\) for even keys does not change that probability, so by linearity of expectation a slot receives

\[ n \cdot \frac{1}{m} = \frac{n}{m} \]

keys on average. Equivalently, if half the keys are odd, each half contributes \(\frac{n}{2m}\), and the two halves add to \(\frac{n}{m}\). \(\frac{n}{2m}\) counts only one half, \(\frac{2n}{m}\) double-counts, and \(\frac{m}{n}\) is the reciprocal of the load factor.

Discuss in Forum

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) = \lfloor m(kA - \lfloor kA \rfloor) \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.

Exam Year(s)

GATE CS - 2023,

Answer: C

The best strategy is the universal hashing method.

Any single fixed hash function can be defeated: an adversary who knows it can choose k keys that all hash to the same slot, giving \(\Theta(k)\) time per lookup. Universal hashing chooses the hash function at random, at run time, from a family in which any two distinct keys collide with probability at most 1/m. Since the adversary picks keys without knowing which function was drawn, the expected number of collisions for any key is at most about k/m, whatever keys were chosen.

The division method and the multiplication method are both fixed, deterministic functions, so each can be attacked as above. Switching between them on whether k is prime is still deterministic, and the adversary controls the keys anyway.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Hashing Techniques Questions and Answers || Hashing Techniques MCQ Questions and Answers || Hashing Techniques GK Questions and Answers || Hashing Techniques GK MCQ Questions || Hashing Techniques Multiple Choice Questions and Answers || Hashing Techniques GK || GK on Hashing Techniques || Data Structures and Algorithms Questions and Answers || Data Structures and Algorithms MCQ Questions and Answers || Data Structures and Algorithms GK Questions and Answers || GK on Data Structures and Algorithms

Hashing Techniques Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications