Think of a hash table as a super-fast lookup table.
It uses a hash function to decide where to store or find each item in an array (called the table).
index = hash(key)
table[index] = value
So instead of searching linearly (O(n)), we can access data directly — almost like a magic index.
<aside> 💡
The goal is to find or insert items in O(1) time on average.
</aside>
| Term | Meaning |
|---|---|
| Bucket | Each cell (slot) of the array |
| Bucket Number | The index of that slot |
| Hash Function | A function that turns a key into a bucket number |
| Collision | When two different keys map to the same bucket |
| Probe | The act of checking a bucket to see what’s inside |
| Chaining | colliding entries are placed in a sequence (e.g. linked |
| list) attached to the “home” bucket | |
| Open Addressing | colliding entries are placed in other buckets in the |
| table. |
index = hash(key) % table_size
Ex:
If you had a hash table with 10 buckets (indexes 0–9) and your hash function for key "dog" returned 13, what index would "dog" actually be stored at?
index = 13 % 10 = 3
Modulo “wraps around” the hash value so it always fits the table’s range - 13, 23, 33, etc., would all end up in bucket 3 for a 10-slot table.
Different keys can hash to the same bucket number, we need ways to handle collisions.
| Type | How it works |
|---|---|
| Chaining | Each bucket holds a list (like a linked list) of all entries that hash to it |
| Open Addressing | If a bucket is full, find another empty one somewhere else in the table |