This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Hashing Functions”
- Using division method, in a given hash table of size 157, the key of value 172 be placed at position __
Explanation: The key 172 can be placed at position 15 by using the formula H(k) = k mod m H(k) = 172 mod 157H(k) = 15.
2. How many steps are involved in creating a hash function using a multiplication method?
Explanation: There are two steps in the multiplication process. First, a constant is multiplied by the main value. After that, multiply this value by m.
3. 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)
Explanation: By multiplying m by the fractional part of kA (kA mod 1) and then calculating the result’s floor value, the hash function can be computed.
4. 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
Explanation: Since the function can be easily implemented in most computers, the value of m can simply be in powers of two. m=2p (where p is a positive integer)
5. What is the table size when the value of p is 7 in multiplication method of creating hash functions?
Explanation: In multiplication method of creating hash functions the table size can be taken in integral powers of 2.
m = 2p
m = 128
6. What is the value of h(k) for the key 123456?
Given: p=14, s=2654435769, w=32
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
7. What is the average retrieval time when n keys hash to the same slot?
C) Theta(nlog n)
Explanation: Theta(n) is the average retrieval time when n keys hash to the same slot in the hash table when a collision occurs.
8. 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.
Explanation: .The algorithm will behave differently on each execution due to randomization, resulting in good average case results for any input.
9. 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
Explanation: By taking the reminder of k divided by m, k keys are mapped into one of m slots in the division method for generating hash functions.
10. What can be the value of m in the division method?
A) Any prime number
B) Any even number
C) 2p – 1
Explanation: A prime number that is not too close to an exact power of 2 is also a good option for m because it decreases the likelihood of collisions.
11. Which scheme provides good performance?
A) open addressing
B) universal hashing
C) hashing by division
D) hashing by multiplication
Explanation: Since it uses a special randomization technique, the universal hashing scheme outperforms other schemes.
12. Which scheme uses a randomization approach?
A) hashing by division
B) hashing by multiplication
C) universal hashing
D) open addressing
Explanation: A randomization approach is used in the universal hashing scheme, while hashing by division and hashing by multiplication are heuristic in nature.
13. 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)
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
14. 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.
Explanation: A hash value is supposed to be unrelated to or unaffected by key distribution patterns.
15. Interpret the given character string as an integer expressed in suitable radix notation.
Character string = pt
Explanation: The value is 112*128 + 116 = 14452 because the given character string can be interpreted as (112,116) (Ascii values) and then represented as a radix-128 integer.
Any function that can be used to map data of any size to fixed-size values is referred to as a hash function. Hash values, hash codes, digests, or simply hashes are the results of a hash function. The values are usually used to index a hash table, which is a fixed-size table. Hashing or scatter storage addressing is the use of a hash function to index a hash table. Hash functions and hash tables are used in data storage and retrieval applications to access data in a small and nearly constant amount of time per retrieval, requiring just a fraction of the overall storage space needed for the data or records themselves.