Jakimi metodami radzisz sobie z kolizjami w tablicach haszujących?

W tablicach haszujących do obsługi kolizji zwykle stosuje się dwie główne metody:

1. Łańcuchowanie (Chaining) — w przypadku kolizji wszystkie elementy z tym samym hashem są przechowywane w liście powiązanej lub innym kontenerze w jednej komórce tablicy. Podczas wyszukiwania lub wstawiania przeszukuje się tę listę.

2. Otwarte adresowanie (Open Addressing) — w przypadku kolizji szuka się następnej wolnej komórki według określonej sekwencji (liniowe próbkowanie, kwadratowe próbkowanie, podwójne haszowanie).

W Go standardowa implementacja mapy używa metody łańcuchowania z optymalizacjami. Na przykład, w przypadku kolizji, elementy są przechowywane w listach powiązanych wewnątrz kubełków.

Przykład łańcuchowania (uproszczony):

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

// Wstawianie z łańcuchowaniem
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
}

Tak więc obsługa kolizji to sposób na zachowanie poprawności i wydajności działania tablicy haszującej w przypadku kolizji hashy.