Virtual Labs

1. In double hashing, which of the following is a commonly used probe-position formula?

(h_1(k) - i \cdot h_2(k)) \bmod m

Explanation

h_1(k) + h_2(k)

Explanation

(h_1(k) + i \cdot h_2(k)) \bmod m

Explanation

(h_1(k) + h_2(k)) \bmod m

Explanation

2. Which collision-resolution technique generally provides the largest variety of probe sequences because it uses a second hash function?

a: Quadratic probing Explanation

Explanation

b: Linear probing Explanation

Explanation

c: Double hashing Explanation

Explanation

d: Separate chaining Explanation

Explanation

3. What is the main purpose of the second hash function in double hashing?

a: To determine the number of keys stored in the table. Explanation

Explanation

b: To determine the step size between successive probes. Explanation

Explanation

c: To sort the keys in ascending order. Explanation

Explanation

d: To remove the first hash function. Explanation

Explanation

4. In the expression

h(k,i) = (h_1(k) + i \cdot h_2(k)) \bmod m

, what does

i

represent?

a: The number of elements in the hash table. Explanation

Explanation

b: The table capacity. Explanation

Explanation

c: The key value. Explanation

Explanation

d: The probe number. Explanation

Explanation

5. Why should the second hash function in double hashing avoid producing a step size of zero?

a: A zero step would repeatedly probe the same table position. Explanation

Explanation

b: A zero step automatically sorts the table. Explanation

Explanation

c: A zero step doubles the table size. Explanation

Explanation

d: A zero step removes all collisions. Explanation

Explanation

6. What is a major advantage of double hashing over linear probing?

a: It never requires a hash function. Explanation

Explanation

b: It can reduce clustering by generating more varied probe sequences. Explanation

Explanation

c: It stores every collision in a linked list. Explanation

Explanation

d: It guarantees constant-time worst-case search. Explanation

Explanation

7. Suppose

m=11

h_1(k)=4

h_2(k)=3

, and the current probe number is

i=2

. What index is generated by double hashing?

7

Explanation

8

Explanation

10

Explanation

3

Explanation

8. Which condition is commonly desirable for the second hash function when the table size is

m

h_2(k)=0

for every key Explanation

Explanation

h_2(k)

should be relatively compatible with the table size so that probes can cover the table effectively Explanation

Explanation

h_2(k)=h_1(k)

for every key Explanation

Explanation

h_2(k)

must always be larger than

m

Explanation

9. If two different keys have the same

h_1(k)

value but different

h_2(k)

values, what is a likely effect in double hashing?

a: They must always occupy the same slot. Explanation

Explanation

b: They will be rejected automatically. Explanation

Explanation

c: They can follow different probe sequences after the initial collision. Explanation

Explanation

d: The table size becomes zero. Explanation

Explanation

Hash Tables