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.

Q: The searching technique that takes O(1) to find a data is :

The technique is hashing.A hash function computes the position of a key directly from the key itself, so a lookup goes straight to the right slot without comparing against other elements. With a good hash function and a low load factor, search takes constant time, O(1), on average.Linear search takes O(n), binary search on a sorted array O(log n), and a balanced search tree O(log n); none of them finds an item in constant time.

Q: Which hashing technique minimizes primary clustering the most ?

The technique is double hashing.Primary clustering is the tendency of linear probing to build long runs of occupied slots: any key hashing into a run lands at its end and lengthens it. Quadratic probing jumps by 1, 4, 9 and so on, which breaks up primary clusters, but keys with the same home slot still follow the same sequence (secondary clustering). Double hashing takes its step size from a second hash function, so even keys with the same home slot probe different sequences; it removes both kinds of clustering and comes closest to uniform hashing among the open-addressing methods.Linear probing is the method that causes primary clustering. Chaining does not probe the table at all, storing colliding keys in lists, so it is a different approach rather than a probe sequence that reduces clustering.

Q: In a file that uses hash-based organization, overflow chains degrade performance mainly due to which of the following ?

Overflow chains degrade performance mainly through increased seek time.In a hashed file, a record's key leads straight to one bucket, ideally one block read. When a bucket fills up, further records go into overflow blocks chained from it. Finding a record may then mean reading the bucket and following the chain block by block, and overflow blocks are usually stored elsewhere on the disk, so each extra block costs another head movement. As chains grow, a lookup that should take one access takes several.Bucket alignment is not the issue. Hashed files never kept alphabetical order, so nothing is lost there. Rotational latency is incurred with each access too, but the dominant extra cost is the seek to each scattered overflow block.

Q: In a hash table, which of the following is used to resolve collisions ?

Collisions are resolved by Chaining.In separate chaining, each slot of the hash table holds a linked list (chain) of all keys that hash to it, so colliding keys are stored side by side. Open addressing (linear or quadratic probing) is the other main method.Hashing is what causes collisions, not their remedy, and backtracking and sorting are unrelated techniques.

Q: In a hash table with 'n' slots using chaining for collision resolution, what is the average time complexity for search in the worst case ?

In the worst case a search takes O(n) time.With separate chaining each slot holds a linked list of the keys that hash to it. If the hash function sends all n keys to the same slot, one chain holds every key, and a search has to walk that whole list, which is linear time.O(1) is the average case with a good hash function and a bounded load factor, not the worst case. O(log n) applies only if each chain is replaced by a balanced tree. \(O(n^{2})\) is too large, since a search visits each key at most once.

Q: While hashing 5 integer keys namely 5, 12, 23, 32, 104 using the hash function h(key) = key % 10 into a hash table with 10 buckets the number of keys that will collide is

The number of keys that collide is 2.Apply h(key) = key % 10 to each key:Key5122332104Bucket52324Only bucket 2 receives more than one key: 12 and 32 both end in 2. So 2 keys collide. Counting the collision as one event gives 1, the trap; 0 ignores the shared bucket and 3 counts a key that has a bucket to itself.

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

The searching technique that takes O(1) to find a data is :

A.Linear search
B.Binary search
C.Hashing
D.Tree

Exam Year(s)

MH SET - 2018, SET Exam - 2018,

Answer: C

The technique is hashing.

A hash function computes the position of a key directly from the key itself, so a lookup goes straight to the right slot without comparing against other elements. With a good hash function and a low load factor, search takes constant time, O(1), on average.

Linear search takes O(n), binary search on a sorted array O(log n), and a balanced search tree O(log n); none of them finds an item in constant time.

Discuss in Forum

Which hashing technique minimizes primary clustering the most ?

A.Linear probing
B.Quadratic probing
C.Double hashing
D.Chaining

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: C

The technique is double hashing.

