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***__*

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 157H(k) = 15.

**2. How many steps are involved in creating a hash function using a multiplication method?**

A) 1

B) 4

C) 3**D) 2**

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?**

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

**6. 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

**7. 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: 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.****A) True**

B) False

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) 2^{p} – 1

D) 2^{p}

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

h(k)= lowerbound(km).

**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.**

A) True**B) False**

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

A) 14963

B) 14392

C) 12784**D) 14452**

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.