दो अलग-अलग कुंजियां एक ही बकेट में हैश हो सकती हैं — एक टकराव। हैश टेबल्स टकरावों को हल करके और बकेट भीड़ से पहले रीसाइज़ करके औसतन 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) तक बढ़ सकते हैं — प्रदर्शन-संवेदनशील कोड और प्रतिकूल-इनपुट (hash-flooding) बचावों के लिए महत्वपूर्ण।
लोड फैक्टर को समझने से वास्तविक लाइब्रेरीज़ द्वारा प्रदान किए गए मेमोरी/स्पीड ट्यूनिंग नॉब्स भी समझ आता है।
विस्तृत उत्तरों के साथ IT इंटरव्यू प्रश्नों की एक लाइब्रेरी — जूनियर से सीनियर तक।
दान करें