Hasítófüggvény

A Wikipédiából, a szabad enciklopédiából
(Hasító függvény szócikkből átirányítva)

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 használatakor is.

Az eljárás[szerkesztés | forrásszöveg szerkesztése]

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 és 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. Viszont ekkor szükséges egy módszer az azonos hasító értékkel rendelkező elemek megkülönböztetésére.

Forrás[szerkesztés | forrásszöveg szerkesztése]