Cad is tábla hash ann agus conas a bhaintear amach O(1) cuardaigh?

Question

Accepted Answer

Stóraíonn **tábla hash** (hash map) péireanna **eochair → luach** agus cuireann sé ar fáil **O(1) ar an meánchás** do ionsá, cuardaigh, agus scrios. Oibríonn sé trí gach eochair a rith trí **fheidhm hash** a mhapálíonn í go hinnéacs san fhoras array bunúsach ("balcéad").

## Conas a oibríonn sé

```text
key "cat" --hash()--> 3   buckets:
key "dog" --hash()--> 0     [0] -> ("dog", 5)
                            [1]
                            [2]
                            [3] -> ("cat", 9)
```

## Sampla

```python
phone = {}
phone['alice'] = 555_1234   # insert -> hash 'alice' to a bucket
num = phone['alice']        # lookup -> hash again, jump to bucket
del phone['alice']          # delete
'bob' in phone              # membership -> O(1) average
```

## Castacht

| Oibríochta | Meánchás | Droch-chás |
|---|---|---|
| ionsá | O(1) | O(n) |
| cuardaigh | O(1) | O(n) |
| scrios | O(1) | O(n) |

Tarlaíonn an **droch-chás** O(n) nuair a bhíonn go leor eochracha ag tuairiscint isteach sa bhealcéad céanna.

## Comhéifeachtaí

- **Nicéalta:** rochtain an-tapa bunaithe ar eochracha; eochracha lenar féidir oibriú leo.
- **Laigí:** gan ordú ar an eochracha; cuimhne bhreise; droch-chás O(n); teastaíonn feidhm hash mhaith.

## Cén fáth a bhíonn sé tábhachtach

Is é an tábla hash an struchtúr is mó a úsáidtear san fheidhm - taobh thiar de dhictonáirelí, tacair, taisce, innéacsanna bunachar sonraí, agus dídhúblú.

A bhheith ag ionadú scanadh líneach le cuardaigh hash is ceann de na bealaí is coitianta a bhíonn ag iompú algartam O(n²) ina O(n).