दोन वेगवेगळ्या की एकाच बकेटमध्ये हॅश हो शकतात — एक टकराव. हॅश टेबल्स टकराव सोडवून आणि बकेट्स गर्दीचे न होते तेव्हा रिसाइজ करून सरासरीने O(1) राहतात, जे लोड फॅक्टर द्वारे नियंत्रित होते.
Separate chaining: each bucket holds a list
[3] -> ("cat",9) -> ("rat",2) # both hashed to 3
Open addressing: probe to the next free slot
hash=3 taken -> try 4 -> try 5 ... (linear probing)
load factor α = number_of_entries / number_of_buckets
α rises -> more collisions -> slower lookups
When α exceeds a threshold (e.g. 0.75):
-> allocate a bigger array (usually 2x)
-> REHASH every existing key into new buckets
# Conceptual resize
def _resize(self):
old = self.buckets
self.buckets = [None] * (len(old) * 2)
for entry in all_entries(old):
self._insert(entry.key, entry.value) # rehash into new array
| ऑपरेशन | सरासरी | सर्वकाळ |
|---|---|---|
| lookup / insert / delete | O(1) | O(n) |
| एकल रिसाइज | — | O(n) |
| insert (摊销, रिसाइजिंग सह) | O(1) | — |
एक रिसाइज O(n) आहे पण क्वचित घडते, तर तो प्रति insert O(1) मध्ये आपोआप होतो.
हे आंतरिक भाग का हॅश मॅप्स सरासरीने वेगवान आहेत तरी O(n) पर्यंत स्पाइक करू शकतात हे स्पष्ट करतात — performance-sensitive कोड आणि adversarial-input (hash-flooding) संरक्षणासाठी महत्वाचे.
लोड फॅक्टर समजणे देखील वास्तविक लायब्रेरींद्वारे उघडकेले केलेले मेमरी/speed ट्यूनिंग नॉब्स्स समजायला मदत करते.