What is a hash table and how does it work?
A hash table is a data structure that maps keys to values using a hash function. It achieves constant-time operations on average by placing entries in buckets based on computed hash codes rather than searching linearly.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Internal Structure
A hash table contains three main components:
-
Hash function: Converts a key into an integer hash code.
-
Buckets or slots: Fixed-size storage locations holding entries.
-
Load factor: The ratio of stored entries to available buckets.
A typical lookup follows this process:
-
Compute the key’s hash code.
-
Convert that code into a bucket index.
-
Locate the bucket.
-
Compare the stored key with the requested key to confirm a match.
-
Resolve any collision if the bucket contains multiple candidates.
For example, a simple hash function might use hash(key) % bucket_count. Python’s built-in hash() is randomized for supported types such as str and bytes, helping prevent predictable collision patterns.
Hashable Keys
Hash-table keys must be hashable, meaning they have a hash value and can be compared reliably with equivalent keys.
-
str,int,float,tuple, andfrozensetare commonly hashable. -
listanddictare unhashable because they are mutable containers. -
A
tupleis hashable only when all its elements are hashable.
# Valid keys
employee_id = 42
coordinates = (10, 20)
# Invalid keys
names = ["Ada", "Grace"] # list is unhashable
settings = {"role": "admin"} # dict is unhashable
Built-in hashable types are effectively immutable because changing a key after insertion could change where it should be stored.
Collision Handling
Different keys can produce the same hash code, creating a collision. Common strategies include:
| Strategy | How It Works | Main Trade-off |
|---|---|---|
| Separate chaining | Each bucket stores a collection of entries, often a list | Simple to implement; pointer overhead and potentially long lists |
| Linear probing | Searches consecutive slots after a collision | Good cache locality; clustering can increase probe counts |
| Quadratic probing | Searches using squared probe offsets | Reduces clustering; may not inspect every slot |
| Double hashing | Uses a second hash function to determine the step size | Fewer clustering patterns; more computation |
A from-scratch implementation often uses separate chaining, represented as a list of lists. CPython 3.12’s dict instead uses a compact open-addressing table with probing. A Python set is also implemented as a hash table, but it stores keys rather than key-value pairs.
Example Walkthrough
Suppose a table has four buckets, and the hash function returns hash(key) % 4:
| Operation | Hash Index | Result |
|---|---|---|
Insert "cat" |
1 | "cat" is placed in bucket 1 |
Insert "dog" |
2 | "dog" is placed in bucket 2 |
Insert "bird" |
1 | It shares bucket 1 with "cat" |
Look up "bird" |
1 | Search bucket 1 and confirm the exact key |
A lookup must compare keys after finding a bucket because another key may share the same index.
Resizing and Load Factor
The load factor indicates how full the table is:
load factor = number of entries / number of buckets
As entries increase, collisions become more likely. A table can therefore resize by allocating more buckets and rehashing every entry into its new position.
-
Trigger: A common threshold is a load factor around
0.66or0.75, depending on the implementation. -
Rehashing: Every existing key is hashed again and placed in the new table.
-
Cost: A single resize takes
O(n)time. -
Amortized insertion:
O(1)across a sequence of insertions because the total rehashing cost is spread across many operations.
Complexity
The following bounds assume fixed-size keys and constant-time key comparison:
| Operation | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Lookup | O(1) |
O(1) |
O(n) |
| Insert | O(1) |
O(1) amortized |
O(n) |
| Delete | O(1) |
O(1) |
O(n) |
-
Best case: The desired bucket or slot is found immediately.
-
Average case: Uniform hashing and a controlled load factor keep probes or chain lengths small.
-
Worst case: Many keys collide in one bucket or probing becomes expensive.
-
Space:
O(n)fornstored entries, excluding the input; no recursion stack is used.
Python 3.12 guarantees that dict preserves insertion order, but it does not guarantee that iteration order follows hash-code order.
Interview Tips
-
Distinguish average
O(1)from amortizedO(1): average concerns hashing behavior, while amortized concerns occasional resizing costs. -
Explain how duplicate keys are handled: they normally update the existing value instead of creating another entry.
-
Mention that deleting from a chained table simply removes the entry from its chain, while deleting from an open-addressed table needs tombstones or backward-shift deletion.
-
Common follow-up questions cover load factors, rehashing, collision attacks, thread safety, and implementing a hash map with separate chaining.