हेश म्यापहरूले एल्गोरिदमहरूलाई कसरी अनुकूल बनाउँछन्?

Question

Accepted Answer

एक **hash map** (dictionary) ले **O(1) औसत** लुकअप, इन्सर्ट र डिलिट दिन्छ। O(n) मेमोरीको सट्टामा गति लिएर धेरै O(n²) एल्गोरिदमहरूलाई O(n) मा रूपान्तरण गर्न सकिन्छ, जसमा दोहोरिएको स्क्यानलाई तात्कालीन लुकअपले प्रतिस्थापन गर्छ।

## विचार

रेखा खोज्नुको सट्टा, हेश म्यापमा देखिएका मानहरू भण्डारण गर्नुहोस् र स्थिर समयमा सदस्यता जाँच गर्नुहोस्।

## उदाहरण: 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)
```

म्यापको बिना यो O(n²) हो; यससँग, एक पास।

## सामान्य प्रयोगहरू

- **निर्वचन / सदस्यता** सेटको साथ।
- **गणना आवृत्तिहरू** (`Counter`)।
- **समूहीकरण / अनुक्रमण** कुञ्जी द्वारा।
- **क्याचिङ / मेमोइजेशन** परिणामहरूको।

## जटिलता

- **औसत:** O(1) प्रति अपरेशन। **सबैभन्दा नराम्रो:** भारी टक्करहरूमा O(n)। **स्पेस:** O(n)।

## समस्याहरू

कुञ्जीहरू **hashable** र अपरिवर्तनीय हुनुपर्छ। सबैभन्दा नराम्रो टक्करहरूले कार्यक्षमता घटाउँछ। हेश म्यापहरू अनुक्रमित नहुन्छन् (यदि क्रम महत्त्वपूर्ण छ भने अनुक्रमित भेरिएन्टहरू प्रयोग गर्नुहोस्)।

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

हेसिङ कोडिङ साक्षात्कार र वास्तविक प्रणालीहरूमा सबैभन्दा सामान्य अनुकूलन हो — यसले "फेरि र फेरि खोज" लाई "एक पटक हेर" मा रूपान्तरण गर्छ।

स्पेस-समय व्यापार पुनरावृत्ति गरिने ईन्जिनियरिङ लीवर हो।

आवृत्ति गणना, क्याचिङ र अनुक्रमण सबै यस एक विचारमा निर्भर हुन्छ।