Hash maps huongeza jinsi gani algorithms?

Question

Accepted Answer

**Hash map** (kamusi) inatoa **O(1) wastani** kwa utaftaji, kuingiza, na kufuta. Kubadilisha O(n) kumbukumbu kwa kasi hubadilisha algoritimu nyingi O(n²) kuwa O(n) kwa kuondoleza utaftaji mara kwa mara na utaftaji wa haraka.

## Wazo la msingi

Badala ya kutaftaji orodha kila wakati, hifadhi maadili uliyoona katika hash map na angalia uanachama katika wakati wa mara kwa mara.

## Mfano: jumla-mbili katika O(n)

```python
def two_sum(nums, target):
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:               # O(1) lookup
            return (seen[need], i)
        seen[x] = i
    return None

two_sum([2, 7, 11, 15], 9)             # -> (0, 1)
```

Bila ramani hii ni O(n²); nayo, ilipita moja.

## Matumizi ya kawaida

- **Kuondoleza kurudiwa / uanachama** na seti.
- **Kuhesabu masafa** (`Counter`).
- **Kuweka vikundi / kuandika faharasa** kwa ufunguo.
- **Akili / kukumbuka** matokeo.

## Ujumbe

- **Wastani:** O(1) kwa operesheni. **Mbaya:** O(n) katika mgogoro mkubwa. **Nafasi:** O(n).

## Pigo

Vifunguo lazima viwe **vinaweza kuheshimiwa** na vigeu visivyobadilika. Mgogoro wa kesi mbaya huharibu utendaji. Hash maps hazina mpangilio (tumia tofauti zilizounganishwa ikiwa mpangilio unamaanisha).

## Kwa nini inamaanisha

Hashing ni uboreshaji wa kawaida zaidi katika mahojiano ya kuandika na mifumo halisi — inabadilisha "taftaji tena na tena" kuwa "angalia mara moja".

Mahaba wa nafasi kwa kasi ni kiwango cha uhandisi cha kurudia.

Hesabu ya masafa, akili, na kuandika faharasa zote zinasisitiza wazo hili moja.