Consider a hash table of size seven, with starting index zero, and a hash…
2018
Consider a hash table of size seven, with starting index zero, and a hash function (7x+3) mod 4. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing ? Here “__” denotes an empty location in the table.
- A.
3, 10, 1, 8, __ , __ , __
- B.
1, 3, 8, 10, __ , __ , __
- C.
1, __ , 3, __ , 8, __ , 10
- D.
3, 10, __ , __ , 8, __ , __
Attempted by 218 students.
Show answer & explanation
Correct answer: A
Solution:
Compute the initial index for each key using h(x) = (7x + 3) mod 4. Use linear probing in a table of size 7 (indices 0 through 6).
Insert 1: 7*1 + 3 = 10 ≡ 2 (mod 4). Slot 2 is empty, so place 1 at index 2.
Insert 3: 7*3 + 3 = 24 ≡ 0 (mod 4). Slot 0 is empty, so place 3 at index 0.
Insert 8: 7*8 + 3 = 59 ≡ 3 (mod 4). Slot 3 is empty, so place 8 at index 3.
Insert 10: 7*10 + 3 = 73 ≡ 1 (mod 4). Slot 1 is empty, so place 10 at index 1.
Final table (indices 0 to 6):
Index 0: 3
Index 1: 10
Index 2: 1
Index 3: 8
Index 4: __
Index 5: __
Index 6: __
Therefore the table contents from index 0 to 6 are: 3, 10, 1, 8, __, __, __.
A video solution is available for this question — log in and enroll to watch it.