Hashing Functions Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Hashing Functions”.

1. Which scheme uses a randomization approach?
a) hashing by division
b) hashing by multiplication
c) universal hashing
d) open addressing
View Answer

Answer: c
Explanation: Universal hashing scheme uses a randomization approach whereas hashing by division and hashing by multiplication are heuristic in nature.

2. Which hash function satisfies the condition of simple uniform hashing?
a) h(k) = lowerbound(km)
b) h(k)= upperbound(mk)
c) h(k)= lowerbound(k)
d) h(k)= upperbound(k)
View Answer

Answer: a
Explanation: If the keys are known to be random real numbers k independently and uniformly distributed in the range 0<=k<=1, the hash function which satisfies the condition of simple uniform hashing is
h(k)= lowerbound(km).

3. A good hash approach is to derive the hash value that is expected to be dependent of any patterns that might exist in the data.
a) True
b) False
View Answer

Answer: b
Explanation: A hash value is expected to be unrelated or independent of any patterns in the distribution of keys.
advertisement
advertisement

4. Interpret the given character string as an integer expressed in suitable radix notation.

Character string = pt

a) 14963
b) 14392
c) 12784
d) 14452
View Answer

Answer: d
Explanation: The given character string can be interpreted as (112,116) (Ascii values) then expressed as a radix-128 integer, hence the value is 112*128 + 116 = 14452.

5. What is the hash function used in the division method?
a) h(k) = k/m
b) h(k) = k mod m
c) h(k) = m/k
d) h(k) = m mod k
View Answer

Answer: b
Explanation: In division method for creating hash functions, k keys are mapped into one of m slots by taking the reminder of k divided by m.

6. What can be the value of m in the division method?
a) Any prime number
b) Any even number
c) 2p – 1
d) 2p
View Answer

Answer: a
Explanation: A prime number not too close to an exact power of 2 is often a good choice for m since it reduces the number of collisions which are likely to occur.
advertisement

7. Which scheme provides good performance?
a) open addressing
b) universal hashing
c) hashing by division
d) hashing by multiplication
View Answer

Answer: b
Explanation: Universal hashing scheme provides better performance than other schemes because it uses a unique randomisation approach.

8. Using division method, in a given hash table of size 157, the key of value 172 be placed at position ____
a) 19
b) 72
c) 15
d) 17
View Answer

Answer: c
Explanation: The key 172 can be placed at position 15 by using the formula
H(k) = k mod m
H(k) = 172 mod 157
H(k) = 15.
advertisement

9. How many steps are involved in creating a hash function using a multiplication method?
a) 1
b) 4
c) 3
d) 2
View Answer

Answer: d
Explanation: In multiplication method 2 steps are involved. First multiplying the key value by a constant. Then multiplying this value by m.

10. What is the hash function used in multiplication method?
a) h(k) = floor( m(kA mod 1))
b) h(k) = ceil( m(kA mod 1))
c) h(k) = floor(kA mod m)
d) h(k) = ceil( kA mod m)
View Answer

Answer: a
Explanation: The hash function can be computed by multiplying m with the fractional part of kA (kA mod 1) and then computing the floor value of the result.

11. What is the advantage of the multiplication method?
a) only 2 steps are involved
b) using constant
c) value of m not critical
d) simple multiplication
View Answer

Answer: c
Explanation: The value of m can be simply in powers of 2 since we can easily implement the function in most computers. m=2p where p is an integer.

12. What is the table size when the value of p is 7 in multiplication method of creating hash functions?
a) 14
b) 128
c) 49
d) 127
View Answer

Answer: b
Explanation: In multiplication method of creating hash functions the table size can be taken in integral powers of 2.
m = 2p
m= 27
m = 128.

13. What is the value of h(k) for the key 123456?
Given: p=14, s=2654435769, w=32
a) 123
b) 456
c) 70
d) 67
View Answer

Answer: d
Explanation: A = s/2w
A = 2654435769/ 232
k.A = 123456 * (2654435769/ 232)
= (76300 * 232) + 17612864
Hence r1= 76300; r0=17612864
Since w=14 the 14 most significant bits of r0 yield the value of h(k) as 67.

14. What is the average retrieval time when n keys hash to the same slot?
a) Theta(n)
b) Theta(n2)
c) Theta(nlog n)
d) Big-Oh(n2)
View Answer

Answer: a
Explanation: The average retrieval time when n keys hash to the same slot is given by Theta(n) as the collision occurs in the hash table.

15. Collisions can be reduced by choosing a hash function randomly in a way that is independent of the keys that are actually to be stored.
a) True
b) False
View Answer

Answer: a
Explanation: Because of randomization, the algorithm can behave differently on each execution, providing good average case performance for any input.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.