Question

Java Hash table,

What does the separate chaining ST look like for M=3 and the following input key, hash pairs? A,0 F,0 Z,2

Answer 1

In hashing, we associate keys to indexes of our table. This helps in reducing the time complexity for common operations such as insertion, search, deletion to an average of O(1). We use a hash function to map keys to indexes. When two different keys map to the same index, it is known as a collision. Although number of collisions can be reduced, but collisions can never be eliminated completed if the number of entries in the table(N) is greater than the size of table(M). For efficient implementation of operations like  searching, we try reduce the number of collisions. However since collisions cannot be completely eliminated,  to deal with collisions we use various collision resolution techniques.

Separate chaining is a collision resolution technique in which we create separate chains for all entries that map to a particular index. These chains are created using linked lists, we create a separate linked list for each index of our hash table. So say if we two keys A and B map to index 0, then index 0 of out hash table will point to a linked list, which contains two nodes, one for A and one for B.

Now in the above question we have M = 3, two keys A and F map to 0th index and key Z maps to 2nd index. So out hash table will have a linked list  containing two nodes as it's index 0. No node at index 1 and a single node for Z at index 2. The final hash table along with the state of hash table after each insertion is shown by in below image.