How To Think Of... A Hash Table (part 1)
The hash table seems to be the dominator of data structures as it is being used to solve a variety of CompSci problems such as caching. On a day to day basis we can use it when there is a need to make a choice or to operate on a Set (though hidden). Now, rarely there is a need to implement a hash table from scratch but having a deep understanding of how a hash table works can greatly help us make the most out of it when the time comes.
The basic idea is that you have an array to store values. Given that an array has an index that you can use to store and retrieve a value, it all works.
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
What happens though if you want to use your own key that you can query on? So you have a hashtable of size 3 and you want to put the value of 0 under the key 0.
Now given that the underlying structure is an array, the hashtable needs to figure out which index to use in the array to put the value in. Since the array is of size 3 the possible indexes are 0 to 2.
[0, 1, 2] |---3---|
A simple way to get a number within that range is to mod the key with the length of the hashtable. So in this case
0 % 3 = 0 // key % length = index
So the hashtable uses index 0 to store the value.
The next time you ask for the value stored under the key 0
the hashtable calculates the index again and gives you the value stored
It all works great until you have a key which gives you the same index.
That’s when you have a collision which you need to deal with.