A hash table is a data structure that maps keys to values for highly efficient lookup.There are several ways to implement the hash table. Here I would like to describe a simple and common implementation.
We use an array of linked lists and a hash code function. To insert a key (which may be string or number or any other data type) and the value we do the following.
-
Compute the hash code (usually it will be in int or long).
Note : Two or more different keys might have the same hash code because of the obvious fact that keys are infinite and ints are finite. (In Computer Science infinite is not actually infinite , it is a large number)
-
Map the hash code to an index in the array. This can be done something like hashCode(key) mod arrayLength , which will generate a number (index) from 0 to arrayLength-1.
Note: Observe that two different keys might generate the same hash code and map to the same index
-
At this index , there is a linked list of keys and values. Add the <Key , Value> pair to the end od the linked list
Time Complexity
In the best case, each key generates a hash code which might map to the different index. And we know that the time complexity to get an element from an array is constant knowing its index. So BEST case is O(1)
In the worst case, all the hash codes generated by the keys might map to the same index which in turn will make the linked list length long. And to search for a key it might take O(n) time.
When we observe the above cases we can come to the conclude that generating hash code takes a big role in time complexity. HashCode function uses prime numbers to generate the indexes.