Hash-tábla

Hash-tábla
Típus	Tömb (adatszerkezet)
Komplexitás (O jelöléssel)
Tárigény	O(n)
Beszúrás	O(1)
Keresés	O(n)
Törlés	O(n)

A számítógép-tudományban a hash-tábla olyan adatszerkezet, amely hasítófüggvény segítségével állapítja meg, hogy melyik kulcshoz milyen érték tartozik – így implementál egy asszociatív tömböt. A hasítófüggvény segítségével a kulcsot leképezzük az adatokat tároló tömb egy adott indexére, ahol a keresett érték fellelhető.

Ideális esetben minden értelmezett kulcsra egyedi hash-t állít elő a hasítófüggvény, de ez a gyakorlatban ritkán valósítható meg – így számolnunk kell azzal, hogy két különböző kulcsra ugyanazt a hash-t kapjuk, és kezelnünk kell az ilyenkor fellépő hash-ütközést.

Sok esetben a hash-táblák teljesítménye számottevően jobb, mint a keresőfáké vagy egyéb táblás szerkezeteké, ezért széles körben használják asszociatív tömbök implementációjában, adatbázisok indexelésében, illetve a cache-memória felépítésében.

A hash-függvény

A tábla algoritmusának középpontjában egy tömb áll, amelyet a hash-táblának hívunk. A táblát egy függvény segítségével indexeljük.

index = f(kulcs, méret)

Az f függvény előállít egy indexet a [0, méret] tartományon, amelyet arra használunk, hogy a tömböt indexeljük.

Egy jó hash-függvény elengedhetetlen a hatékony implementációhoz. Alapvető követelmény a hash-függvénnyel szemben, hogy a lehetséges kulcsokra egyenletes eloszlású hasheket képezzen. Amennyiben nem egyenletes az eloszlás, az ütközések száma megnő, melyeknek a kezelése költséges. Nyílt címzésű hashelés alkalmazása esetén a függvényt úgy érdemes megszerkeszteni, hogy elkerüljük a tömörüléseket. A tömörülések a nyílt címzés tulajdonságaiból adódóan akár megtöbbszörözhetik a keresési időket. A kriptográfiában alkalmazott hashelő függvények gyakran egyenletes eloszlású hasheket állítanak elő tetszőleges méretű hash-táblához, de ezek ritkán alkalmasak egyszerű hash-táblák indexelésére a hashek előállításának költségéből adódóan.

Hash-ütközések

A gyakorlatban szinte elkerülhetetlen a hash-ütközés jelensége – a születésnap-paradoxon alapján egy hash-táblába már a mérethez viszonyítva alacsony számú beszúrás után magas a valószínűsége az ütközések előfordulásának. A paradoxon példáját felhasználva amennyiben egy 365 méretű hash-táblában az embereket a születésnapjuk alapján hasheljük, akkor már 23 beszúrás esetén 50%-os valószínűséggel jelentkezik hash-ütközés.

A hash-ütközéseket kezelő algoritmusok teljesítménye általában nem a táblában fellelhető elemek számától, hanem az összes rendelkezésre álló hely és az elemek által elfoglalt hely arányától függ, azaz a telítettségi tényezőtől. A telítettségi tényező adott esetben akár a 100%-ot is átlépheti, például láncolásos megoldás esetén.

A továbbiakban felsoroljuk a leggyakoribb módszereket a hash-ütközések kezelésére.

Láncolás

Láncolás alkalmazása esetén a hash-tábla egyes indexein nem egy elemet tárolunk, hanem azon kulcsok és értékek láncolt listáját, amelyeket a hash-függvény oda képzett le. Ekkor a táblában való kereséskor a hash-indexén levő listát kell bejárnunk a keresett adat kinyeréséhez. Beszúráskor a lista végéhez hozzáfűzzük az új értéket. Törléskor a megfelelő listaelemet távolítjuk el a láncolt listából.

A táblában végzett műveletek költsége ekkor a megfelelő indexen levő elemek bejárása. Így egy megfelelően egyenletes eloszlású hashelés esetén a műveletek költsége kizárólag a telítettségi tényező függvénye. A láncolás során a teljesítmény lineárisan csökken a telítettségi tényező növekedésével, így hatékonyabb egy azonos elemszámú láncolt listánál, vagy akár egy kiegyensúlyozott keresőfánál is.

A láncolás alkalmazásánál legrosszabb esetben az összes beszúrt elem ugyanarra az indexre kerül, ekkor minden művelet O(n) lépést igényel.

A láncolást teljesen véletlenszerű hozzáférés esetén gyakran kulcs szerint rendezett listákkal implementáljuk, ekkor felére csökken az átlagos keresési idő, hiszen amennyiben egyértelműen tudjuk rendezni a kulcsok halmazát, reprezentatív, véletlenszerű mintavételezés során átlagosan az elemek 50%-a nagyobb és 50%-a kisebb, mint a kiválasztott elem, azaz átlagosan elegendő a lista felét bejárnunk ahhoz, hogy megtaláljuk az elemet (vagy hogy megállapítsuk, hogy nincs a táblában). Amennyiben viszont egyes kulcsok gyakrabban fordulnak elő, mint mások, ideálisabb a listákat a hozzáférések száma alapján rendezni, azaz egy előremozgató becslést alkalmazni.

Hátrányai

