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.