# Hash Map — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/hash-map

> Hash फ़ंक्शन और bucket के ज़रिए औसतन O(1) में key → value।

## Hash फिर bucket

Hash फ़ंक्शन key को array इंडेक्स में बदलता है। अलग keys एक ही bucket में टकरा सकती हैं; bucket के अंदर छोटी list (या tree) इसे सुलझाती है। अच्छे वितरण से `get`/`put`/`delete` औसत `O(1)`, worst `O(n)`।

## पहले अक्षर से पुस्तकालय

शीर्षक के पहले अक्षर से किताबें रखने पर आप सही शेल्फ़ पर तुरंत जा सकते हैं। यदि बहुत सारे शीर्षक 'S' से शुरू हों, वह शेल्फ़ धीमी — यही collision है।

## एक पास में Two Sum

चलते-चलते हर संख्या का इंडेक्स रखें; डालने से पहले पूरक जाँचें।

```python
def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        if target - n in seen:
            return [seen[target - n], i]
        seen[n] = i
    return []
```

Output:

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

**Quiz:** आपको key से तेज़ lookup चाहिए और क्रम की परवाह नहीं। चुनें...

- [ ] Sorted array + binary search
- [x] Hash map
- [ ] Linked list

*Answer:* Hash map. Hash map प्रति lookup औसत O(1); binary search O(log n) और sorting चाहिए।