Engineering Questions with Answers - Multiple Choice Questions

# Hashing Functions Multiple Choice MCQ

1 - Question

Which scheme uses a randomization approach?
a) hashing by division
b) hashing by multiplication
c) universal hashing

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

2 - Question

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
h(k)= lowerbound(km).

3 - Question

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

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

4 - Question

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

`Character string = pt`

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

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 - Question

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: 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 - Question

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

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.

7 - Question

Which scheme provides good performance?
b) universal hashing
c) hashing by division
d) hashing by multiplication

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

8 - Question

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

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.

9 - Question

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

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

10 - Question

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: 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 - Question

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: 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 - Question

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

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 - Question

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

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 - Question

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)

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 - Question

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