બે અલગ-અલગ કીઓ એક જ બકેટમાં હેશ થઈ શકે છે — જેને કોલિઝન કહેવાય છે. હેશ ટેબલ્સ કોલિઝનોને રિઝોલ્વ કરીને અને બકેટ્સ ભીડ વધતા પહેલાં રીસાઇઝ કરીને સરેરાશ 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) છે પણ ભાગ્યે જ થાય છે, તેથી તે O(1) માં સમોર્ટાઇઝ થાય છે પ્રતિ ઇનસર્ટ.
આ આંતરિક વિગતો સમજાવે છે કે શા માટે હેશ મેપ્સ સરેરાશ તીવ્ર છે પણ O(n) સુધી વધી શકે છે — performance-sensitive code અને adversarial-input (hash-flooding) defense માટે નિર્ણાયક.
લોડ ફેક્ટર સમજવું પણ મેમોરી/સ્પીડ ટ્યુનિંગ નોબ્સને સમજાવે છે જે વાસ્તવિક લાઇબ્રેરીઓ પ્રદાન કરે છે.