Хеш кагылышы деген эмне жана аны чечүү үчүн кандай ыкмалар бар?

Хэш кагылышуусу, эки башка кирүү маанилери бирдей хэш функциясынын маанисин бергенде пайда болот. Бул кагылышуу кыйынчылыксыз, анткени мүмкүн болгон кирүү маанилеринин топтому көбүнчө мүмкүн болгон хэш маанилеринин топтомуна караганда чоңураак.

Кагылышууларды чечүү ыкмалары:

1. Ачык дарекке жайгаштыруу — кагылышуу болгондо, белгиленген тартипте кийинки бош клетка издөө (сызыктуу, квадратик, эки жолу хэшдөө).
2. Занжирлөө (chaining) — ар бир хэш таблицасынын клеткасында, бирдей хэш мааниге ээ бардык элементтердин байланып турган тизмеси сакталат.
3. Жаңы хэшдөө — кагылышуу болгондо, башка хэш функциясы колдонулат.

Pythonдо занжирлөө мисалы:

хэш_таблица = [[] for _ in range(10)]

def кошуу(ключ, маан):
    индекс = hash(ключ) % 10
    хэш_таблица[индекс].append((ключ, маан))

кошуу('алма', 1)
кошуу('пам', 2)  # мүмкүн кагылышуу