What is a hash table?

A hash table is a data structure that stores (key → value) pairs and allows elements to be found almost instantly, in O(1) time on average.

#How it works

1. Each key passes through a hash function, which turns it into a number, the hash.
2. This hash points to which "slot" (index) of the table the value should be written to.
3. When looking up the same key, the hash function computes the same index, and the element is found quickly.

#The collision problem

Sometimes different keys produce the same hash, this is a collision. It is resolved with:

• chaining, the slot stores a list of all elements with the same hash,
• open addressing, searching for the next free slot.

#Advantages

• fast access to data, O(1) on average;
• simple insertion and removal.

#Example

In Python this is a dictionary (dict), in Java, HashMap, in C++, unordered_map.

Hash tables underlie caches, dictionaries, databases, and many algorithms where fast lookup by key matters.