GATE2025_CS1_Q65

In a double hashing scheme, h₁(k) = k mod 11 and h₂(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₁(k) + i h₂(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 ______. (Answer in integer)

✅ Final Answer:

The correct answer is 10.

🔹 Short Answer:

To find the slot for key 24, we calculate its hash values: h₁(24) = 24 mod 11 = 2 and h₂(24) = 1 + (24 mod 7) = 1 + 3 = 4. We then probe the hash table. Probe 0: `(2 + 0*4) mod 11 = 2` (collision). Probe 1: `(2 + 1*4) mod 11 = 6` (collision). Probe 2: `(2 + 2*4) mod 11 = 10` (empty). Key 24 is placed in slot 10.

🔸 Long Answer:

This problem requires a step-by-step trace of insertions into a hash table that uses double hashing for collision resolution. Let's trace each insertion in the given order.

Hashing Parameters

• Hash Table Size (m): 11 (slots 0 to 10)
• Primary Hash Function: h₁(k) = k mod 11
• Secondary Hash Function: h₂(k) = 1 + (k mod 7)
• Double Hashing Formula: h(k, i) = (h₁(k) + i * h₂(k)) mod 11

Insertion Trace

We'll track the state of the hash table after each key is inserted. An underscore `_` denotes an empty slot.

Key to Insert	h₁(k)	h₂(k)	Probe Calculation	Final Slot	Hash Table State [0...10]
63	8	1	i=0: (8 + 0*1) mod 11 = 8	8	[_, _, _, _, _, _, _, _, 63, _, _]
50	6	2	i=0: (6 + 0*2) mod 11 = 6	6	[_, _, _, _, _, _, 50, _, 63, _, _]
25	3	5	i=0: (3 + 0*5) mod 11 = 3	3	[_, _, _, 25, _, _, 50, _, 63, _, _]
79	2	5	i=0: (2 + 0*5) mod 11 = 2	2	[_, _, 79, 25, _, _, 50, _, 63, _, _]
67	1	2	i=0: (1 + 0*2) mod 11 = 1	1	[_, 67, 79, 25, _, _, 50, _, 63, _, _]
24	2	4	i=0: (2 + 0*4) mod 11 = 2 (Occupied) i=1: (2 + 1*4) mod 11 = 6 (Occupied) i=2: (2 + 2*4) mod 11 = 10 (Empty)	10	[_, 67, 79, 25, _, _, 50, _, 63, _, 24]

Detailed Calculation for Key 24

1. Calculate Hash Values:

• h₁(24) = 24 mod 11 = 2
• h₂(24) = 1 + (24 mod 7) = 1 + 3 = 4

2. Start Probing (i=0):

h(24, 0) = (2 + 0 * 4) mod 11 = 2

Slot 2 is occupied by key 79. This results in a collision.

3. Probe Again (i=1):

h(24, 1) = (2 + 1 * 4) mod 11 = 6

Slot 6 is occupied by key 50. This is another collision.

4. Probe Again (i=2):

h(24, 2) = (2 + 2 * 4) mod 11 = (2 + 8) mod 11 = 10

Slot 10 is empty. The key 24 is inserted here.

Therefore, the final slot where key 24 is stored is 10.

Bibliography:
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press. (Chapter 11: Hash Tables).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.