A hash table is a data structure that stores data as key-value pairs and uses a hash function to quickly compute the storage location.
When we write:
set("abc", "xyz")
Internally, it becomes:
index = hash("abc") % array_size
A[index] = ("abc", "xyz")
This means: - The key (“abc”) is passed into a hash function - The hash function converts it into a number - That number is reduced into a valid array index using modulo (%) - The value is stored together with the key at that index
In real implementations, each slot is usually a “bucket”, not a single value:
A[index] = list of (key, value)
Even if there is only one element, it is still stored inside a bucket.
If no other key maps to the same index:
A[index] = [("abc", "xyz")]
This is the simplest case.
Different keys can map to the same index:
"abc" → index 2 "def" → index 2
In this case:
A[2] = [
("abc", "xyz"),
("def", "123")
]
This is called “chaining”.
If the same key is inserted again:
set("abc", "v1")
set("abc", "v2")
The hash table does NOT create duplicates.
Instead, it updates the existing value:
Before:
A[index] = [("abc", "v1")]
After:
A[index] = [("abc", "v2")]
Rule:
Same key → overwrite value
When we do:
get("abc")
Steps: 1. Compute index = hash(“abc”) % array_size 2. Go to A[index] 3. Search inside the bucket 4. Match the key exactly 5. Return its value
Example:
A[index] = [("abc", "xyz"), ("def", "123")]
Only return value where key == “abc”
Two-level thinking:
High-level:
key → hash(key) → index → value
Real implementation:
key → hash(key) → index → A[index] = list of (key, value)
- Hash table maps keys to values using a hash function - Index is computed as: hash(key) % array_size - Each slot is a bucket storing (key, value) - Same key overwrites old value - Different keys with same index are stored together (collision handling) - Average time complexity for get/set is O(1)
Hash tables are fast because they convert a key directly into an index, avoiding full scanning of data structures like arrays or lists.