Data structures from scratch- Bot-up series #12[Hash Tables II]
We introduced the concept of ‘Hash table’ because we need a data structure that is suitable for search operations
One thing to remember is that ‘Hash tables’ are refined versions of ‘Arrays’
Why? Arrays are best suited for ‘accessibility’ and ‘search operations’ contains ‘accessibility operation’
So we need to build ‘hash tables’ upon ‘arrays’
See in Hash tables we have ‘keys’ which in turn converted into ‘indices’ whereas in arrays we don’t have this liberty.
We will build a hash table in the array of 10 continuous slots(0–9)
We have 10 names to store and the requirement is easy to search or lookup
For that, we will convert characters into alphabetical positions and add the numbers
Note we have 10 continuous slots(0–9) but we have resulting numbers of more than 9.
So I divide the result by the number of slots and this will give us the remainder.
The remainder can never be more than the number of slots
There is a name to this operation called ‘Modulo operation’
To reiterate, the hash function converts the key to some number
Then index is found by dividing it by array size
When you notice the above table we have remainders for Finch, Jane and Ross, Lisbon.
We have only one slot but two names
When you encounter this type of scenario, it is called ‘Hash Collision’
Hash Collision = Same output(Index) for different input(Key)
There are many ways to avoid this collision
Before that let us identify the stakeholders here.
Hash function, Array size, Index or different data structure in case of collision
1)Hash Function — Try to put functions that avoid collision(Obvious)
2)ArraySize — Try to increase the array size and hence modulo operator range will increase
3)Index — When collision comes, just start looking for the next available empty slot and store the element
4)Different data structures — Have an array of pointers. Pointers points to next location(Yes! Linked list)
5)In fact, we usually implement a mix of all the above to get the best result.
