როგორ ოპტიმიზირებს ჰეშ რუკა ალგორითმებს?

Question

Accepted Answer

**ჰეშ რუკა** (ლექსიკონი) იძლევა **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).

## პაგები

კლიდი უნდა იყოს **ჰეშირებადი** და უცვლელი. უარეს შემთხვევაში შეჯახებები ცუდავენ მუშაობას. ჰეშ რუკა არაწესრიგიანია (გამოიყენეთ წესრიგიანი ვარიანტი თუ წესრიგი მნიშვნელოვანია).

## რატომ მნიშვნელოვანია

ჰეშირება ერთი ყველაზე გავრცელებული ოპტიმიზაცია კოდირების ინტერვიუში და რეალურ სისტემებში — ის გარდაქმნის "ისევ და ისევ ძებნა" "ერთხელი გამოძიება" ში.

რეზურსი-დროის გაცვლა არის განმეორებული საინჟინრო ბერკეტი.

სიხშირის დათვლა, კეშირება და ინდექსირება ყველა ეს ერთი იდეაზე დაფუძნებული.