8.2. Hasító függvény

A kulcsok között gyakran viszonylag nagy számok is előfordulhatnak, de a dinamikus halmaz mérete kicsi (azaz kevés adatot tartalmaz). Ekkor a közvetlen címzés nem gazdaságos, vagy esetleg el sem fér a megfelelő tömb a memóriában. A megoldás ekkor az lehet, hogy a kulcsok értékéből egy hasító függvény segítségével 0,. . . , m − 1 intervallumba eső számokat kapunk. A függvény több kulcshoz is ugyanazt a számot rendeli, ezt ütközésnek nevezzük. A hasító függvények „cseles" megválasztásával az ütközések esélye csökkenthető, de ki nem zárható. Az ütközések kezelésének egyik módszere, hogy az azonos függvényértékű adatokat egy láncolt listára fűzzük (8.2.1. ábra). A megfelelő függvények vázlata a következő:

LÁNCOLT-HASÍTÓ-BESZÚRÁS(T,x)

beszúrás a T[h(x.kulcs)] lista elejére

LÁNCOLT-HASÍTÓ-KERESÉS(T,k)

keresés a T[h(k)] listában

LÁNCOLT-HASÍTÓ-TÖRLÉS(T,x)

törlés a T[h(x.kulcs)] listából

8.2. ábra - 8.2.1. ábra. Ütközések kezelése láncolt listával

8.2.1. ábra. Ütközések kezelése láncolt listával