I am learning hash table by using separate chaining using linked lists and there comes an instance where we have to resize the hash table. But I am not getting why do we need to resize it as it works the same with or without resizing it. I read somewhere that it has to do something with the time complexity of the search, insert and remove options. But how can these be affected with resizing the table. Its a request to please answer in as simple language as possible as I am new to these things and sorry for any english mistakes as this is not my primary language.
What does it really mean by resizing hash table with separate chaining resolution technique?
Viewed 38
1 Answers
In short - smaller hash tables have a higher collision rate which means more effort is needed to ensure correctness.
Consider a simple example of a hash table as an array of lists. If two items map down to the same array position (slot), you add that value to the list at that position. On retrieval, you find the slot, iterate that list, and look for an item with the requested key. The slot of an incoming hash key is calculated by hash key % array length.
Now consider an array with 7 elements as the backing store (hash table sizes are generally prime numbers), and you store 10k items in it. Each slot in the backing array is going to have ~1400 items in it due to the limited storage and a high number of collisions. When you ask for the value with key x, you're going to have to look through those ~1400 items for the correct one to return.
By bumping the array size to 73, each slot now only contains ~130 items - a big reduction in the amount of work, particularly on retrieval.
Related