Hashing
Question 1 |
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?
h(i) = i2 mod 10 | |
h(i) = i3 mod 10 | |
h(i) = (11 *i2) mod 10 | |
h(i) = (12 * i) mod 10 |
Question 2 |
Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is ___________.
80 | |
70 | |
60 | |
50 |
Question 3 |
Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are
3, 0, and 1 | |
3, 3, and 3 | |
4, 0, and 1 | |
3, 0, and 2 |
h(k) = k mod 9
Collisions are resolved using chaining.
Keys: 5, 28, 19, 15, 20, 33, 12, 17, 10.

5%9 – 5
28%9 – 1
19%9 – 1
15%9 – 6
20%9 – 2
33%9 – 6
12%9 – 3
17%9 – 8
10%9 – 1
Maximum chain length is 3
Minimum chain length is 0
Average chain length = 0+3+1+1+0+1+2+0+1/ 9 = 1
Question 4 |
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?
(97×97×97)/1003 | |
(99×98×97)/1003 | |
(97×96×95)/1003 | |
(97×96×95)/(3!×1003) |
They are picked with equal probability of Hash function since it is uniform hashing.
So to avoid the first 3 slots to be unfilled
= 97/100*97/100*97/100 =((97*97*97))⁄1003
Question 5 |
A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.

How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?
46, 42, 34, 52, 23, 33 | |
34, 42, 23, 52, 33, 46
| |
46, 34, 42, 23, 52, 33 | |
42, 46, 33, 23, 34, 52
|
After inserting 6 values, the table looks like

The possible order in which the keys are inserted are:
34, 42, 23, 46 are at their respective slots 4, 2, 3, 6.
52, 33 are at different positions.
― 52 has come after 42, 23, 34 because, it has the collision with 42, because of linear probing, it should have occupy the next empty slot. So 52 is after 42, 23, 34.
― 33 is after 46, because it has the clash with 23. So it got placed in next empty slot 7, which means 2, 3, 4, 5, 6 are filled.
42, 23, 34 may occur in any order but before 52 & 46 may come anywhere but before 33.

So option (C)

Question 6 |
A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.

How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?
10 | |
20 | |
30 | |
40 |
― 33 must be inserted at last (only one possibility)
― 46 can be inserted in any of the 5 places remaining. So 5 ways.
― 52 must be inserted only after inserting 42, 23, 34. So only one choice for 52.
〈42,23,34〉 can be sequenced in 3! ways.
Hence, 5×3! = 30 ways
Question 7 |
The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?
![]() | |
![]() | |
![]() | |
![]() |
They are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k)=k mod 10 & linear probing is used.

12 % 10 = 2
18 % 10 = 8
13 % 10 = 3
2 % 10 = 2 (Index 4 is empty)
3 % 10 = 3 (Index 5 is empty)
23 % 10 = 3 (Index 6 is empty)
5 % 10 = 5 (Index 7 is empty)
15 % 10 = 5 (Index 9 is empty)
Hence Option C is correct.
A & B doesn’t include all the keys & option D is similar to chaining. So, will go with C.
Question 8 |
Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table.
8, _, _, _, _, _, 10 | |
1, 8, 10, _, _, _, 3 | |
1, _, _, _, _, _,3 | |
1, 10, 8, _, _, _, 3 |
Starting index is zero i.e.,

