როგორ ართავსებს ჰეშ-ცხრილები შეჯახებებს, დატვირთვის კოეფიციენტს და ზომის გაზრდას?

Question

Accepted Answer

ორი განსხვავებული გასაღები შეიძლება ჰეშირდეს **იმავე bucket-ში** — ეს არის **შეჯახება**. ჰეშ-ცხრილები O(1) საშუალოდ რჩებიან შეჯახებების გადაჭრის და **ზომის გაზრდის** მეშვეობით bucket-ებ გადატვირთვის წინ, რაც კონტროლირდება **დატვირთვის კოეფიციენტით**.

## შეჯახების გადაჭრა

```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 O(1)-ში** ჩასმაზე.

## კომპრომისები

- **Chaining:** მარტივი, მცირდება გამგრძელებლად, მაგრამ იყენებს დამატებით მეჩი და სუსტი cache-ის ლოკალობა.
- **Open addressing:** cache-მეგობრული და კომპაქტური, მაგრამ დატვირთვის მაღალი კოეფიციენტის მიმართ მგრძნობიარი და საჭიროებს ფრთხილ წაშლას (tombstones).

## რატომ აქვს მნიშვნელობა

ეს შიდა მექანიზმები ხსნის, თუ *რატომ* არიან ჰეშ-რუკები სწრაფი საშუალოდ, მაგრამ შეიძლება გამოწვევდეს O(n) სპايკებს — ეს ცვლადი არის performance-sensitive კოდისთვის და adversarial-input (hash-flooding) თავდაცვისთვის. დატვირთვის კოეფიციენტის გაგება ასევე ხსნის memory/speed tuning knobs-ებს, რომლებიც რეალური ბიბლიოთეკებით ავლენ.