Si përballehen tabelat hash me përplasjet, faktorin e ngarkesës dhe ndryshimin e madhësisë?

Question

IT Interview Practice · Accepted Answer

Dy çelësa të ndryshëm mund të caktojnë në **të njëjtën kovë** — një **përplasje**. Tabelat hash mbeten O(1) në mesatare duke zgjidhur përplasjet dhe **duke ndryshuar madhësinë** përpara se kovet të bëhen të mbipopuluara, të kontrolluar nga **faktori i ngarkesës**.

## Zgjidhja e përplasjeve

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

## Faktori i ngarkesës dhe ndryshimi i madhësisë

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

## Kompleksiteti

| Operacioni | Mesatare | Më i keqi |
|---|---|---|
| kërkimi / futja / fshirja | O(1) | O(n) |
| një ndryshim madhësie | — | O(n) |
| futja (e amortizuar, me ndryshim madhësie) | O(1) | — |

Ndryshimi i madhësisë është O(n) por ndodh rrallë, kështu që **amortizohej në O(1)** për futje.

## Këmbim

- **Zinxhirimi:** i thjeshtë, degradohet me elegancë, por përdor tregues shtesë dhe ka lokalitet të keq në cache.
- **Adresim i hapur:** miqësor për cache dhe kompakt, por i ndjeshëm ndaj faktorit të lartë të ngarkesës dhe kërkon fshirje të kujdesshme (lapidare).

## Pse ka rëndësi

Këto detaje të brendshme shpjegojnë *pse* hartëzuesit hash janë të shpejtë në mesatare përqype mund të kërcejnë në O(n) — vendimtare për kodin e ndjeshëm ndaj performancës dhe mbrojtjen kundër inputeve armiqësore (përmbytja hash).

Kuptimi i faktorit të ngarkesës gjithashtu shpjegon butonave e akordimit të memorjes/shpejtësisë të ekspozuara nga biblioteka reale.

Operacioni	Mesatare	Më i keqi
kërkimi / futja / fshirja	O(1)	O(n)
një ndryshim madhësie	—	O(n)
futja (e amortizuar, me ndryshim madhësie)	O(1)	—

Zgjidhja e përplasjeve

Faktori i ngarkesës dhe ndryshimi i madhësisë

Kompleksiteti

Këmbim

Pse ka rëndësi

Pyetje të ngjashme