⇾ Given hash function is = (3x+4) mod 3
⇾ Given sequence is = 1, 3, 8, 10
where x = 1 ⟹ (3(1)+4)mod 3 = 0
1 will occupy index 0.
where x = 3 ⟹ (3(3)+4) mod 7 = 6
3 will occupy index 6.
where x = 8 ⟹ (3(8)+4) mod 7 = 0
Index ‘0’ is already occupied then put value(8) at next space (1).
where x = 10 ⟹ (3(10)+4) mod 7 = 6
Index ‘6’ is already occupied then put value(10) at next space (2).
The resultant sequence is (1, 8, 10, __ , __ , __ , 3).
Question 9 |
Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?
-
i) 9679, 1989, 4199 hash to the same value
ii) 1471, 6171 hash to the same value
iii) All elements hash to the same value
iv) Each element hashes to a different value
i only | |
ii only | |
i and ii only | |
iii or iv |
Hash function = x mod 10
Hash values = (2, 4, 1, 9, 9, 1, 3, 9)
9679, 1989, 4199 have same hash values
&
1471, 6171 have same hash values.
Question 10 |
An advantage of chained hash table (external hashing) over the open addressing scheme is
Worst case complexity of search operations is less? | |
Space used is less | |
Deletion is easier | |
None of the above |
Question 11 |
Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23, and the secondary hash function is h2(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 _______.
13 |
• K=90
• h1(k) = k mod 23 = 90 mod 23 = 21
• In case of collision, we need to use secondary hash function.
• h2(k) = 1 + (k mod19) = 1 + 90mod19 = 1+14 = 15
• Now (21+15) mod 23 = 36 mod 23 = 13
• So the address is 13.
Question 12 |
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

4 | |
5 | |
6 | |
3 |
→ Worst case of finding a number is equal to maximum size of cluster + 1(after searching all the cluster it enters into empty cluster)
→ Maximum no. of comparisons = 4 + 1 = 5
Question 13 |
Consider a hash table of size 11 that uses open addressing with linear probing. Let h(k) = k mod 11 be the hash function used. A sequence of records with keys
43 36 92 87 11 4 71 13 14is inserted into an initially empty hash table, the bins of which are indexed from zero to ten. What is the index of the bin into which the last record is inserted?
2 | |
4 | |
6 | |
7 |

Hence, correct option is (D).
Question 14 |

4 | |
5 | |
6 | |
3 |
→ Worst case of finding a number is equal to maximum size of cluster + 1(after searching all the cluster it enters into empty cluster)
→ Maximum number of comparisons = 4 + 1 = 5
Question 15 |
3 | |
4 | |
5 | |
6 |
Hash function = f(key) = key mod 7

Question 16 |
0 | |
1 | |
11 | |
12 |
661 mod 13 = 11
182 mod 13 = 0
24 mod 13 = 11, already filled, so after linear probing it will get index 12
103 mod 13 = 12, already filled, so after linear probing it will get index 1
Question 17 |
A hash function h defined h(key) = key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18 ?
3 | |
4 | |
5 | |
6 |
h(44) = 44 mod 7 ⇒ 2
h(45) = 45 mod 7 ⇒ 3
h(79) = 79 mod 7 ⇒ 2 (collision occurred)
h(79) = (79+1) mod 7 ⇒ 3 (collision occurred)
h(79) = (79+2) mod 7 ⇒ 4
h(55) = 55 mod 7 ⇒ 6
h(91) = 91 mod 7 ⇒ 0
h(18) = 18 mod 7 ⇒ 4 (collision occurred)
h(79) = (18+1) mod 7 ⇒ 5
h(63) = 63 mod 7 ⇒ 0 (collision occurred)
h(63) = (63+1) mod 7 ⇒ 1
Now the array contain keys 44, 45, 79, 55, 91, 18, 63 at locations.

Question 18 |
Consider a hash table of size seven, with starting index zero, and a hash function (7x+3) mod 4. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing ?
Here “__” denotes an empty location in the table.
3, 10, 1, 8, ___ , ___, ___.
| |
1, 3, 8, 10, ___, ___, ___.
| |
1, ___, 3, ___, 8, ___, 10
| |
3, 10, ___, ___, 8, ___, ___. |
h(3) = ((7*3)+3) mod 4 = 0
h(8) = ((7*8)+3) mod 4 = 3
h(10) = ((7*10)+3) mod 4 = 1

Question 19 |
is far less than one | |
equals one | |
is far greater than one | |
none of these |
Load factor= n / k
where
● n is the number of entries occupied in the hash table.
● k is the number of buckets.
As the load factor grows larger, the hash table becomes slower, and it may even fail to work (depending on the method used)
The load factor is the number of keys stored in the hash table divided by the capacity. The size should be chosen so that the load factor is less than 1
Question 20 |
6 | |
5 | |
4 | |
3 | |
None of the above |
Question 21 |
3 | |
4 | |
5 | |
6 |
37%7=2
38%7=3
72%7=2. Here, collision happened because already index 2 is already filled by 37.
According to linear probing, increment index value by 1.
2+1=3 but index 3 also filled with 38 element. So, again increment by 1.
72%7=2( getting index position in hash table 4 )
48%7=6
98%7=0
11%7=4. Here, collision happened because already index 4 is already filled by 72.
According to linear probing, increment index value by 1.
11%7=4 (getting index position in hash table 5 )
56%7=0Here, collision happened because already index 0 is already filled by 98.
According to linear probing, increment index value by 1.
56%7=0 (getting index position in hash table 1 )
Question 22 |
0.45 | |
0.5 | |
0.3 | |
0.37(approximately) |
So, 1- (100*99*98*97*96*95*94*93*92*91)/100 10 ⇒ 0.37(approximately)
Question 23 |

4 | |
5 | |
6 | |
3 |
→ Worst case of finding a number is equal to maximum size of cluster + 1(after searching all the cluster it enters into empty cluster)
→ Maximum no. of comparisons = 4+1
= 5
Question 24 |
Is far less than one | |
Equals one | |
Is far greater than one | |
None of the above |
Question 25 |
1 | |
1/n | |
1/m | |
n/m |
Question 26 |
h (k, i) = (h 1 (k) + h 2 (k) + i) mod m | |
h (k, i) = (h 1 (k) + h 2 (k) - i) mod m | |
h (k, i) = (h 1 (k) + i h 2 (k)) mod m | |
h (k, i) = (h 1 (k) - i h 2 (k)) mod m |
h 1 → hash function
h 2 → Step function
First try h(k,0) = h 1 (k), if it is occupied, try h(k,1) etc..,
Advantage: less clusters, uses Θ(m*m) permutations of index addressing sequences.
Question 27 |
2 | |
3 | |
9 | |
97 |
-- Hash(y)=X mod 100
-- Key=4594
-- First 3 locations are already occupied.
-- Next cell=?
Step-1: Quadratic Probing function is h(k,i) = (h'(k) +c 1 i+c 2 i 2 )mod m 0≤ i ≤ m-1
where c1 and c2 constants ≠0
Step-2: First pass: 4594 % 100
= 94
Sep-3: Second pass: (4594 + 1 2 ) % 100
= (94 + 1) % 100
= 95
Step-3: Third pass: (4594 + 2 2 ) % 100
= (94 + 4) %100
= 98
Step-4: Fourth pass: (4594 + 1 2 ) % 100
= (94 + 9) %100
= 103 % 100
= 3
Question 28 |
Hash addressing | |
Chaining | |
Both (A) and (B) | |
Indexing |
→ Two keys mapping to the same location in the hash table is called “Collision”.
Collision Resolving techniques
1. Separate chaining
2. Open addressing
i. Linear Probing
ii. Quadratic Probing
iii. Double hashing
Question 29 |
3 | |
4 | |
5 | |
6 |
Hash function = f(key) = key mod 7

Question 30 |
Hash addressing | |
Chaining | |
Indexing | |
None of these |
→ Two keys mapping to the same location in the hash table is called “Collision”.
Collision Resolving techniques
1. Separate chaining
2. Open addressing
i. Linear Probing
ii. Quadratic Probing
iii. Double hashing
Question 31 |
worst-case, average | |
worst-case, worst-case | |
average, worst-case | |
best, average |
Question 32 |
3 | |
4 | |
5 | |
6 |
h(44)=44 mod 7 ⇒ 2
h(45)=45 mod 7 ⇒ 3
h(79)=79 mod 7 ⇒ 2 (collision occurred)
h(79)=(79+1) mod 7 ⇒ 3 (collision occurred)
h(79)=(79+2) mod 7 ⇒ 4
h(55)=55 mod 7 ⇒ 6
h(91)=91 mod 7 ⇒ 0
h(18)=18 mod 7 ⇒ 4 (collision occurred)
h(79)=(18+1) mod 7 ⇒ 5
h(63)=63 mod 7 ⇒ 0 (collision occurred)
h(63)=(63+1) mod 7 ⇒ 1
Now the array contain keys 44, 45, 79, 55, 91, 18, 63 at locations

Question 33 |
1 | |
2 | |
3 | |
4 |

Question 34 |
3, 10, 1, 8,___ ,___,___. | |
1, 3, 8, 10,___,___,___. | |
1,___,3,___, 8,___,10 | |
3,10,___,___, 8,___,___. |
h(3)= ((7*3)+3) mod 4 = 0
h(8)= ((7*8)+3) mod 4 = 3
h(10)= ((7*10)+3) mod 4 = 1

Question 35 |
46 | |
47 | |
41 | |
43 |
-- size m=10000
-- hash function h(k) = ⌊m(kA mod 1)'⌋
-- A=(√5 – 1)/2
-- key k=123456 location =?
Step-1: Find out h(123456) = ⌊(10000 * (123456 * (√5 − 1) / 2) mod 1)⌋
= ⌊(10000 * (76300.004115 mod 1)⌋
= ⌊(10000 * (.004115))⌋
= ⌊41.15⌋
= 41
Question 36 |
At most (1/α) ln ((1–α)/α) | |
At most (1/α) ln (1/(1–α)) | |
At least (1/α) ln (1/(1– α)) | |
At least (1/α) ln (α/(1– α)) |
→ Given an open-address hash table with load factor α = n/m < 1, the expected number of probes in an unsuccessful search is at most 1/(1 − α), assuming uniform hashing.
→ Given an open-address hash table with load factor α = n/m < 1, the expected number of probes in a successful search is at most (1/α) ln (1/(1 − α)), assuming uniform hashing and assuming that each key in the table is equally likely to be searched for.
Question 37 |
Secondary clustering | |
Primary clustering | |
Both (A) and (B) | |
None of these |
Example: Linear probing
→ Secondary clustering is less severe, two records do only have the same collision chain if their initial position is the same.
Example: Quadratic probing
Question 38 |
100 | |
200 | |
10000 | |
There is no upper limit |
1. They given chained hash. It is like linked list.
2. Maximum number of entries that can be placed in the table.
In chained hash, we adding new element when collisions are happened.
Question 39 |
3 | |
4 | |
5 | |
6 |
Hash function = f(key) = key mod 7

Question 40 |
46 | |
41 | |
43 | |
48 |
-- Hash table size(m)=10000
-- Hash function(h(K))= floor (m(KA mod1))
-- A=(√(5)-1)/2
-- key(K)=123456
-- location=?
Step-1: Hash function(h(K))= floor (m(KA mod1))
h(123456) = floor(10000 * (123456 * (√5 − 1) / 2) mod 1)
= floor(10000 * (76300.004115 mod 1)
= floor(10000 * (.004115))
= floor(41.15)
= 41
Question 41 |
h(k,i)=(h 1 (k)+ih 2 (k)) mod m
Where h 1 (k)=k mod m
h 2 (k)=1+(k mod n)
Where n=m-1and m=701
for k=123456, what is the difference between first and second probes in terms of slots?
255 | |
256 | |
257 | |
258 |
where h1(k)=k mod m
h2(k)=1+k mod n
where n=m-1 and m=701. For k=123456
h1(k)=123456 mod 701
h1(k)=80
h2(k)=1+(123456 mod 700)
h2(k)=1+256=257
1st probe: i=1
h(k,i)=h1(k)+ih2(k)
h(k,1)=h1(k)+ih2(k)
h(k,1)=80+257=337
h(k,1)=337
2nd probe: i=2
h(k,2)=80+2257
h(k,2)=80+514
h(k,2)=594
∴ Difference h(k,2)-h(k,1)
594-337
257
Question 42 |
77 | |
82 | |
88 | |
89 |
= floor(100(0.88204))
= floor(88.204)
= 88
Question 43 |
cr=l+bfr + N | |
r= l-bfr - N | |
r=l+bfr - N | |
r=l*bfr*N |
Question 44 |
In hashing, collision resolution is carried out by close addressing. Which of the following is close addressing technique-
I. Bucket (for contiguous storage)
II. Chains (for linked storage)
Only I | |
Only II
| |
I and II
| |
None |
Hence Chains use close addressing whereas bucket uses open addressing.
Question 45 |
In hashing, collision results when ____
An attempt is made to delete a record at full primary bucket | |
An attempt is made to insert a record at full primary bucket
| |
An attempt is made to insert a record anywhere in primary bucket
| |
An attempt is made to insert a record at empty primary bucket
|
Question 46 |
Linear search | |
Binary search | |
Hash coded search | |
Radix search |