Given keys as {17, 49, 21, 46, 50, 80, 57, 81, 11, 71} and their associated valu

Question

Given keys as {17, 49, 21, 46, 50, 80, 57, 81, 11, 71} and their associated values as {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} respectively. Show the contents of the hash table after inserting those key values pairs into an initially empty hash table with size 13 using the following conflict resolution methods discussed in class:

a) Separate chaining. When there is a search miss, insert new key into the first node of the linked list.

b) Linear probing without resizing.

Explanation / Answer

17 % 13 => 4 49 % 13 => 10 21 % 13 => 8 46 % 13 => 7 50 % 13 => 11 80 % 13 => 2 57 % 13 => 5 81 % 13 => 3 11 % 13 => 11 71 % 13 => 6 a) Using chaining: 0 -> 1 -> 2 -> (80, 5) 3 -> (81, 7) 4 -> (17, 0) 5 -> (57, 6) 6 -> (71, 9) 7 -> (46, 3) 8 -> (21, 2) 9 -> 10 -> (49, 1) 11 -> (11, 8) -> (50, 4) 12 -> b) Using Linear probing: 0 -> 1 -> 2 -> (80, 5) 3 -> (81, 7) 4 -> (17, 0) 5 -> (57, 6) 6 -> (71, 9) 7 -> (46, 3) 8 -> (21, 2) 9 -> 10 -> (49, 1) 11 -> (11, 8) 12 -> (50, 4)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.