హ్యాష్ టేబిల్ అంటే ఏమిటి మరియు ఇది O(1) శోధనను ఎలా సాధిస్తుంది?

Question

IT Interview Practice · Accepted Answer

ఎ **హ్యాష్ టేబిల్** (hash map) **key → value** జతలను నిల్వ చేస్తుంది మరియు సగటున **O(1)** చేర్చడం, శోధన మరియు తొలగించడం అందిస్తుంది. ఇది ప్రతి కీని ఒక **హ్యాష్ ఫంక్షన్** ద్వారా అమలు చేయడం ద్వారా పనిచేస్తుంది, ఇది దానిని అంతర్నిహిత శ్రేణిలో (ఒక "bucket") ఒక సూచికకు మ్యాప్ చేస్తుంది.

## ఇది ఎలా పనిచేస్తుంది

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

## ఉదాహరణ

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

## సంక్లిష్టత

| ఆపరేషన్ | సగటు | చెత్త |
|---|---|---|
| చేర్చడం | O(1) | O(n) |
| శోధన | O(1) | O(n) |
| తొలగించడం | O(1) | O(n) |

**చెత్త సందర్భం** O(n) అనేక కీలు ఒకే బకెట్‌లో ఢీకొట్టినప్పుడు జరుగుతుంది.

## ట్రేడ్-ఆఫ్‌లు

- **బలాలు:** చాలా వేగమైన కీ-ఆధారిత ప్రవేశం; నమ్యమైన కీలు.
- **బలహీనతలు:** కీల యొక్క కోఆర్డినేషన్ లేదు; అतిरिक్త మెమరీ; O(n) చెత్త సందర్భం; మంచి హ్యాష్ ఫంక్షన్ అవసరం.

## ఇది ఎందుకు ముఖ్యమైనది

హ్యాష్ టేబిల్‌లు ఆచరణలో సాధారణంగా సबसे ఎక్కువ ఉపయోగించిన నిర్మాణం — నిఘంటువులు, సెట్‌లు, కేష్‌లు, డేటాబేస్ ఇండెక్స్‌లు మరియు డిడూప్లికేషన్ వెనుక ఉన్నాయి.

రేఖీయ స్కాన్‌ను హ్యాష్ శోధనతో భర్తీ చేయడం O(n²) అల్గోరిథమ్‌ను O(n)కి మార్చడానికి సबচे సामాన్యమైన మార్గాలలో ఒకటి.

ఆపరేషన్	సగటు	చెత్త
చేర్చడం	O(1)	O(n)
శోధన	O(1)	O(n)
తొలగించడం	O(1)	O(n)

ఇది ఎలా పనిచేస్తుంది

ఉదాహరణ

సంక్లిష్టత

ట్రేడ్-ఆఫ్‌లు

ఇది ఎందుకు ముఖ్యమైనది

సంబంధిత ప్రశ్నలు