Data Structures & Algorithms Multiple Choice Questions on “Double Hashing”.
1. Double hashing is one of the best methods available for open addressing.
a) True
b) False
Answer: a
Clarification: Double hashing is one of the best methods for open addressing because the permutations produced have many characteristics of randomly chosen permutations.
2. What is the hash function used in Double Hashing?
a) (h1(k) – i*h2(k))mod m
b) h1(k) + h2(k)
c) (h1(k) + i*h2(k))mod m
d) (h1(k) + h2(k))mod m
Answer: c
Clarification: Double hashing uses a hash function of the form (h1(k) + i*h2(k))mod m where h1 and h2 are auxiliary hash functions and m is the size of the hash table.
3. On what value does the probe sequence depend on?
a) c1
b) k
c) c2
d) m
Answer: b
Clarification: The probe sequence depends in upon the key k since the initial probe position, the offset or both may vary.
4. The value of h2(k) can be composite relatively to the hash table size m.
a) True
b) False
Answer: b
Clarification: The value h2(k) must be relatively prime to the hash table size m for the entire hash table to be searched. It can be ensured by having m in powers of 2 and designing h2 so that it produces an odd number.
5. What are the values of h1(k) and h2(k) in the hash function?
a)
h1(k) = m mod k
h2(k) = 1+ (m’ mod k)
b)
h1(k) = 1 + (m mod k)
h2(k) = m’ mod k
c)
h1(k) = 1+ (k mod m)
h2(k) = k mod m
d)
h1(k) = k mod m
h2(k) = 1+ (k mod m’)
View Answer
Answer: d
Clarification: The values h1(k) and h2(k) are k mod m and 1+(k mod m’) respectively where m is a prime number and m’ is chosen slightly less than m. (m’=m-1).
6. What is the running time of double hashing?
a) Theta(m)
b) Theta(m2)
c) Theta(m log k)
d) Theta(m3)
View Answer
Answer: a
Clarification: The running time of double hashing is Theta(m) since each possible (h1(k), h2(k)) pair yields a distinct probe sequence. Hence the performance of double hashing is better.
7. Which technique has the greatest number of probe sequences?
a) Linear probing
b) Quadratic probing
c) Double hashing
d) Closed hashing
Answer: c
Clarification: Double hashing has the greatest number of probe sequences thereby efficiently resolves hash collision problems.
8. At what position the number 72 gets inserted in the following table?
| Index | Key |
| 0 | 22 |
| 1 | 34 |
| 2 | |
| 3 | |
| 4 | |
| 5 | 56 |
| 6 | |
| 7 | 18 |
| 8 | 41 |
| 9 | |
| 10 |
a) 3
b) 10
c) 4
d) 6
Answer: d
Clarification: The number 72 must be inserted at index 6.
H(k)=k mod m
H(72)= 72 mod 11
H(72)= 6.
9. Where does the number 14 get inserted in the following table?
| Index | Key |
| 0 | |
| 1 | 79 |
| 2 | |
| 3 | |
| 4 | 69 |
| 5 | 98 |
| 6 | |
| 7 | 72 |
| 8 | |
| 9 | |
| 10 | |
| 11 | 50 |
| 12 |
a) 2
b) 9
c) 4
d) 8
Answer: b
Clarification: Here the hash table is of size 13 with h1(k) = k mod 13 and h2(k) = 1 + k mod 11. Since 14 = 1 (mod 13) and 14 = 3 (mod 11), the key 14 is inserted into empty slot 9.
10. What is the value of m’ if the value of m is 19?
a) 11
b) 18
c) 17
d) 15
Answer: c
Clarification: The value of m’ is chosen as a prime number slightly less than the value of m. Here the value of m is 19, hence the value of m’ can be chosen as 17.