Hash to'qnashuvi nima va uni hal qilish uchun qanday usullar mavjud?

Hash to'qnashuvi, ikki turli kirish qiymatlari bir xil hash-funksiyasi qiymatini beradigan paytda yuzaga keladi. Bu qochib bo'lmaydi, chunki mumkin bo'lgan kirishlar to'plami odatda mumkin bo'lgan hash-qiymatlar to'plamidan kattaroq.

Qochib qolish usullari:

1. Ochiq manzilga joylash — qochib qolish holatida, belgilangan ketma-ketlik bo'yicha keyingi bo'sh hujayra qidiriladi (to'g'ri chiziqli, kvadratli, juft hashlash).
2. Zanjir (chaining) — har bir hash jadvalining hujayrasida, bir xil hash-qiymatga ega bo'lgan barcha elementlarning bog'langan ro'yxati saqlanadi.
3. Yangi hash qilish — qochib qolish holatida, boshqa hash-funksiyasi qo'llanadi.

Python'da zanjir misoli:

hash_jadvali = [[] for _ in range(10)]

def qo'shish(kalit, qiymat):
    indeks = hash(kalit) % 10
    hash_jadvali[indeks].append((kalit, qiymat))

qo'shish('olma', 1)
qo'shish('malo', 2)  # mumkin bo'lgan qochib qolish