hash table म्हणजे काय आणि ते O(1) lookup कसे साध्य करते?

Question

Accepted Answer

एक **hash table** (hash map) **key → value** जोड्या संचयित करतो आणि सरासरी **O(1)** insert, lookup, आणि delete प्रदान करतो. हे प्रत्येक key ला **hash function** द्वारे चालवून काम करते जो त्याला अंतर्निहित array ("bucket" म्हणून ओळखले जाते) मध्ये index ला मॅप करतो.

## ते कसे काम करते

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

## जटिलता

| ऑपरेशन | सरासरी | सर्वात वाईट |
|---|---|---|
| insert | O(1) | O(n) |
| lookup | O(1) | O(n) |
| delete | O(1) | O(n) |

**सर्वात वाईट परिस्थिती** O(n) तेव्हा होते जेव्हा अनेक keys एकाच bucket मध्ये टकराते.

## ट्रेड-ऑफ्स

- **शक्तिशाली बाजू:** अत्यंत वेगवान key-आधारित प्रवेश; लचकदार keys.
- **कमजोर बाजू:** keys चा कोणताही क्रम नाही; अतिरिक्त स्मृती; सर्वात वाईट परिस्थितीत O(n); एक चांगला hash function आवश्यक आहे.

## हे का महत्वाचे आहे

Hash table हे व्यवहारात कदाचित सर्वात वापरलेले संरचना आहे — शब्दकोश, sets, caches, database indexes, आणि deduplication मागे.

रेखीय scan ला hash lookup ने बदलणे O(n²) अल्गोरिदमला O(n) मध्ये बदलण्याचा सर्वात सामान्य मार्ग आहे.