Introduction
A hash table (also called a hash map) is a data structure that stores key-value pairs and allows extremely fast access to values based on their keys. Instead of searching through elements one by one like an array or linked list, a hash table uses a special function called a hash function to compute an index directly from the key, so most operations run in average O(1) time.
Cricket analogy: Instead of scanning down a scorecard row by row to find a player's stats, a hash table computes exactly where that player's row lives from their name, jumping straight there, average O(1) instead of a linear scan.
How It Works
Internally, a hash table maintains an array of fixed size called buckets. When you insert a key, the hash function converts the key into an integer (the hash code), which is then reduced modulo the array size to produce a bucket index. The value is stored at that bucket. To look up a key later, the same hash function is applied again to find the same bucket instantly, without scanning the rest of the structure.
Cricket analogy: A stadium assigns each ticket holder to a gate by taking their seat number modulo the number of gates, reapplying the same rule at re-entry sends them straight back to the same gate without checking every gate.
Explanation
A good hash function should be fast to compute and should distribute keys uniformly across buckets to minimize collisions (two keys mapping to the same bucket). The load factor, defined as the number of stored elements divided by the number of buckets, is a key health metric: as it grows too large, more collisions occur and performance degrades. Most hash table implementations automatically resize (rehash) the underlying array once the load factor crosses a threshold, typically around 0.7, doubling the bucket count and redistributing all existing keys.
Cricket analogy: A good team-selection formula should be quick to apply and spread players evenly across squads to avoid one squad being overloaded; once a squad's player-to-slot ratio (load factor) crosses about 70%, selectors expand the squad and redistribute, just like a hash table resizing and rehashing.
Example
# Python's built-in dict is a hash table implementation
phone_book = {}
# Insert key-value pairs -> average O(1)
phone_book["Alice"] = "555-1234"
phone_book["Bob"] = "555-5678"
phone_book["Carol"] = "555-9012"
# Lookup by key -> average O(1)
print(phone_book["Bob"]) # 555-5678
# Check membership -> average O(1)
print("Alice" in phone_book) # True
# Delete a key -> average O(1)
del phone_book["Carol"]
print(phone_book) # {'Alice': '555-1234', 'Bob': '555-5678'}
# A simplified illustration of a hash function
def simple_hash(key, num_buckets):
return sum(ord(ch) for ch in key) % num_buckets
print(simple_hash("Alice", 10))
print(simple_hash("Bob", 10))Complexity
For a well-implemented hash table with a good hash function and reasonable load factor, insertion, lookup, and deletion all run in average O(1) time. However, in the worst case, if many keys collide into the same bucket (for example, due to a poor hash function or adversarial input), these operations can degrade to O(n), since the bucket effectively becomes a linked list that must be scanned linearly. Space complexity is O(n) for storing n key-value pairs.
Cricket analogy: With a good selection formula and manageable squad sizes, finding a player's stats is average O(1); but if a poor formula crowds too many players into one squad, that squad becomes a list you must scan linearly, degrading to O(n), and the scoreboard overall still needs O(n) space for n players.
Key Takeaways
- A hash table maps keys to values using a hash function that computes a bucket index.
- Average-case time complexity for insert, lookup, and delete is O(1); worst case is O(n) due to collisions.
- The load factor (elements / buckets) determines when the table needs to resize (rehash).
- Python's dict and set are built-in hash table implementations.
- A good hash function distributes keys uniformly to minimize collisions.
Practice what you learned
1. What is the average time complexity of a lookup operation in a well-implemented hash table?
2. What is the load factor of a hash table?
3. Why do hash tables resize (rehash) when the load factor gets too high?
4. In Python, which built-in data type is implemented as a hash table?
5. What causes the worst-case O(n) time complexity in hash table operations?
Was this page helpful?