Data structures from scratch- Bot-up series #11[Hash Tables]

In the last post, we arrived at a conclusion that both arrays and linked lists are not suitable for search operations

Why? We need to check each and every element till the desired element is found

Also, we learnt the difference between searching and accessing

Accessing — We know the address or position

Searching — We only know the element or value

One thing hidden here is ‘searching’ includes ‘accessing

How? After the desired element is found, we need to access it to show the result or output

So accessing is the basic step in all operations

We know that access is based on knowing the address or position

So if we could find the way to reach position exactly while searching, we can bypass the whole process of checking every element

Let’s do that

See we have two things basically — Memory address and Value

Value is basically what we want to store or search(depends on motive).

The memory address is where it is located.

If we know the memory location, we can access it.

What if there is a converter that maps to a memory location that contains the value?

This converter is like a function that takes in input and gives output.

Wait we know the output which is Memory location but what should be the input?

Is the input connected to value? Yes

Why? Because converter function maps to value’s memory location

There is a fancy name to the input called ‘Keys

So while storing data, we give input as key: value pairs to the mapper function and while retrieving data we give a key that maps to the exact memory location.

This type of structuring the data is called ‘Hash tables’


Keys must be unique but values can be the same

Why? Keys are input and every input must be mapped to the same location every time.

Converter function or hash function always gives output as numbers because memory location is in numbers.

In the next post, we will look into some pros and cons of the hash table in-depth.