რა არის ჰეშის კოლიზია და რა მეთოდები არსებობს მის გადაჭრისთვის?

ჰეშის კონფლიქტი წარმოიქმნება, როდესაც ორი სხვადასხვა შესვლის მნიშვნელობა იძლევა ერთსა და იმავე ჰეშ-ფუნქციის მნიშვნელობას. ეს შეუქცევადია, რადგან შესაძლო შესვლების რაოდენობა ჩვეულებრივ დიდია შესაძლო ჰეშ-შედეგების რაოდენობისგან.

კონფლიქტების გადაჭრის მეთოდები:

1. გახსნილი მისამართი — კონფლიქტის დროს, ეძებს შემდეგ თავისუფალ უჯრას განსაზღვრულ სერიაში (გრძივი, კვადრატული, ორმაგი ჰეშირება).
2. ჩეინინგი — თითოეულ ჰეშ-ცხრილში ინახება დაკავშირებული სია ყველა იმ ელემენტის შესახებ, რომლებიც ერთსა და იმავე ჰეშ-შედეგს იძლევიან.
3. ახალი ჰეშირება — კონფლიქტის დროს გამოიყენება სხვა ჰეშ-ფუნქცია.

Python-ში ჩეინინგის მაგალითი:

ჰეშ_ცხრილი = [[] for _ in range(10)]

def ჩაამატე(საკლიტი, მნიშვნელობა):
    ინდექსი = hash(საკლიტი) % 10
    ჰეშ_ცხრილი[indeksi].append((საკლიტი, მნიშვნელობა))

ჩაამატე('ვაშლი', 1)
ჩაამატე('პამ', 2)  # შესაძლო კონფლიქტი