Imagine a parking lot with a fixed number of spaces. When the lot is almost full, cars have to park farther away or in less convenient spots, making it harder to find your car. To fix this, the parking lot is expanded with more spaces, so cars can park comfortably and be found easily.
┌───────────────┐ ┌───────────────┐ ┌───────────────┐ │ Small Hash │ │ Load Factor │ │ Rehashing │ │ Table (Buckets)│─────▶│ Increases as │─────▶│ Create Larger │ │ [ ] [ ] [ ] │ │ items fill up │ │ Table & Move │ │ [x] [x] [ ] │ │ │ │ Items │ └───────────────┘ └───────────────┘ └───────────────┘ │ │ ▼ ▼ ┌─────────────────────────────┐ ┌─────────────────────────┐ │ Collisions Increase │ │ Larger Table Has More │ │ Searching Slows Down │ │ Buckets, Reducing Load │ └─────────────────────────────┘ │ Factor and Collisions │ └─────────────────────────┘
class HashTable: def __init__(self, size=4): self.size = size self.buckets = [[] for _ in range(size)] self.count = 0 def _hash(self, key): return hash(key) % self.size def insert(self, key, value): if self.load_factor() > 0.7: self.rehash() index = self._hash(key) for i, (k, v) in enumerate(self.buckets[index]): if k == key: self.buckets[index][i] = (key, value) return self.buckets[index].append((key, value)) self.count += 1 def load_factor(self): return self.count / self.size 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 key, value in bucket: self.insert(key, value) def __str__(self): return str(self.buckets) ht = HashTable() for i in range(10): ht.insert(f'key{i}', i) print(f'Load factor after inserts: {ht.load_factor():.2f}') print('Hash table buckets:', ht)