હેશ ટેબલ શું છે અને તે O(1) લુકઅપ કેવી રીતે હાંસલ કરે છે?

Question

Accepted Answer

**હેશ ટેબલ** (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
```

## જટિલતા

| Operation | સરેરાશ | સૌથી ખરાબ |
|---|---|---|
| insert | O(1) | O(n) |
| lookup | O(1) | O(n) |
| delete | O(1) | O(n) |

**સૌથી ખરાબ કેસ** O(n) ત્યારે થાય છે જ્યારે ઘણી બધી keys એક જ bucket માં collide થાય.

## Trade-offs

- **શક્તિઓ:** અત્યંત ઝડપી key-based access; લવચક keys.
- **નબળાઈઓ:** keys ની કોઈ ક્રમબદ્ધતા નથી; વધારાની મેમરી; O(n) સૌથી ખરાબ કેસ; સારા hash function ની જરૂર છે.

## શા માટે તે મહત્વપૂર્ણ છે

હેશ ટેબલ વ્યવહારમાં સૌથી વધુ ઉપયોગમાં લેવાતી structure છે — dictionaries, sets, caches, database indexes, અને deduplication પાછળ.

លીનિયર scan ને hash lookup સાથે બદલવું એ O(n²) algorithm ને O(n) માં ફેરવવાની સૌથી સામાન્ય રીતોમાંથી એક છે.