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) = i^{2} mod 10  
h(i) = i^{3} mod 10  
h(i) = (11 *i^{2}) 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)/100^{3}  
(99×98×97)/100^{3}  
(97×96×95)/100^{3}  
(97×96×95)/(3!×100^{3}) 
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))⁄100^{3}
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 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 _______.
13 
• K=90
• h_{1}(k) = k mod 23 = 90 mod 23 = 21
• In case of collision, we need to use secondary hash function.
• h_{2}(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=?
Step1: Quadratic Probing function is h(k,i) = (h'(k) +c _{1} i+c _{2} i^{ 2} )mod m 0≤ i ≤ m1
where c1 and c2 constants ≠0
Step2: First pass: 4594 % 100
= 94
Sep3: Second pass: (4594 + 1 ^{2} ) % 100
= (94 + 1) % 100
= 95
Step3: Third pass: (4594 + 2 ^{2} ) % 100
= (94 + 4) %100
= 98
Step4: 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 
worstcase, average  
worstcase, worstcase  
average, worstcase  
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 =?
Step1: 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 openaddress 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 openaddress 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=?
Step1: 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=m1and 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=m1 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)
594337
257
Question 42 
77  
82  
88  
89 
= floor(100(0.88204))
= floor(88.204)
= 88
Question 43 
cr=l+bfr + N  
r= lbfr  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 