(25 Points) Insert the keys 8, 4, 11, 20, 15, 17, 10 in order into a hash table
ID: 3607079 • Letter: #
Question
(25 Points) Insert the keys 8, 4, 11, 20, 15, 17, 10 in order into a hash table that uses open addressing with linear probing with an initial size of 6. The hash function is defined as: h(k) -k mod SIZE, where SIZE is the current size of the table (initially, SIZE - 6). Rehashing should be performed as soon as the table is completely full, and will double the size of the table (note that the increased table size here is not required to be a prime number). Show how the table looks like immediately before the rehash, as well as the final result after all insertions.Explanation / Answer
Initial table:
Given keys: 8,4,11,20,15,17,10
Insertion positions: 8-->8%6=2
4-->4%6=4
11%6=5
20%6=2-->inserted at position 3 (Due to linear probing)
15-->15%6=3-->inserted at position 0 (Due to linear probing)
17-->17%6=5-->inserted at position 1(Due to linear probing)
Now, Rehashing occurs as table is full.
Table before Rehashing.
Now table size is doubled, i.e. k=12
Therefore, 8 is inserted at-->8 mod 12 =8
4-->4 mod 12 = 4
11-->11 mod 12 =11
20-->20 mod 11= 9
15-->15 mod 11=4 (value already there, so inserted at position 5)
17-->17 mod 11=6
10-->10 mod 11=10
Final Table:
0 1 2 3 4 5Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.