ਹੈਸ਼ ਮੈਪ ਐਲਗੋਰਿਦਮ ਨੂੰ ਕਿਵੇਂ ਅਨੁਕੂਲ ਬਣਾਉਂਦੇ ਹਨ?

Question

Accepted Answer

ਇੱਕ **hash map** (ਸ਼ਬਦ-ਕੋਸ਼) **O(1) ਔਸਤ** ਲੁਕਅਪ, ਪ੍ਰਵੇਸ਼ ਅਤੇ ਮਿਟਾਉਣਾ ਦਿੰਦਾ ਹੈ। O(n) ਮੈਮੋਰੀ ਦੇ ਨਿਵੇਸ਼ ਨੂੰ ਗਤੀ ਲਈ ਬਦਲ ਕੇ, ਬਹੁਤ ਸਾਰੇ O(n²) ਐਲਗੋਰਿਦਮ ਨੂੰ O(n) ਵਿੱਚ ਤਬਦੀਲ ਕਰਿਆ ਜਾ ਸਕਦਾ ਹੈ, ਦੁਹਰਾਏ ਗਏ ਸਕੈਨ ਨੂੰ ਤਾਤਕਾਲਿਕ ਲੁਕਅਪ ਨਾਲ ਬਦਲ ਕੇ।

## ਵਿਚਾਰ

ਹਰ ਵਾਰ ਸੂਚੀ ਦੀ ਖੋਜ ਕਰਨ ਦੀ ਬਜਾਏ, ਹੈਸ਼ ਮੈਪ ਵਿੱਚ ਦੇਖੀ ਗਈ ਮੁੱਲਾਂ ਨੂੰ ਸਟੋਰ ਕਰੋ ਅਤੇ ਸਧਾਰਨ ਸਮੇਂ ਵਿੱਚ ਰਾਖਵੀ ਰਾਜ ਦੀ ਜਾਂਚ ਕਰੋ।

## ਉਦਾਹਰਨ: 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²) ਹੈ; ਇਸ ਦੇ ਨਾਲ, ਇੱਕ ਪਾਸ।

## ਆਮ ਵਰਤੋਂ

- **ਡਿਡੁਪਲੀਕੇਸ਼ਨ / ਰਾਖਵੀ ਰਾਜ** ਸੈਟ ਦੇ ਨਾਲ।
- **ਫ੍ਰੀਕੁਇੰਸੀ ਗਿਣਨਾ** (`Counter`)।
- **ਗਰੁਪਿੰਗ / ਇੰਡੈਕਸਿੰਗ** ਕੁੰਜੀ ਦੁਆਰਾ।
- **ਕੈਸ਼ਿੰਗ / ਮੇਮੋਇਜ਼ੇਸ਼ਨ** ਨਤੀਜਿਆਂ ਦਾ।

## ਜਟਿਲਤਾ

- **ਔਸਤ:** O(1) ਪ੍ਰਤੀ ਕਾਰਜ। **ਬਦਤਰ:** ਭਾਰੀ ਟਕਰਾਵ ਪਰ O(n)। **ਸਥਾਨ:** O(n)।

## ਨੁਕਸਾਨ

ਕੁੰਜੀਆਂ **hashable** ਅਤੇ ਤਬਦੀਲੀ ਹਨ। ਬਦਤਰ-ਕੇਸ ਟਕਰਾਵ ਕਾਰਜ ਸਮਾਪਤੀ ਨੂੰ ਨੁਕਸਾਨ ਪਹੁੰਚਾਉਂਦਾ ਹੈ। ਹੈਸ਼ ਮੈਪ ਅਨੁਕ੍ਰਮਿਤ ਹਨ (ਜੇ ਕ੍ਰਮ ਮਾਹਿਰ ਹੈ ਤਾਂ ਪ੍ਰਬੰਧਿਤ ਵੇਰੀਅੰਟ ਦੀ ਵਰਤੋਂ ਕਰੋ)।

## ਕਿਉਂ ਇਹ ਮਾਹਿਰ ਹੈ

Hashing ਕੋਡਿੰਗ ਇੰਟਰਵਿਊ ਅਤੇ ਅਸਲ ਸਿਸਟਮ ਵਿਚ ਸਭ ਤੋਂ ਆਮ ਨਿਯੰਤਰਕ ਸੋਧ ਹੈ - ਇਹ