Hash Table Insertion with Collisions Resolution Strategy
How can we insert the given words into a hash table of size 13?
Insert the following 3-letter words into a hash table of size 13 using a specific hash function and collision resolution strategy.
Answer:
The words are inserted into the hash table using the described hash function and applying a collision resolution strategy known as linear probing. This allows effective insertion of elements, regardless of collisions.
When inserting the words into the hash table of size 13, we follow a hash function that simply adds the positions of each letter in the alphabet. For example, 'cat' would be calculated as 3+1+20 = 34. In case of collisions, a linear probing collision resolution strategy is applied.
The hash table with the given words will initially cause several collisions due to the hash function. However, by using linear probing, we can handle these collisions effectively. The hash function essentially sums up the alphabetic positions of the letters.
The process of inserting the words is as follows:
- bat = 2 + 1 + 20 = 23 % 13 = 10
- cop = 3 + 15 + 16 = 34 % 13 = 8
- sat = 19 + 1 + 20 = 40 % 13 = 1
- tea = 20 + 5 + 1 = 26 % 13 = 0
- sad = 19 + 1 + 4 = 24 % 13 = 11
- log = 12 + 15 + 7 = 34 % 13 = 8 (collision, next free slot is 9)
- eat = 5 + 1 + 20 = 26 % 13 = 0 (collision, next free slot is 2)
- yet = 25 + 5 + 20 = 50 % 13 = 11 (collision, next free slot is 12)
Collision resolution strategies such as linear probing enable successful insertion of elements into a hash table even when collisions occur.