hash table کیا ہے اور یہ O(1) lookup کو کیسے حاصل کرتا ہے؟

Question

Accepted Answer

ایک **hash table** (hash map) **key → value** جوڑوں کو محفوظ کرتا ہے اور **اوست O(1)** insert، lookup، اور delete فراہم کرتا ہے۔ یہ ہر key کو ایک **hash function** سے گزار کر کام کرتا ہے جو اسے ایک بنیادی array میں ایک index تک map کرتا ہے (ایک "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
```

## Complexity

| Operation | Average | Worst |
|---|---|---|
| insert | O(1) | O(n) |
| lookup | O(1) | O(n) |
| delete | O(1) | O(n) |

**worst case** O(n) تب ہوتا ہے جب بہت سی keys ایک ہی bucket میں collide کریں۔

## Trade-offs

- **Strengths:** بہت تیز key-based access؛ لچکدار keys۔
- **Weaknesses:** keys کی کوئی ترتیب نہیں؛ اضافی میموری؛ O(n) worst case؛ ایک اچھے hash function کی ضرورت ہے۔

## یہ کیوں اہم ہے

Hash tables عملی طور پر سب سے زیادہ استعمال ہونے والی ساخت ہیں — dictionaries، sets، caches، database indexes، اور deduplication کے پیچھے۔

ایک linear scan کو hash lookup سے بدلنا ایک O(n²) الگورتھم کو O(n) میں تبدیل کرنے کا سب سے عام طریقہ ہے۔