Milyen módszereket használsz a hash-táblák ütközéseinek kezelésére?

Hash-táblákban a ütközések kezelésére általában két fő módszert alkalmaznak:

1. Láncolás (Chaining) — ütközés esetén minden azonos hash értékű elem egy láncolt listában vagy más tárolóban kerül tárolásra ugyanabban a tömbcellában. Keresés vagy beszúrás során ezt a listát végigjárják.

2. Nyitott címzés (Open Addressing) — ütközés esetén a következő szabad cellát keresi egy meghatározott sorrend szerint (lineáris próba, kvadratikus próba, dupla hash).

Go-ban az alapértelmezett map implementáció a láncolás módszerét használja optimalizációkkal. Például, ütközés esetén az elemek a bucket-okon belüli láncolt listákban tárolódnak.

Egyszerűsített láncolási példa:

// Elem struktúrája
type entry struct {
    key string
    value int
    next *entry
}

// Láncolással történő beszúrás
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
}

Így a kollíziók kezelése módja annak, hogy megőrizzük a hash-tábla helyességét és hatékonyságát, amikor azonos hash értékek ütköznek.