હેશ મેપ અલ્ગોરિધમ્સને કેવી રીતે ઓપ્ટિમાઇজ કરે છે?

Question

Accepted Answer

એક **hash map** (dictionary) **O(1) સરેરાશ** લુકઅપ્સ, ઇનસર્ટ્સ અને ડિલીટ્સ આપે છે. O(n) મેમરીને સ્પીડ માટે ટ્રેડ કરવાથી ઘણા O(n²) અલ્ગોરિધમ્સને O(n) માં રૂપાંતરિત કરે છે, પુનરાવર્તિત સ્કેન્સને ત્વરિત લુકઅપ્સ સાથે બદલીને.

## આઇડિયા

પ્રત્યેક વખતે લિસ્ટ શોધવાને બદલે, જોયેલી વેલ્યુ્સને hash map માં સ્ટોર કરો અને સ્થિર સમયમાં મેમ્બરશિપ તપાસો.

## ઉદાહરણ: 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)
```

મેપ વિના આ O(n²) છે; તેના સાથે, એક પાસ.

## સામાન્ય ઉપયોગો

- **ડિડુપ્લિકેશન / મેમ્બરશિપ** એક set સાથે.
- **ફ્રીક્વેન્સી કાઉન્ટિંગ** (`Counter`).
- **ગ્રુપિંગ / ઇન્ડેક્સિંગ** કીની આધારે.
- **કેશિંગ / મેમોઇજેશન** પરિણામોનું.

## જટિલતા

- **સરેરાશ:** O(1) પ્રતિ ઓપરેશન. **સૌથી ખરાબ:** O(n) ભારે કોલિશનમાં. **સ્પેસ:** O(n).

## ખામીઓ

કીઓ **hashable** અને અપરિવર્તનશીલ હોવી આવશ્યક છે. સૌથી ખરાબ કોલિશનો પરફોર્મન્સ ખરાબ કરે છે. હેશ મેપ્સ અક્રમિત છે (જો ક્રમ મહત્વપૂર્ણ હોય તો ક્રમબદ્ધ વેરિયન્ટ્સ વાપરો).

## આ શા માટે મહત્વપૂર્ણ છે

હેશિંગ કોડિંગ ઇન્ટરવ્યુ અને વાસ્તવિક સિસ્ટમ્સમાં સૌથી સામાન્ય ઓપ્ટિમાઇજેશન છે — તે "ફરીથી અને ફરીથી શોધો" ને "તે એક વાર લુક કરો" માં રૂપાંતરિત કરે છે.

સ્પેસ-ફોર-ટાઇમ ટ્રેડ-ઓફ એક પુનરાવર્તિત ઇજનેરિંગ લીવર છે.

ફ્રીક્વેન્સી કાઉન્ટિંગ, કેશિંગ અને ઇન્ડેક્સિંગ બધા આ એક આઇડિયા પર આધારિત છે.