Kas yra žemės sugretinimo kolizija ir kokie metodai jos sprendimui yra?

Hash'o kolizija įvyksta, kai du skirtingi įvesties reikšmės duoda tą pačią hash funkcijos reikšmę. Tai neišvengiama, nes galimų įvesties reikšmių rinkinys paprastai yra didesnis nei galimų hash reikšmių rinkinys.

Kolizijų sprendimo būdai:

1. Atvira adresacija — kolizijos atveju ieškoma kitos laisvosios ląstelės pagal tam tikrą seką (linijinis, kvadratinis, dvigubas hashavimas).
2. Grandinimas (chaining) — kiekvienoje hash lentelės ląstelėje saugomas susietas sąrašas visų elementų su ta pačia hash reikšme.
3. Perhashavimas — kolizijos atveju taikoma kita hash funkcija.

Pavyzdys su grandinimu Python:

hash_lentelė = [[] for _ in range(10)]

def įterpti(raktas, reikšmė):
    indeksas = hash(raktas) % 10
    hash_lentelė[indeksas].append((raktas, reikšmė))

įterpti('obuolys', 1)
įterpti('pmo', 2)  # galimas kolizija