A Hash table (also known as a hash map) is a data structure used to store a set of items and retrieve any stored item quickly using key associated with the item. Every item stored in a hash table is stored against a key unique to the item.
For example, if we were to store details of students, we allocate an id to each student and then store the student details against his id. Here id corresponds to the key in hash table and student data is the actual data. Any time we require details of a student, we can give any student’s id to the hash map and the hash map can quickly return data of the student.
How a Hash Table Works
Let’s say we have 5 students enrolled for a course. In simple scenario, we can assign ids starting from 0 to 4 for each of the student. So the data looks like below:
Now, if we wish to look at the details of student with id-3, we can directly go to position 3 in the array and access the corresponding student details. Similarly changing any attributes of any student is as simple as going to the slot corresponding to student’s id and change the attributes.
The above data structure is a simple array and we are accessing element using the index where the element is stored. But what if the id/key is not a number? in this case the id can’t be used to access a position in the array. This is where hash tables come into picture.
A basic hash table internally uses an array to store data. It takes in the key/id of any object and tries to map the key to a number which lies in the range of size of the array. This mapping is done using a hash function.
For example if the hash table needs to store details of a student with key stud22, it uses a hashing function to convert that key to a number, for example stud22 is mapped to 4. Then the student’s data is stored at position 4 in the array. Next time when we wish to access the data of student with key/id stud22, the hash table uses the same hashing function to get the index position (which is 4). Then the data at position 4 in the array is accessed and returned to the requester.
Note: The hash function should consistently return the same index for a key. For example, the hash function when applied to stud22 should always return a same index (eg: 4) at any time.