Hasítófüggvény

A hasítófüggvények informatikában használt speciális eljárások a kereső algoritmusoknál használt indexstruktúrák, hasítótáblák felépítésére. Ezeket a hasítótáblákat nagy méretű adatállományok adatelemeinek gyors, hatékony megkeresésére használják. A hasítótáblák a bináris fastruktúrák és a láncolt listák mellett a leggyakrabban használt indexstruktúrák a modern kereső alkalmazásokban. Alkalmazásuk esetén gyakran használják a hesselés (hashing) kifejezést, ami gyakran félreértésekhez vezet, mivel a magyar nyelvben ugyanez a kifejezés használatos a kriptográfiai hash függvény, illetve más hashfüggvények, mint például érzékelési hashfüggvények használatakor is.

Az eljárás

Az informatika mindmáig legfontosabb kutatási területe minél jobb keresőalgoritmusok kidolgozása. Az már az 1950-es években világossá vált, hogy hagyományosan a nyers erőt használó szekvenciális kereső algoritmusok nem kellően hatékonyak.

A legtöbb kereső módszer egy adott K értéknek egy adattábla kulcsaival történő összehasonlításán alapul. A hasításos módszer egy harmadik lehetőség. Esetében egy a K értéken végzett aritmetikai művelet segítségével kiszámolunk egy f(K) függvényt, ez határozza meg a K érték helyét az adatállományban. Ezt a módszert nevezik a hasításos keresés módszerének. Sajnos ezeknek a függvényeknek a megtalálása nagyon nehéz, különösen ha azt is figyelembe vesszük, hogy lehetőség szerint az azonos érték hozzárendelését is el kell kerülni.

Ezért a f(K) függvények hasítóértékének keresése során fel kell adni az egyértelműség követelményét, azaz megengedhető több kiinduló értékhez ugyanaz az f(K) hasítóérték hozzárendelése. Ekkor viszont szükséges egy módszer az azonos hasítóértékű elemek megkülönböztetésére.

Források

• Knuth, Donald E.. Art of Computer Programing, Volume / 3 Sorting and Searching. Addison-Wesley, 513–558. o. (1997). ISBN 0-201-896850