Mi az a hash ütközés és milyen módszerek léteznek a megoldására?

Hash ütközés akkor fordul elő, amikor két különböző bemeneti érték ugyanazt a hash-függvény értékét adja. Ez elkerülhetetlen, mivel a lehetséges bemenetek halmaza általában nagyobb, mint a lehetséges hash-értékek halmaza.

Az ütközések megoldására szolgáló módszerek:

1. Nyitott címzés — ütközés esetén a következő szabad cellát keressük egy meghatározott sorrendben (lineáris, kvadratikus, dupla hasholás).
2. Láncolás — minden hash-tábla cellában egy összekapcsolt lista tárolódik az összes ugyanazzal a hash-értékkel rendelkező elemről.
3. Újra hash-elés — ütközés esetén másik hash-függvényt alkalmazunk.

Python példával a láncolás:

hash_tábla = [[] for _ in range(10)]

def beszúr(kulcs, érték):
    index = hash(kulcs) % 10
    hash_tábla[index].append((kulcs, érték))

beszúr('alma', 1)
beszúr('pma', 2)  # lehetséges ütközés