Hash tables maps an arbitrary data type to another arbitrary data type using hashing.
Data is stored in an array, where each data value has an unique index.
- When we add
(key, value)pair to the array, we use a hash function to mapkeyto a hash value within the range of the array. - When we retrieve the data with
key, we hash thekeyagain and look up the data in the array with the corresponding index.
Graphical example of hash table
We need to deal with collisions as the possibility of keys increases, collision is unavoidable by the pigeonhole principle. An example of this is using separate chaining, where each hash value corresponds to a list:
