ਹੈਸ਼ ਟੇਬਲ ਟਕਰਾਵਾਂ, ਲੋਡ ਫੈਕਟਰ ਅਤੇ ਰੀਸਾਈਜ਼ਿੰਗ ਨੂੰ ਕਿਵੇਂ ਸੰਭਾਲਦੇ ਹਨ?

Question

Accepted Answer

ਦੋ ਵੱਖ-ਵੱਖ ਕੁੰਜੀਆਂ ਉਸੇ **bucket** ਨੂੰ ਹੈਸ਼ ਕਰ ਸਕਦੀਆਂ ਹਨ — ਇੱਕ **ਟਕਰਾਅ**। ਹੈਸ਼ ਟੇਬਲ ਔਸਤ ਵਿੱਚ O(1) ਰਹਿੰਦੇ ਹਨ ਟਕਰਾਵਾਂ ਨੂੰ ਹੱਲ ਕਰਕੇ ਅਤੇ buckets ਭਰੀਆਂ ਹੋਣ ਤੋਂ ਪਹਿਲਾਂ **ਰੀਸਾਈਜ਼** ਕਰਕੇ, **ਲੋਡ ਫੈਕਟਰ** ਦੁਆਰਾ ਕੰਟਰੋਲ ਕੀਤਾ ਜਾਂਦਾ ਹੈ।

## ਟਕਰਾਅ ਦਾ ਹੱਲ

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

## ਲੋਡ ਫੈਕਟਰ ਅਤੇ ਰੀਸਾਈਜ਼ਿੰਗ

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

## ਜਟਿਲਤਾ

| ਓਪਰੇਸ਼ਨ | ਔਸਤ | ਸਭ ਤੋਂ ਖਰਾਬ |
|---|---|---|
| ਖੋਜ / ਸ਼ਾਮਿਲ ਕਰਨਾ / ਹਟਾਉਣਾ | O(1) | O(n) |
| ਸਿੰਗਲ ਰੀਸਾਈਜ਼ | — | O(n) |
| ਸ਼ਾਮਿਲ ਕਰਨਾ (amortized, ਰੀਸਾਈਜ਼ਿੰਗ ਦੇ ਨਾਲ) | O(1) | — |

ਇੱਕ ਰੀਸਾਈਜ਼ O(n) ਹੈ ਪਰ ਦੁਰਲੱਭ ਤਰੀਕੇ ਨਾਲ ਹੁੰਦਾ ਹੈ, ਇਸ ਲਈ ਇਹ **amortizes to O(1)** ਪ্রति ਸ਼ਾਮਿਲ।

## ਟ੍ਰੇਡ-ਆਫ

- **Chaining:** ਸਧਾਰਨ, gracefully ਘਟਦੇ ਹਨ, ਪਰ ਵਾਧੂ pointers ਵਰਤਦੇ ਹਨ ਅਤੇ ਗ਼ਲਤ cache locality ਹੈ।
- **Open addressing:** cache-friendly ਅਤੇ compact, ਪਰ ਉੱਚੇ load factor ਪ੍ਰਤੀ ਸੰਵੇਦਨਸ਼ੀਲ ਅਤੇ ਸਾਵਧਾਨੀ ਨਾਲ deletion ਦੀ ਲੋੜ ਹੈ (tombstones)।

## ਇਹ ਕਿਉਂ ਮਾਇਨੇ ਰੱਖਦਾ ਹੈ

ਇਹ ਅੰਦਰੂਨੀ ਵੇਰਵੇ ਵਿਖਾਉਂਦੇ ਹਨ *ਕਿਉਂ* hash maps ਔਸਤ ਵਿੱਚ ਤੇਜ਼ ਹੋ ਸਕਦੇ ਹਨ ਪਰ O(n) ਵਿੱਚ ਸਪਾਈਕ ਕਰ ਸਕਦੇ ਹਨ — performance-sensitive ਕੋਡ ਅਤੇ adversarial-input (hash-flooding) ਰੱਖਿਆ ਲਈ ਮਹੱਤਵਪੂਰਨ।

Load factor ਨੂੰ ਸਮਝਣਾ memory/speed tuning knobs ਦੀ ਵੀ ਵਿਆਖਿਆ ਕਰਦਾ ਹੈ ਜੋ ਅਸਲ libraries ਦ੍ਵਾਰਾ ਉਜਾਗਰ ਕੀਤੇ ਜਾਂਦੇ ਹਨ।

ਓਪਰੇਸ਼ਨ	ਔਸਤ	ਸਭ ਤੋਂ ਖਰਾਬ
ਖੋਜ / ਸ਼ਾਮਿਲ ਕਰਨਾ / ਹਟਾਉਣਾ	O(1)	O(n)
ਸਿੰਗਲ ਰੀਸਾਈਜ਼	—	O(n)
ਸ਼ਾਮਿਲ ਕਰਨਾ (amortized, ਰੀਸਾਈਜ਼ਿੰਗ ਦੇ ਨਾਲ)	O(1)	—