Engineering Questions with Answers - Multiple Choice Questions

Home » MCQs » Aeronautical Engineering » Double Hashing Multiple Choice MCQ

# Double Hashing Multiple Choice MCQ

Double hashing is one of the best methods available for open addressing.

a) True

b) False

**
View Answer**

Answer: a

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?

a) (h1(k) – i*h2(k))mod m

b) h1(k) + h2(k)

c) (h1(k) + i*h2(k))mod m

d) (h1(k) + h2(k))mod m

**
View Answer**

Answer: c

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?

a) c1

b) k

c) c2

d) m

**
View Answer**

Answer: b

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.

a) True

b) False

**
View Answer**

Answer: b

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?

a)

h1(k) = m mod k

h2(k) = 1+ (m’ mod k)

b)

h1(k) = 1 + (m mod k)

h2(k) = m’ mod k

c)

h1(k) = 1+ (k mod m)

h2(k) = k mod m

d)

h1(k) = k mod m

h2(k) = 1+ (k mod m’)

**
View Answer**

Answer: d

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

What is the running time of double hashing?

a) Theta(m)

b) Theta(m^{2})

c) Theta(m log k)

d) Theta(m^{3})

**
View Answer**

Answer: a

Explanation: The running time of double hashing is Theta(m) since each possible (h1(k), h2(k)) pair yields a distinct probe sequence. Hence the performance of double hashing is better.

Which technique has the greatest number of probe sequences?

a) Linear probing

b) Quadratic probing

c) Double hashing

d) Closed hashing

**
View Answer**

Answer: c

Explanation: Double hashing has the greatest number of probe sequences thereby efficiently resolves hash collision problems.

At what position the number 72 gets inserted in the following table?

Index | Key |

0 | 22 |

1 | 34 |

2 | |

3 | |

4 | |

5 | 56 |

6 | |

7 | 18 |

8 | 41 |

9 | |

10 |

a) 3

b) 10

c) 4

d) 6

**
View Answer**

Answer: d

Explanation: The number 72 must be inserted at index 6.

H(k)=k mod m

H(72)= 72 mod 11

H(72)= 6.

Where does the number 14 get inserted in the following table?

Index | Key |

0 | |

1 | 79 |

2 | |

3 | |

4 | 69 |

5 | 98 |

6 | |

7 | 72 |

8 | |

9 | |

10 | |

11 | 50 |

12 |

a) 2

b) 9

c) 4

d) 8

**
View Answer**

Answer: b

Explanation: Here the hash table is of size 13 with h1(k) = k mod 13 and h2(k) = 1 + k mod 11. Since 14 = 1 (mod 13) and 14 = 3 (mod 11), the key 14 is inserted into empty slot 9.

What is the value of m’ if the value of m is 19?

a) 11

b) 18

c) 17

d) 15

**
View Answer**

Answer: c

Explanation: The value of m’ is chosen as a prime number slightly less than the value of m. Here the value of m is 19, hence the value of m’ can be chosen as 17.