दुई अलग कुञ्जीहरू एउटै बकेटमा हैश हुन सक्छन् — एक टकराव। हैश टेबलहरू औसतमा 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
| अपरेशन | औसत |
|---|
एक रिसाइज O(n) छ तर दुर्लभ रूपमा हुन्छ, त्यसैले यो amortizes to O(1) प्रति सम्मिलन।
यी आन्तरिक भागहरूले व्याख्या गर्छन् कि किन हैश म्यापहरू औसतमा छिटो छन् तर O(n) मा स्पाइक हुन सक्छन् — performance-sensitive कोड र adversarial-input (hash-flooding) रक्षाको लागि महत्त्वपूर्ण।
लोड फ्याक्टर बुझ्नुले वास्तविक लाइब्रेरीहरू द्वारा उजागर गरिएको memory/speed ट्यूनिङ नबहरूको पनि व्याख्या गर्छ।
| सबैभन्दा खराब |
|---|
| खोज / सम्मिलन / हटाउ | O(1) | O(n) |
| एकल रिसाइज | — | O(n) |
| सम्मिलन (amortized, रिसाइजिङ सहित) | O(1) | — |