Akými metódami riešite kolízie v hash tabuľkách?

U hash tabelách sa zaobilaženjem kolizija obično se koriste dve glavne metode:

1. Lančano povezivanje (Chaining) — u slučaju kolizije, svi elementi sa istim hash-om se čuvaju u povezanoj listi ili drugom kontejneru u istoj ćeliji niza. Prilikom pretraživanja ili umetanja, prolazi se kroz ovu listu.

2. Otvoreno adresiranje (Open Addressing) — u slučaju kolizije, traži se sledeća slobodna ćelija prema određenoj sekvenci (linearno sondiranje, kvadratno sondiranje, dvostruko hashiranje).

U Go, standardna implementacija mape koristi metodu lančanog povezivanja sa optimizacijama. Na primer, u slučaju kolizije, elementi se čuvaju u povezanim listama unutar bucket-ova.

Primer lančanog povezivanja (pojednostavljeno):

// Struktura za element
type entry struct {
    key string
    value int
    next *entry
}

// Umetanje sa lančanim povezivanjem
func insert(table []*entry, key string, value int) {
    index := hash(key) % len(table)
    e := &entry{key: key, value: value, next: table[index]}
    table[index] = e
}

Tako, rešavanje kolizija je način da se održi tačnost i efikasnost rada hash tabele u slučaju istih hash vrednosti.