This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Double Hashing”.
1. What are the values of h1(k) and h2(k) in the hash function?
h1(k) = m mod k h2(k) = 1+ (m’ mod k)
h1(k) = 1 + (m mod k) h2(k) = m’ mod k
h1(k) = 1+ (k mod m) h2(k) = k mod m
h1(k) = k mod m h2(k) = 1+ (k mod m’)
Explanation: k mod m and 1+(k mod m’) are the values h1(k) and h2(k), respectively, where m is a prime number and m’ is chosen slightly less than m. (m’=m-1) m’=m-1 m’=m-1 m
2. What is the running time of double hashing?
C) Theta(m log k)
Explanation: Since each possible (h1(k), h2(k)) pair yields a unique probe series, the running time of double hashing is Theta(m). As a result, double hashing performs better.
3. Which technique has the greatest number of probe sequences?
A) Linear probing
B) Quadratic probing
C) Double hashing
D) Closed hashing
Explanation: Since double hashing has the most probe sequences, it effectively resolves hash collision issues.
4. At what position the number 72 gets inserted in the following table?
Explanation: The number 72 must be inserted at index 6.
H(k)=k mod m
H(72)= 72 mod 11
5. Where does the number 14 get inserted in the following table?
Explanation: 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.
6. What is the value of m’ if the value of m is 19?
Explanation: The value of m’ is chosen to be a prime number that is slightly less than m. Since m is 19 in this case, the value of m’ can be chosen as 17.
7. Double hashing is one of the best methods available for open addressing.
Explanation: Since the permutations generated have many characteristics of randomly chosen permutations, double hashing is one of the best methods for accessible addressing.
8. 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
Explanation: The hash function for double hashing is (h1(k) + i*h2(k))mod m, where h1 and h2 are auxiliary hash functions and m is the hash table size.
9. On what value does the probe sequence depend on?
Explanation: Since the initial probe location, offset, or both which differ, the probe sequence is determined by the main k.
10. The value of h2(k) can be composite relatively to the hash table size m.
Explanation: For the entire hash table to be searched, the value h2(k) must be relatively prime to the hash table size m. It is possible to achieve this by making m powers of 2 and designing h2 to generate an odd number.
When a hash collision occurs, double hashing is a computer programming technique that uses a secondary hash of the key as an offset. It is used in combination with open-addressing in hash tables to overcome hash collisions. On a table displaystyle T T, double hashing with open addressing is a classic data structure. The double hashing technique uses one hash value as an index into the table, then moves forward an interval before the desired value is found, an empty location is reached, or the entire table is searched; however, this interval is determined by a second, separate hash function.