Menene teburin hash kuma ta yaya zai iya samun O(1) lookup?

Question

Accepted Answer

A **teburin hash** (hash map) yana adana **key → value** nau'i da kuma yana ba da **matsakaicin O(1)** saka, lookup, da share. Yana aiki ta hanyar turo kowane key ta wata **hash function** da take je wa wani index a cikin jerin da ke ƙarƙashi (wata "bucket").

## Ta yaya ake aiki

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

## Misali

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

## Muni

| Aiki | Matsakaici | Mafi daɗi |
|---|---|---|
| saka | O(1) | O(n) |
| lookup | O(1) | O(n) |
| share | O(1) | O(n) |

**Mafi daɗi na yau** O(n) yana faruwa lokacin da alwatika masu yawa suka tudu a gida jiya.

## Musanya

- **Karfin:** sauri sosai key-based access; reshe maye.
- **Rauni:** babu jeri na keys; ƙarin ƙarfi; O(n) mafi daɗi; bukatar kyakkyawan hash function.

## Me ya sa ya matuwa

Teburin hash sune akkaai sananne a aikace-aikace — bayan jita, saiti, caches, database indexes, da share-tsoke.

Maye tsakanin gudu ta hanyar linzami da hash lookup shine ɗaya daga cikin mafi yawan hanyoyi don juyawa da O(n²) algorithm zuwa O(n).