Hash Table Example

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 map key to a hash value within the range of the array.
• When we retrieve the data with key, we hash the key again 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: