How does a hash table store data?

A hash table stores data as "key -> value" pairs, using an array and a hash function that determines which slot an element is stored in.

#Step by step

1. When an element is added, the hash of the key is computed:

where N is the size of the array. 2. The element is placed in the slot with that index. 3. On lookup or removal, the same hash function is used: the index is computed from the key, and the element is accessed directly.

#Example

Let the table size be 10, and hash("dog") = 23. Then 23 % 10 = 3, and the pair ("dog", "animal") is stored in slot #3.

#If there is a collision (two keys give the same index)

• with chaining, the slot stores a list of all elements with that index;
• with open addressing, the table searches for the next free slot.

So a hash table is essentially an array + hash function + a way of handling collisions, which allows data to be found by key quickly without a full scan.