Intermediate·2 min read
Hashing
Hash functions, collision resolution, and hash table operations.
Hashing
Hashing maps keys to indices in a table for O(1) average lookups.
Hash Function
A function that converts a key into an array index:
``
hash(key) = key % table_size
hash("hello") = hash_code("hello") % 1000
`
A good hash function distributes keys uniformly across the table.
Collision Resolution
When two keys hash to the same index:
Open Hashing (Separate Chaining):
Each bucket is a linked list. Collisions just append to the list.
`
Index 0: →
Index 1: → [15] → [25] → NULL
Index 2: → [12] → NULL
Index 3: → [33] → [43] → NULL
``
Closed Hashing (Open Addressing):
Find another empty slot in the table.
| Header | ||
|---|---|---|
| Method | Formula | Behavior |
| Header | ||
|---|---|---|
| Linear Probing | (h + i) % size | Check h, h+1, h+2, ... |
| Quadratic Probing | (h + i²) % size | Check h, h+1, h+4, ... |
| Double Hashing | (h + i·h2) % size | Use second hash for step size |
Load Factor
α = n / size (number of elements / table size)
- Chaining: α can be > 1, but performance degrades
- Open addressing: α must be < 1, ideally < 0.7
- Rehashing: When α gets too high, create a larger table and reinsert everything
Applications
- Dictionary/HashMap: O(1) get/set
- Database indexing: Fast record lookups
- Caching: LRU cache implementation
- Symbol tables: Compilers use hash tables for variable names
- Deduplication: Finding duplicate elements in O(n)
Code Example
python
class HashTable:
def __init__(self, size=16):
self.size = size
self.count = 0
self.buckets = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def _load_factor(self):
return self.count / self.size
def put(self, key, value):
if self._load_factor() > 0.75:
self._rehash()
idx = self._hash(key)
bucket = self.buckets[idx]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self.count += 1
def get(self, key):
idx = self._hash(key)
for k, v in self.buckets[idx]:
if k == key:
return v
raise KeyError(key)
def delete(self, key):
idx = self._hash(key)
bucket = self.buckets[idx]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket.pop(i)
self.count -= 1
return
raise KeyError(key)
def _rehash(self):
old_buckets = self.buckets
self.size *= 2
self.buckets = [[] for _ in range(self.size)]
self.count = 0
for bucket in old_buckets:
for k, v in bucket:
self.put(k, v)
def __str__(self):
items = []
for bucket in self.buckets:
for k, v in bucket:
items.append(f"{k}: {v}")
return "{" + ", ".join(items) + "}"
ht = HashTable()
ht.put("name", "Alice")
ht.put("age", 21)
ht.put("course", "DSA")
print(ht)
print(f"Get name: {ht.get('name')}")
ht.delete("age")
print(f"After delete: {ht}")Practice Problems
- 01Implement a hash map from scratch using separate chaining
- 02Find the first non-repeating character in a string using hashing
- 03Group all anagrams from a list of strings