Double Hashing Multiple choice Questions and Answers (MCQs)
Double hashing is one of the best methods available for open addressing.
Question 1 Explanation:
Double hashing is one of the best methods for open addressing because the permutations produced have many characteristics of randomly chosen permutations.
What is the hash function used in Double Hashing?
(h1(k) - i*h2(k))mod m
h1(k) + h2(k)
(h1(k) + i*h2(k))mod m
(h1(k) + h2(k))mod m
Question 2 Explanation:
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.
On what value does the probe sequence depend on?
Question 3 Explanation:
The probe sequence depends in upon the key k since the initial probe position, the offset or both may vary.
The value of h2(k) can be composite relatively to the hash table size m.
Question 4 Explanation:
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.
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')
Question 5 Explanation:
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).
There are 5 questions to complete.