Jakými metodami řešíš kolize v hash tabulkách?

V hash tabulkách se pro řešení kolizí obvykle používají dvě hlavní metody:

1. Řetězení (Chaining) — při kolizi jsou všechny prvky se stejným hashem uloženy v propojeném seznamu nebo jiném kontejneru ve stejné buňce pole. Při hledání nebo vkládání se tento seznam prochází.

2. Otevřené adresování (Open Addressing) — při kolizi se hledá následující volná buňka podle určité sekvence (lineární sondování, kvadratické sondování, dvojité hashování).

V Go standardní implementace mapy používá metodu řetězení s optimalizacemi. Například při kolizi jsou prvky uloženy v propojených seznamech uvnitř bucketů.

Příklad řetězení (zjednodušený):

// Struktura pro prvek
type entry struct {
    key string
    value int
    next *entry
}

// Vložení s řetězením
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
}

Tímto způsobem je řešení kolizí způsob, jak zachovat správnost a efektivitu práce hashové tabulky při shodných hashech.