What is a Hash Table?
Data Structures·6 min read·code in python
A hash table is a data structure that stores key-value pairs and finds any value in O(1) time on average. It runs each key through a hash function to compute an array index, then stores the value there. When two keys land on the same slot, a collision, it chains them in a small list.
The intuition: compute where the answer lives
Imagine looking up a friend's phone number. In an unsorted list you'd scan every entry until you hit the right name. A hash table instead does arithmetic on the name itself to jump straight to the slot where the number is stored, no scanning. That single trick, computing a location directly from the key, is what makes lookups feel instant.
The price is that you give up order. A hash table won't hand you keys sorted, and it can't cheaply answer 'what's the next largest key.' In exchange you get near-constant-time insert, lookup, and delete, which is exactly the trade most interview problems are quietly asking for.
How hashing turns a key into an index
A hash function takes a key of almost any type, string, number, tuple, and returns a fixed-size integer. The table reduces that integer modulo the number of buckets to get an array index, then stores the (key, value) pair there. Because array indexing is itself O(1), and a good hash spreads keys evenly across buckets, most operations touch only a single slot.
As you add entries, the load factor (items divided by buckets) climbs. Once it crosses a threshold, often around 0.75, the table allocates a larger array and rehashes every existing key into it. That resize costs O(n), but it happens rarely, so the amortized cost per operation stays O(1). Keeping the load factor bounded is what preserves fast lookups as the table grows.
Collisions: when two keys share a slot
Different keys can hash to the same index, a collision, and every real hash table needs a plan for it. The most common is separate chaining: each bucket holds a small list, and colliding entries live in that list. A lookup finds the bucket, then scans its (usually tiny) list for a matching key. The alternative, open addressing, probes forward to the next free slot instead of keeping lists.
Collisions are why O(1) is an average, not a guarantee. If every key collided into one bucket, a lookup would degrade to O(n): a plain linear scan. A good hash function plus a bounded load factor keeps chains short, so in practice you get constant time. It also explains why untrusted keys are a real attack surface: inputs engineered to collide can deliberately force worst-case behavior.
The code
class HashTable:
def __init__(self, capacity=8):
self.buckets = [[] for _ in range(capacity)]
self.size = 0
def _index(self, key):
return hash(key) % len(self.buckets)
def put(self, key, value):
bucket = self.buckets[self._index(key)]
for i, (k, _) in enumerate(bucket):
if k == key: # key exists -> overwrite
bucket[i] = (key, value)
return
bucket.append((key, value)) # new key -> chain it
self.size += 1
def get(self, key):
bucket = self.buckets[self._index(key)]
for k, v in bucket:
if k == key:
return v
raise KeyError(key)Run it in the browser IDE, free on the platform. Open the IDE
Complexity
| Time | O(1) average for insert, lookup, and delete; O(n) worst case when many keys collide into one bucket. |
|---|---|
| Space | O(n) for n stored entries. |
The O(1) is an amortized average that assumes a good hash function and a bounded load factor. Clustered or adversarial keys, or a table that never resizes, push operations toward O(n).
Watch it run
Reading the steps is one thing. Watching any of these move on your own input, one step at a time, is where the picture sticks.
When to use it
- Membership tests: keep a set of seen items and answer 'have I encountered this before?' in O(1) instead of re-scanning a list.
- Frequency counting: map each item to a running count for character counts, word counts, or grouping anagrams.
- Caching and memoization: store computed results keyed by their inputs so you never recompute the same call twice.
- Collapsing nested loops: replace an O(n^2) 'find a matching pair' scan with a single pass that checks a hash map: the classic Two Sum trick.
Watch out for
- Assuming O(1) always holds. A poor hash function or adversarial keys can collide everything into one bucket and quietly degrade operations to O(n).
- Using mutable or unhashable objects as keys. In Python a list can't be a key at all, and mutating a key after insertion breaks your ability to find it again.
- Expecting order. Hash tables don't store keys sorted, so don't reach for one when you need range queries or ordered traversal, use a balanced tree or sorted structure instead.
Hash Table: questions we get
What is the time complexity of a hash table?
Insert, lookup, and delete are all O(1) on average. The worst case is O(n), which happens when many keys collide into the same bucket and the operation degrades to scanning a list. With a decent hash function and a bounded load factor, you can rely on the average in practice.
Is a hash table hard to learn?
The core idea is beginner-friendly: run the key through a function to get an index, then store the value there. The trickier parts are collisions, load factor, and resizing. It tends to click fast once you watch a key get hashed into a bucket step by step rather than reading it as prose.
What's the difference between a hash table and a hash map?
Practically none: they refer to the same key-value structure. 'Hash table' is the classic data-structure name, while 'hash map' is a common implementation name (Java's HashMap, C++'s unordered_map). Python calls it a dict. A hash set is the same idea storing only keys, for fast membership tests.
When should I use a hash table instead of an array?
Use a hash table when you look things up by a key rather than by position, or when you need fast membership, counting, or deduplication. Use an array when you need ordered data, index-based access, or range queries. Many interview optimizations swap an array scan for a hash lookup to drop from O(n^2) to O(n).
Related concepts
Reading is the easy part. In a batch you build it, say it out loud in a scored mock round and hear what an interviewer would think.
Talk to mentor