A hash table is a data structure that stores key–value pairs and retrieves any value in approximately O(1) time — constant, regardless of how many items are stored. It achieves this by using a hash function to convert a key into an array index, jumping directly to the right location rather than searching from the beginning.
What is a hash function?
A hash function takes an input (the key) and returns a fixed-size integer called the hash value or hash code. The hash code is then used as an index into an underlying array.
The simplest hash function for integer keys is the modulo operation:
index = key mod table_size
Worked example: table size = 7, keys = 10, 25, 34, 18
| Key | Calculation | Index |
|---|---|---|
| 10 | 10 mod 7 | 3 |
| 25 | 25 mod 7 | 4 |
| 34 | 34 mod 7 | 6 |
| 18 | 18 mod 7 | 4 ← collision! |
Key 25 and key 18 both map to index 4. This is a collision — two different keys produce the same hash value.
For string keys, hash functions commonly sum the ASCII values of each character, often weighted by position, then apply modulo:
hash("cat") = (ord('c') × 31² + ord('a') × 31¹ + ord('t') × 31⁰) mod table_size
A good hash function distributes keys evenly across the array, minimising collisions.
What is a collision, and why does it happen?
A collision occurs whenever two different keys produce the same hash value. Collisions are mathematically inevitable whenever the number of possible keys exceeds the table size — which is almost always.
The birthday problem illustrates why collisions occur faster than intuition suggests: in a group of just 23 people, there is a greater than 50% chance that two share the same birthday — even though there are 365 possible birthdays. Similarly, a hash table of 365 slots fills up with collisions well before it holds 365 items.
Collisions are not failures — they are expected. The key is to handle them gracefully.
How does chaining resolve collisions?
Chaining (also called separate chaining) stores all items that hash to the same index in a linked list (or similar structure) at that index. The array slots hold lists, not single values.
Using the previous example (table size = 7):
Index 3: [10]
Index 4: [25] → [18] ← both keys stored in a chain
Index 6: [34]
To look up key 18:
- Compute 18 mod 7 = 4
- Go to index 4
- Walk the chain: 25 ≠ 18 → 18 = 18 ✓ Found
If the chains stay short (on average 1–2 items), lookup is still approximately O(1). In the worst case — all keys hashing to the same index — lookup degrades to O(n), but a good hash function prevents this in practice.
How does open addressing resolve collisions?
Open addressing keeps all items inside the main array — no linked lists. When a collision occurs, the algorithm probes other slots until it finds an empty one.
Linear probing: try index, then index+1, index+2, … (wrapping around):
Key 18 hashes to index 4 → slot 4 taken by key 25
→ try index 5 → empty → store key 18 at index 5
Lookup follows the same probe sequence until the key is found or an empty slot is reached (meaning the key is absent).
Disadvantage: linear probing causes clustering — runs of occupied slots form, making further insertions slower. Quadratic probing and double hashing spread items more evenly.
How does a hash table compare with other data structures?
| Operation | Array (unsorted) | Sorted array | Linked list | Hash table (average) |
|---|---|---|---|---|
| Search | O(n) | O(log n) | O(n) | O(1) |
| Insert | O(1) (at end) | O(n) | O(1) (at head) | O(1) |
| Delete | O(n) | O(n) | O(n) | O(1) |
The O(1) average performance is why Python's dict type, JavaScript's object literals, and Java's HashMap are all implemented as hash tables. When you write student["name"] in Python, you are using a hash table.
What makes a good hash function?
A good hash function is:
- Deterministic: the same key always produces the same hash value
- Uniform: it distributes keys evenly across the table, minimising collisions
- Fast to compute: ideally O(1) for any key
- Avalanche effect: a small change in the key (one character, one bit) produces a completely different hash value — important for security uses
Frequently asked questions
Are Python dictionaries hash tables?
Yes. Python's dict is implemented as a hash table. When you write d = {"name": "Aisha"}, Python applies its built-in hash() function to the key "name", computes an index, and stores the value "Aisha" there. This is why dictionary lookup is O(1) regardless of how many items are in the dictionary — a crucial performance advantage over a list (which requires O(n) linear search).
What is the load factor of a hash table?
The load factor (λ) is the ratio of the number of stored items to the total number of array slots: λ = n / m. A low load factor (e.g. 0.25) means the table is mostly empty — few collisions but wasted memory. A high load factor (e.g. 0.9) means the table is nearly full — frequent collisions and slower lookups. Most implementations resize and rehash when the load factor exceeds a threshold (commonly 0.7 for open addressing).
How does a hash table differ from a hash used in security?
Both use hash functions, but for different purposes. A hash table uses a fast, non-cryptographic hash function to map keys to indices — it does not need to be hard to reverse. A cryptographic hash (like SHA-256) is deliberately designed to be irreversible and collision-resistant, so that finding two inputs with the same output is computationally infeasible. Cryptographic hashes are used for password storage and data integrity; hash tables are a data structure for efficient lookup.
Why does the table size matter, and why use a prime number?
Choosing a prime number as the table size reduces collisions when keys are not uniformly distributed. If the table size shares a common factor with many keys (e.g., table size = 10 and many keys are multiples of 2), several slots will be heavily used while others stay empty. A prime table size has no common factors with typical integer keys, distributing collisions more evenly across all slots.
Hash tables are one of computing's most elegant ideas — bring your questions to Professor Turing at aitutors.me and we will build one from scratch together.