ہیش میپ الگورتھم کو کیسے بہتر بناتے ہیں؟

Question

Accepted Answer

ایک **hash map** (dictionary) **O(1) اوسط** lookups، inserts، اور deletes فراہم کرتا ہے۔ O(n) میموری کو رفتار کے لیے تبدیل کرنے سے بہت سے O(n²) الگورتھم O(n) میں بدل جاتے ہیں بار بار scanning کو فوری lookups سے بدل کر۔

## خیال

ہر بار list میں تلاش کرنے کی بجائے، دیکھے گئے values کو hash map میں store کریں اور مستقل وقت میں membership کو check کریں۔

## مثال: two-sum in O(n)

```python
def two_sum(nums, target):
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:               # O(1) lookup
            return (seen[need], i)
        seen[x] = i
    return None

two_sum([2, 7, 11, 15], 9)             # -> (0, 1)
```

بغیر map کے یہ O(n²) ہے؛ اس کے ساتھ، ایک pass۔

## عام استعمال

- **Deduplication / membership** set کے ساتھ۔
- **Counting frequencies** (`Counter`)۔
- **Grouping / indexing** key کے ذریعے۔
- **Caching / memoization** نتائج کا۔

## Complexity

- **اوسط:** O(1) فی operation۔ **بدترین:** O(n) بھاری collisions پر۔ **Space:** O(n)۔

## نقصانات

Keys **hashable** اور immutable ہونی چاہئیں۔ بدترین حالت میں collisions کارکردگی میں کمی کرتے ہیں۔ Hash maps unordered ہیں (اگر ترتیب اہم ہے تو ordered variants استعمال کریں)۔

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

Hashing coding interviews اور حقیقی systems میں سب سے عام optimization ہے — یہ "دوبارہ تلاش کریں" کو "ایک بار lookup کریں" میں تبدیل کرتا ہے۔

Space-for-time trade-off ایک بار بار آنے والا engineering lever ہے۔

Frequency counting، caching، اور indexing سب اسی ایک خیال پر منحصر ہیں۔