A láncolással implementált hash-táblák a láncolt listák hátrányait is öröklik: a tárigény jelentősen megnő a listákban tárolandó O(n) mutató mérete miatt. A láncolt listáknak a cache teljesítménye is gyenge más adatszerkezetekhez képest, hiszen az egyes "láncszemek" tetszőleges helyen helyezkedhetnek el a memóriában, így egy k elemű listához O(k) lap betöltésére lehet szükség.

Egyes implementációkban a hash-táblában nem egy mutatót tárolunk a megfelelő láncolt listára, hanem annak a láncolt listának az első elemét, ezzel növelve a cache teljesítményt, illetve csökkentve a tárigényt.

Láncolás egyéb adatszerkezetekkel

Az egyes indexeken tárolt adatszerkezet tetszőlegesen megválasztható, amennyiben az támogatja a megfelelő műveletek. Például alkalmazhatunk egy önkiegyensúlyozó bináris keresőfát is, mellyel a tárigény nő, ellenben az egyes műveletek lépésszáma legrosszabb esetben O(n) helyett O(log n). Alkalmazhatunk dinamikus tömböket is, melyben a beszúrás lépésszáma amortizált O(1), a keresés és törlés pedig O(n). A dinamikus tömbökkel való megoldásnak lényegesen jobb a cache teljesítménye, mint a láncolt listás megoldásnak, de az optimális beszúrási teljesítmény eléréséhez a tárigénye is nagyobb.

Nyílt címzés

A nyílt címzésű hash-táblákban a láncolással ellentétben egy indexen kizárólag egy értéket tárolunk, azaz a táblában tárolt elemek száma nem haladhatja meg az indexek (egyedi hashek) számát. Beszúráskor a megadott módszerrel a kapott hashtől indulva megkeressük az első szabad indexet, ahova az elem bekerül. Kereséskor ugyanígy járjuk be az egyes indexeket, ekkor O(n) lépésben megállapíthatjuk, hogy a megadott kulcs szerepel-e a táblában. Törléskor az elem indexét nem üresnek, hanem töröltnek jelöljük, így azok a kereső algoritmusok, amelyek ellenőrzik ezt az indexet se adnak hibás eredményt, viszont egy olyan táblában, ahol gyakoriak a beszúrások és törlések a keresés teljesítménye gyorsabban romlik. Egy kulcs helyét az úgynevezett próbálás során keressük meg. Ennek több, ismert módszere létezik.

Lineáris próbálás

Lineáris próbálás esetén két kipróbált hely között a távolság konstans méretű, általában 1.

Általánosítva, amennyiben adott egy H(x,n) hashelő függvény, a H(x,i,n) lineáris próbafüggvény:

$\operatorname {H} (x,i,n)=\operatorname {H} (x,n)+i\ (\operatorname {mod} n)$

ahol x a kulcs, i a próbálás távolsága és n a tábla mérete.

Nem egyenletes eloszlású hashelés esetén a lineáris próbálás során a beszúrt értékek a hash-tábla egyes tartományain csoportosulnak, azaz gyakran egymás utáni indexeken fognak elhelyezkedni a beszúrt elemek.

Kvadratikus próbálás

Kvadratikus próbálás során a két kipróbált hely között a távolságot egy másodfokú polinom adja.

Amennyiben adott a H(x,n) hashelő függvény, az i. próbálás helyét adja a következő H(x,i,n) kvadratikus próbafüggvény:

$\operatorname {H} (x,i,n)=\operatorname {H} (x,n)+c_{1}i+c_{2}i^{2}\ (\operatorname {mod} n)$

ahol x a kulcs és n a tábla mérete. $c_{1}$ és $c_{2}$ a függvényre jellemző konstansok, amelyeknek az ideális értéke a tábla méretétől függ és egy adott táblára nem változik az értékük. Az együtthatók értéke akkor ideális, ha az összes i < n-re különböző indexet ad a függvény. Tetszőleges táblaméretre nehéz olyan kvadratikus próbát előállítani, amely garantálja, hogy minden beszúrás sikeres, amennyiben a telítettségi tényező meghaladja az 50%-ot. Ha $c_{2}=0$, az algoritmus egy lineáris próbálássá degradálódik.

Kettős hashelés

A kettős hashelés során a lépésköz a bemenő adat függvénye, ezzel csökkentve a csoportulások kialakulásának lehetőségét.

Amennyiben adott a H(x,n) hashelő függvény, az i. próbálás helyét adja a következő függvény:

$\operatorname {H} (x,i,n)=\operatorname {H} (x,n)+i\cdot \operatorname {H'} (x,n)\ (\operatorname {mod} n)$

ahol x a kulcs, n a tábla mérete és a H'(x,n) a másodlagos hashelő függvény. Fontos, hogy úgy válasszuk meg a másodlagos függvényt, hogy az semmilyen kulcsra ne adjon 0 értéket, hiszen ekkor a lépésköz minden i-re 0, azaz a táblának csupán egyetlen helyére próbáljuk meg beszúrni az elemet.

Dinamikus méretezés

A hash-táblák teljesítménye arányosan csökken a telítettségi tényező növekedésével. A telítettségi tényezőt fix méretű táblában nem tudjuk csökkenteni anélkül, hogy elemeket távolítanánk el belőle, így az egyetlen fennmaradó lehetőség a tábla méretének növelése. A tábla növelésével az egyes elemeknek az újrahashelésére van szükség, mivel azoknak a hash-e eltérhet az átméretezett tábla függvénye alapján.

Ha az átméretezés során a tábla mindig konstansszorosára nő, akkor az egyes táblaműveletek amortizált lépésszáma változatlan marad, illetve az átméretezés amortizált lépésszáma is O(1).