Hash maps algorithms को कैसे optimize करते हैं?

Question

Accepted Answer

एक **hash map** (dictionary) **औसतन O(1)** में lookups, inserts, और deletes देता है। O(n) memory को गति के बदले देकर, कई O(n²) algorithms O(n) बन जाते हैं, क्योंकि बार-बार के scans की जगह तुरंत lookups आ जाते हैं।

## मूल विचार

हर बार किसी list को खोजने के बजाय, देखे गए values को एक hash map में store करें और constant time में membership जाँचें।

## उदाहरण: O(n) में two-sum

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

## सामान्य उपयोग

- एक set के साथ **deduplication / membership**।
- **frequencies गिनना** (`Counter`)।
- key के अनुसार **grouping / indexing**।
- परिणामों की **caching / memoization**।

## Complexity

- **Average:** प्रति operation O(1)। **Worst:** भारी collisions पर O(n)। **Space:** O(n)।

## सावधानियाँ

Keys का **hashable** और immutable होना आवश्यक है। Worst-case collisions performance को घटा देते हैं। Hash maps unordered होते हैं (यदि क्रम मायने रखता है तो ordered variants का उपयोग करें)।

## यह क्यों महत्वपूर्ण है

Hashing, coding interviews और वास्तविक systems में सबसे आम optimization है — यह "बार-बार खोजने" को "एक बार look up करने" में बदल देता है।

Space-के-बदले-time का यह trade-off एक बार-बार काम आने वाला engineering साधन है।

Frequency counting, caching, और indexing — सभी इसी एक विचार पर टिके हैं।