Хеш таблицаларында кагылышуларды чечүү үчүн эки жолу хештөө ыкмасының принципин түшүндүрө аласызбы?

Икки каттуу хештөө ыкмасы — бул хеш таблицаларында кагылышууларды чечүүнүн ыкмасы, анда кагылышуу пайда болгондо экинчи хеш эсептелет жана элементти издөө үчүн кийинки индекс ушул экинчи хеш аркылуу аныкталат.

Идея:

• Эки хеш функциясы бар: h1(key) жана h2(key).

• Элементти кошуу же издөөдө биринчи h1(key) — баштапкы индекс эсептелет.

• Эгер орун ээлүү (кагылышуу) болсо, кийинки индекс төмөнкү формула боюнча эсептелет:

  индекс = (h1(key) + i * h2(key)) mod таблица өлчөмү, анда i — аракеттердин саны (0,1,2,...)

Бул кагылышууларды болтурбоого мүмкүндүк берет, таблица боюнча кадамдап өтүү менен, алгачкы ачкычка көз каранды, бул линейдүү издөөгө караганда кластерлешүүнү азайтат.

Go тилинде мисал:

func doubleHashing(key int, i int, tableSize int) int {
    h1 := key % tableSize
    h2 := 1 + (key % (tableSize - 1))
    return (h1 + i*h2) % tableSize
}

Бул жерде h2 дайыма нөлгө барабар эмес жана керек болсо бүт таблицаны өтүп чыгууга кепилдик берет.