हेश टेबल भनेको के हो र यसले कसरी 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 मा collision हुन्छन्।

## ट्रेड-अफहरू

- **शक्तिहरू:** अत्यन्त छिटो key-आधारित पहुँच; लचकदार keys।
- **कमजोरीहरू:** keys को कुनै अर्डरिङ छैन; अतिरिक्त मेमोरी; O(n) सबैभन्दा खराब केस; राम्रो hash function चाहिन्छ।

## यो किन महत्त्वपूर्ण छ

हेश टेबलहरू व्यावहारिकमा सबैभन्दा अधिक प्रयुक्त संरचना हुन् — शब्दकोशहरू, सेटहरू, क्याशहरू, डेटाबेस अनुक्रमणिकाहरू, र डिडुप्लिकेशन पछाडि।

रैखिक स्क्यान लाई hash lookup को साथ बदलना एक O(n²) एल्गोरिदम लाई O(n) मा परिणत गर्ने सबैभन्दा सामान्य तरिकाहरू मध्ये एक हो।