Question

Consider a hash table of size 10 with indices \( \{0, 1, \dots, 9\} \), with the hash function \[ h(x) = 3x \, (\text{mod} \, 10), \] where linear probing is used to handle collisions. The hash table is initially empty and then the following sequence of keys is inserted into the hash table: 1, 4, 5, 6, 14, 15. The indices where the keys 14 and 15 are stored are, respectively:

• A. 2 and 5
• B. 2 and 6
• C. 4 and 5
• D. 4 and 6

Hint:

When using linear probing for collision resolution, if a slot is occupied, check the next slot in a circular manner (wrap around to the beginning of the table if needed) until you find an empty slot.

Answer 1

The Correct Option is D

We are given a hash table with the hash function \( h(x) = 3x \, (\text{mod} \, 10) \), and we are inserting the keys 1, 4, 5, 6, 14, and 15 into the hash table using linear probing.
Let's compute the hash values and insert the keys one by one:

For key 1:
\[ h(1) = 3 \times 1 \, (\text{mod} \, 10) = 3. \] So, key 1 is inserted at index 3.

For key 4:
\[ h(4) = 3 \times 4 \, (\text{mod} \, 10) = 12 \, (\text{mod} \, 10) = 2. \] So, key 4 is inserted at index 2.

For key 5:
\[ h(5) = 3 \times 5 \, (\text{mod} \, 10) = 15 \, (\text{mod} \, 10) = 5. \] So, key 5 is inserted at index 5.

For key 6:
\[ h(6) = 3 \times 6 \, (\text{mod} \, 10) = 18 \, (\text{mod} \, 10) = 8. \] So, key 6 is inserted at index 8.

For key 14:
\[ h(14) = 3 \times 14 \, (\text{mod} \, 10) = 42 \, (\text{mod} \, 10) = 2. \] Index 2 is already occupied (by key 4), so we use linear probing. We check index 3, which is occupied (by key 1). Next, we check index 4, which is empty, so key 14 is inserted at index 4.

For key 15:
\[ h(15) = 3 \times 15 \, (\text{mod} \, 10) = 45 \, (\text{mod} \, 10) = 5. \] Index 5 is already occupied (by key 5), so we use linear probing. We check index 6, which is empty, so key 15 is inserted at index 6.

Thus, the keys 14 and 15 are stored at indices 4 and 6, respectively.