Jedwali la hash ni nini na inapataje O(1) kutafuta?

Question

Accepted Answer

**Jedwali la hash** (hash map) linacheza jozi za **key → value** na hutoa wastani wa **O(1)** kuingiza, kutafuta, na kufuta. Inafanya kazi kwa kueneza kila ufunguo kupitia **kitendaji cha hash** ambacho kinakabidhi katika fahirisi katika safu ya msingi ("bucket").

## Jinsi Inavyofanya Kazi

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

## Mfano

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

## Ugumu wa Wakati

| Uendeshaji | Wastani | Mbaya zaidi |
|---|---|---|
| kuingiza | O(1) | O(n) |
| kutafuta | O(1) | O(n) |
| kufuta | O(1) | O(n) |

Ukali wa **mbaya zaidi** O(n) hutokea wakati funguo nyingi zinagongana katika bucket moja.

## Mahitaji

- **Nguvu:** upatikanaji wa haraka sana unaolingana na ufunguo; funguo zenye kubadilika.
- **Uhalifu:** hakuna mpangilio wa funguo; kumbukumbu inayoongezwa; O(n) hali mbaya; inahitaji kitendaji cha hash kizuri.

## Kwa Nini Kuna Muhimu

Jedwali la hash ni pengine muundo unaotumiwa zaidi katika mazoezi — nyuma ya kamusi, seti, akiba, fahirisi za hifadhi data, na kuondoa maigizo.

Kubadilisha utaftaji wa mstari na utaftaji wa hash ni mojawapo ya njia za kawaida sana kubadilisha algoriti O(n²) kuwa O(n).