Question

In a double hashing scheme, \( h_1(k) = k \mod 11 \) and \( h_2(k) = 1 + (k \mod 7) \) are the auxiliary hash functions. The size \( m \) of the hash table is 11. The hash function for the \( i \)-th probe in the open address table is \( [h_1(k) + i \cdot h_2(k)] \mod m \). The following keys are inserted in the given order: 63, 50, 25, 79, 67, 24. The slot at which key 24 gets stored is:

Hint:

In double hashing, ensure that the second hash function helps in reducing clustering by selecting a good step size. Always check if the slot is already occupied and probe further using the given formula.

Answer 1

We are given the following hash functions:
\( h_1(k) = k \mod 11 \)
\( h_2(k) = 1 + (k \mod 7) \)
The size of the hash table is \( m = 11 \). Insertion Process:
1. Insert 63:
- \( h_1(63) = 63 \mod 11 = 8 \)
- \( h_2(63) = 1 + (63 \mod 7) = 1 + 0 = 1 \)
- The slot for 63 is \( 8 \).
2. Insert 50:
- \( h_1(50) = 50 \mod 11 = 6 \)
- \( h_2(50) = 1 + (50 \mod 7) = 1 + 1 = 2 \)
- The slot for 50 is \( 6 \).
3. Insert 25:
- \( h_1(25) = 25 \mod 11 = 3 \)
- \( h_2(25) = 1 + (25 \mod 7) = 1 + 4 = 5 \)
- The slot for 25 is \( 3 \).
4. Insert 79:
- \( h_1(79) = 79 \mod 11 = 2 \)
- \( h_2(79) = 1 + (79 \mod 7) = 1 + 2 = 3 \)
- The slot for 79 is \( 2 \).
5. Insert 67:
- \( h_1(67) = 67 \mod 11 = 1 \)
- \( h_2(67) = 1 + (67 \mod 7) = 1 + 4 = 5 \)
- The slot for 67 is \( 1 \).
6. Insert 24 (We are looking for where key 24 gets stored):
- \( h_1(24) = 24 \mod 11 = 2 \)
- \( h_2(24) = 1 + (24 \mod 7) = 1 + 3 = 4 \)
- The slot for 24 is \( 2 \). However, slot 2 is already occupied (by 79).
- So, we move to the next probe:
- \( h_1(24) + 1 \cdot h_2(24) = 2 + 1 \cdot 4 = 6 \) (Slot 6 is occupied by 50).
- The next probe:
- \( h_1(24) + 2 \cdot h_2(24) = 2 + 2 \cdot 4 = 10 \)
- Slot 10 is empty, so key 24 is inserted in slot 10.
Thus, the key 24 gets stored in slot 10.