Môžete vysvetliť princíp metódy dvojitého hashovania na riešenie kolízií v hash tabuľkách?

Metóda dvojitého hashovania je spôsob riešenia kolízií v hash tabuľkách, pri ktorom sa pri kolízii vypočíta druhý hash a nasledujúci index na vyhľadanie prvku je určený pomocou tohto druhého hash.

Myšlienka:

• Existujú dve hashovacie funkcie: h1(key) a h2(key).

• Pri vkladaní alebo hľadaní prvku sa najskôr vypočíta h1(key) — počiatočný index.

• Ak je pozícia obsadená (kolízia), nasledujúci index sa vypočíta podľa vzorca:

  index = (h1(key) + i * h2(key)) mod veľkosť_tabuľky, kde i je číslo pokusu (0,1,2,...)

Toto umožňuje vyhnúť sa kolíziám pohybom v tabuľke s krokom závislým od kľúča, čím sa znižuje klastrovanie v porovnaní s lineárnym sondovaním.

Príklad v Go:

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

Tu h2 je vždy nenulové a zabezpečuje, že prejdeme celú tabuľu, ak je to potrebné.