ہیش ٹیبلز تنازعات (Collisions)، لوڈ فیکٹر، اور ری سائزنگ کو کیسے ہینڈل کرتے ہیں؟

Question

Accepted Answer

دو مختلف کلیدیں ایک **ہی بکٹ** میں ہیش ہو سکتی ہیں — ایک **تنازعہ**۔ ہیش ٹیبلز اوسط میں O(1) رہتے ہیں تنازعات کو حل کر کے اور بکٹ کے بھرنے سے پہلے **ری سائز** کر کے، جو **لوڈ فیکٹر** سے کنٹرول ہوتا ہے۔

## Collision resolution

```text
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 اور resizing

```text
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
```

```python
# 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) |
| سنگل resize | — | O(n) |
| insert (amortized, resizing کے ساتھ) | O(1) | — |

ایک resize O(n) ہے لیکن کم ہی ہوتا ہے، اس لیے یہ **ہر insert میں O(1) amortize** ہوتا ہے۔

## Trade-offs

- **Chaining:** سادہ، خوبصورتی سے خراب ہوتا ہے، لیکن اضافی pointers استعمال کرتا ہے اور cache locality خراب ہے۔
- **Open addressing:** cache-friendly اور compact، لیکن اعلیٰ load factor کے لیے حساس اور احتیاط سے deletion کی ضرورت (tombstones)۔

## یہ کیوں اہم ہے

یہ internals بیان کرتے ہیں کہ *کیوں* ہیش میپز اوسط میں تیز ہیں پھر بھی O(n) تک سکتے ہیں — performance-sensitive کوڈ اور adversarial-input (hash-flooding) defenses کے لیے اہم۔

Load factor کو سمجھنا یہ بھی بیان کرتا ہے کہ حقیقی libraries میں memory/speed tuning knobs کیوں exposed ہیں۔