Conas a dhéileálann táblaí hash le tuairimíochtaí, fachtóir ualach, agus athmhéadú?

Question

IT Interview Practice · Accepted Answer

Is féidir le dhá eochair dhiscrèite a bheith i gcomhbhagairt go dtí an **bucket céanna** — **tuairimíocht** a thugtar air. Fanann táblaí hash ag O(1) ar an meán tríd na tuairimíochtaí a réiteach agus **athmhéadú** a dhéanamh sula mbíonn na buckets ró-líonta, á rialú ag an **fachtóir ualach**.

## Réiteach tuairimíochtaí

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

## Fachtóir ualach agus athmhéadú

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

## Casta

| Oibríocht | Meánach | Drochuair |
|---|---|---|
| cuardach / ionsá / scrios | O(1) | O(n) |
| athmhéadú amháin | — | O(n) |
| ionsá (ard-dhíbhircheartaithe, le hathmhéadú) | O(1) | — |

Tá athmhéadú ina O(n) ach tharlaíonn sé go hannamh, mar sin **díbhircheartaíonn sé go O(1)** in aghaidh an ionsuigh.

## Malartuithe

- **Slabhra:** simplí, díghrádú go réasúnach, ach úsáideann sé pointéirí bhreise agus tá drochéadálacht cache ann.
- **Seoladh oscailte:** barúil cache agus dlúth, ach mothúchán do fhachtóir ualach ard agus gá atá ann do scriosadh chúramach (tombstones).

## Cén fáth a bhfuil sé tábhachtach

Míníonn na intinn inmheánacha seo *cén fáth* a bhíonn spéis ag léarscáileanna hash ach go bhféadfadh siad imeall go dtí O(n) — ríthábhachtach do chód íogair feidhmíochta agus cosaint ar bhréagánacha achasáin (hash-flooding).

Tugann tuiscint ar fhachtóir ualach míniú freisin ar chnaipe dhúnta cuimhne/luas ar leith ag fíor-leabharlanna.

Oibríocht	Meánach	Drochuair
cuardach / ionsá / scrios	O(1)	O(n)
athmhéadú amháin	—	O(n)
ionsá (ard-dhíbhircheartaithe, le hathmhéadú)	O(1)	—

Réiteach tuairimíochtaí

Fachtóir ualach agus athmhéadú

Casta

Malartuithe

Cén fáth a bhfuil sé tábhachtach

Ceisteanna gaolmhara