Primary clustering is the tendency of linear probing to build long runs of occupied slots: any key hashing into a run lands at its end and lengthens it. Quadratic probing jumps by 1, 4, 9 and so on, which breaks up primary clusters, but keys with the same home slot still follow the same sequence (secondary clustering). Double hashing takes its step size from a second hash function, so even keys with the same home slot probe different sequences; it removes both kinds of clustering and comes closest to uniform hashing among the open-addressing methods.

Linear probing is the method that causes primary clustering. Chaining does not probe the table at all, storing colliding keys in lists, so it is a different approach rather than a probe sequence that reduces clustering.

Discuss in Forum

In a file that uses hash-based organization, overflow chains degrade performance mainly due to which of the following ?

A.Increased seek time
B.Bucket alignment issues
C.Loss of alphabetical ordering
D.Increased rotational latency

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: A

Overflow chains degrade performance mainly through increased seek time.

In a hashed file, a record's key leads straight to one bucket, ideally one block read. When a bucket fills up, further records go into overflow blocks chained from it. Finding a record may then mean reading the bucket and following the chain block by block, and overflow blocks are usually stored elsewhere on the disk, so each extra block costs another head movement. As chains grow, a lookup that should take one access takes several.

Bucket alignment is not the issue. Hashed files never kept alphabetical order, so nothing is lost there. Rotational latency is incurred with each access too, but the dominant extra cost is the seek to each scattered overflow block.

Discuss in Forum

In a hash table, which of the following is used to resolve collisions ?

A.Hashing
B.Chaining
C.Backtracking
D.Sorting

Exam Year(s)

Tripura Public Service Commission - 2025,

Answer: B

Collisions are resolved by Chaining.

In separate chaining, each slot of the hash table holds a linked list (chain) of all keys that hash to it, so colliding keys are stored side by side. Open addressing (linear or quadratic probing) is the other main method.

Hashing is what causes collisions, not their remedy, and backtracking and sorting are unrelated techniques.

Discuss in Forum

In a hash table with 'n' slots using chaining for collision resolution, what is the average time complexity for search in the worst case ?

A.O(1)
B.O(log n)
C.O(n)
D.\(O(n^{2})\)

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: C

In the worst case a search takes O(n) time.

With separate chaining each slot holds a linked list of the keys that hash to it. If the hash function sends all n keys to the same slot, one chain holds every key, and a search has to walk that whole list, which is linear time.

O(1) is the average case with a good hash function and a bounded load factor, not the worst case. O(log n) applies only if each chain is replaced by a balanced tree. \(O(n^{2})\) is too large, since a search visits each key at most once.

Discuss in Forum

While hashing 5 integer keys namely 5, 12, 23, 32, 104 using the hash function h(key) = key % 10 into a hash table with 10 buckets the number of keys that will collide is

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: C

The number of keys that collide is 2.

Apply h(key) = key % 10 to each key:

Key	5	12	23	32	104
Bucket	5	2	3	2	4

Only bucket 2 receives more than one key: 12 and 32 both end in 2. So 2 keys collide. Counting the collision as one event gives 1, the trap; 0 ignores the shared bucket and 3 counts a key that has a bucket to itself.

Discuss in Forum

10.

Given an open address hash table with load factor α \(\lt\) 1, the expected number of probes in a successful search is

A.Atmost \(\frac{1}{\alpha}\ln\left(\frac{1-\alpha}{\alpha}\right)\)
B.Atmost \(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\)
C.Atleast \(\frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\)
D.Atleast \(\frac{1}{\alpha}\ln\left(\frac{\alpha}{1-\alpha}\right)\)

Exam Year(s)

UGC NET - 2013,

Answer: B

For open addressing with load factor alpha less than 1, the expected number of probes in a successful search is at most (1/alpha) ln(1/(1 - alpha)), option (B). This is the bound given in the standard analysis under uniform hashing: an unsuccessful search needs at most 1/(1 - alpha) probes, and a successful search for the (i+1)-th inserted key takes as many probes as that key needed on insertion, averaging to (1/alpha) ln(1/(1 - alpha)). It is an upper bound, so the phrase at least in (C) and (D) is wrong. Option (A) has (1 - alpha)/alpha inside the logarithm, which would be negative for alpha above one half, so it cannot be a count of probes.

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