Si hartëzat hash optimizojnë algoritmet?

Question

IT Interview Practice · Accepted Answer

Një **hartë hash** (fjalor) jep **O(1) mesatare** për kërkime, futje dhe fshirje. Zëvendësimi i O(n) kujtesës për shpejtësi e shndërron shumë algoritme O(n²) në O(n) duke zëvendësuar skanet e përsëritur me kërkime të çastit.

## Ideja bazë

Së vendi që të kërkosh një listë çdo herë, ruaj vlerat e parë në një hartë hash dhe kontrollo anëtarësinë në kohë konstante.

## Shembull: dy-shuma në 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)
```

Pa hartën ky është O(n²); me të, vetëm një kalim.

## Përdorime të zakonshme

- **Heqja e duplifikateve / anëtarësimi** me një grup.
- **Numërimi i frekuencave** (`Counter`).
- **Grupimi / indeksimi** sipas çelësit.
- **Memorizimi / ruajtja në kujtesë** e rezultateve.

## Kompleksiteti

- **Mesatare:** O(1) për operacion. **Më i keq:** O(n) në përplasje të rënda. **Hapësira:** O(n).

## Kurthe

Çelësat duhet të jenë **të hashuar** dhe të palëvizshëm. Përplasjet në rastin më të keq e degradojnë performancën. Hartëzat hash janë të parenditura (përdor variante të renditura nëse radha ka rëndësi).

## Pse ka rëndësi

Hashtabela është optimizimi më i zakonshëm në intervjuat e kodimit dhe në sistemet reale — ajo e shndërron "kërkimin përsëri dhe përsëri" në "këtë kërkimin një herë".

Trgimi i hapësirës për shpejtësi është një mekanizëm inxhinierik i përsëritur.

Numërimi i frekuencave, memorizimi dhe indeksimi të gjitha mbështeten në këtë një ide.

Ideja bazë

Shembull: dy-shuma në O(n)

Përdorime të zakonshme

Kompleksiteti

Kurthe

Pse ka rëndësi

Pyetje të ngjashme