రెండు విభిన్న కీలు ఒకే బకెట్కు హ్యాష్ చేయవచ్చు — ఘర్షణ. హ్యాష్ టేబిల్లు ఘర్షణలను పరిష్కరించడం ద్వారా మరియు బకెట్లు రద్దీగా ఉండటానికి ముందు పున నిర్ణయ చేయడం ద్వారా సగటున 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(1) | O(n) |
| ఒకే పున నిర్ణయ | — | O(n) |
| చేర్చు (amortized, పున నిర్ణయ కలిగి) | O(1) | — |
పున నిర్ణయ O(n) కానీ అరుదుగా జరుగుతుంది, కాబట్టి ఇది చేర్చుకు **O(1)**కు నిర్లక్ష్యం చేస్తుంది.
ఈ అంతర్నిర్మితాలు ఎందుకు హ్యాష్ మ్యాప్లు సగటున వేగవంతమైనవి కానీ O(n)కు ఎగిరిపోయే వాటిని వివరిస్తాయి — పనితీరుకు సంబంధించిన కోడ్ మరియు విరుద్ధ-ఇన్పుట్ (హ్యాష్-ఫ్లూడింగ్) రక్షణకు కీలకమైనది.
లోడ్ ఫ్యాక్టర్ను అర్థం చేసుకోవడం నిజమైన లైబ్రరీలచే బహిర్గతం చేయబడిన మెమరీ/స్పీడ్ ట్యూనింగ నాబ్లను కూడా వివరిస్తుంది.