In: Computer Science
Create a visualization of a hash table containing at least 10 items using one of the hash table collision techniques covered in this section. Fully describe the image and how the items came to be in their given positions.
<<<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>>>>>>>>
we are going to use hash function h(x)=key mod10
so size of hash table is 10
and for collision we are using linear probing which means if a collision occurs or a hash value already has a key then the key element will be placed in next empty hash value. and hash values table should be handled in a circular list manner meaning if a key collides at end of list then we start looking for key from 1st element of list.
lets say 10 numbers to be inserted are 20,11,19,17,50,21,99,2,33,66
inserting numbers in hash table one by one
key | h(x) | index |
index after (collision if any) |
20 | 0 | 0 | - |
11 | 1 | 1 | - |
19 | 9 | 9 | - |
17 | 7 | 7 | - |
50 | 0 | 0(collision) | 2(as after index 0 2 is empty) |
21 | 1 | 1(collision) | 3(as after index 1 3 is empty) |
99 | 9 | 9(collision) | 4(as after index 9 4 is empty) |
2 | 2 | 2(collision) | 5(as after index 2 5 is empty) |
33 | 3 | 3(collision) | 6(as after index 3 6 is empty) |
66 | 6 | 6(collision) | 8(as after index 6 8 is empty) |
so final hash table with above keys and using linear probing are:
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
key | 20 | 11 | 50 | 21 | 99 | 2 | 33 | 17 | 66 | 99 |
<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>>>>>>>