This is a # and this is a #Tag. Hash table and Hashing has yet lot to do. So, we have yet lot to understand. A first-class amount of background information will make the study more than interesting. Let’s settle down the dust and chew the fat!
Say you have an inclination of writing a daily journal (not on Facebook), every day one page, as already dated in the diary. The diary has the tag to identify the month and days are easily accessible. On a lonely day with no work, if you feel like reading something which you scribbled on May 31 when you had something special with your crush, you can easily access the page of necessitate and read it. You precisely know where exactly to go. Days and years pass by and diaries pile up. One fine day you decide to make it electronic and transfer everything to your computer. Every page is a separate document. Each page is saved somewhere on the disk. Thinking like a computer engineer it’s our duty to make sure to provide a mechanism where for each date, when the page has to be searched, it’s quickly accessible.
Let us say there is some magic black box which takes the date as input and gives out the location on disk where that page can be fetched and loaded into memory.
Well, yes, we have dig up to the point. That is the hash function sitting inside the magic black box and converting the required. Let us pre-empt all the necessary questions.
It is a search?
Yes, off course and indeed. But we need a mechanism to make the search faster. We don’t want to search page by page and then give out the result. We want a faster access.
Who designs this magic sitting inside the black box?
We will. We have to. That is the challenging task. Quite difficult but with some noise we can easily have a good enough solution.
What exactly is this Hash?
Function and an array! Funny, but that’s it. One function which computes based on the supplied input which we call it as key and an array to store all the values associated with keys. Yes, you got it right, a [key-value] pair.
Let us have a closer look inside the black box!
The date is the key which is given as input to the hash function. Hash function computes using the key where the result is an array index. There is an array, which is a hash table, housing the addresses. Based on the generated index value, the address is fetched from the index and sent out of the box as the value.
We now have some serious questions to answer!
- How do we make sure that every key is hashed to unique index?
- How do we make sure that the result of hash function is within the index of hash table?
- What do we do if the hash table is full?
- Is there a possibility that a few values in hash table never be used?Is there a possibility that multiples keys hash to same index location?
- How do we design a hash function? Are there any rules?
- How do we know we have designed a good hash function?
Explore more, to know more!