Welke methoden gebruik je om botsingen in hash-tabellen af te handelen?

In hash-tabellen worden meestal twee hoofdmethoden gebruikt om botsingen af te handelen:

1. Chaining (Kettingvorming) — bij een botsing worden alle elementen met dezelfde hash opgeslagen in een gekoppelde lijst of een andere container in één cel van de array. Bij zoeken of invoegen wordt deze lijst doorlopen.

2. Open Adressering — bij een botsing wordt de volgende vrije cel gezocht volgens een bepaalde sequentie (lineair zoeken, kwadratisch zoeken, dubbele hashing).

In Go gebruikt de standaard implementatie van map de chaining-methode met optimalisaties. Bijvoorbeeld, bij een botsing worden de elementen opgeslagen in gekoppelde lijsten binnen de buckets.

Voorbeeld van chaining (vereenvoudigd):

// Structuur voor een element
type entry struct {
    key string
    value int
    next *entry
}

// Invoegen met chaining
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
}

Dus, het afhandelen van botsingen is een manier om de correctheid en efficiëntie van de hash-tabel te behouden bij gelijke hash-waarden.