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’
Note:
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.
