Hash táblázat

A hash tábla  egy olyan adatstruktúra , amely megvalósítja az asszociatív tömb interfészt , azaz lehetővé teszi párok (kulcs, érték) tárolását és három művelet végrehajtását: egy új pár hozzáadásának műveletét, a keresési műveletet és a törlési műveletet. párosítás kulcsonként.

Bevezetés

A hash tábláknak két fő változata van: láncolt és nyílt címzés. A hash tábla tartalmaz néhány tömböt , amelynek elemei párok (nyitott cím hash tábla) vagy párok listája (láncolt hash tábla).

A művelet végrehajtása egy hash táblában a kulcs hash függvényének kiszámításával kezdődik. Az eredményül kapott hash érték indexként működik a tömbben . Ezután a végrehajtott művelet (hozzáadás, törlés vagy keresés) átirányításra kerül az objektumra, amely a tömb megfelelő cellájában van tárolva .

Ütközésnek nevezzük azt a helyzetet, amikor a különböző kulcsokhoz ugyanazt a hash értéket kapjuk . Az ilyen események nem olyan ritkák - például ha csak 23 elemet illesztünk be egy 365 cellás hash táblába, az ütközés valószínűsége már meghaladja az 50%-ot (ha minden elem azonos valószínűséggel bármelyik cellába eshet) - lásd a születésnapot paradoxon . Ezért az ütközés-feloldó mechanizmus minden hash-tábla fontos része.

Egyes speciális esetekben teljesen elkerülhető az ütközés. Például, ha az elemek összes kulcsa előre ismert (vagy nagyon ritkán változik), akkor számukra találhat valami tökéletes hash függvényt , amely ütközések nélkül elosztja azokat a hash tábla cellái között. Az ezeket a hash-függvényeket használó hash-táblázatoknak nincs szükségük ütközés-feloldó mechanizmusra, és ezeket közvetlen címkivonat-táblázatoknak nevezik .

A tárolt elemek számát osztva a tömb méretével (a lehetséges hash értékek számával) hash tábla terhelési tényezőnek nevezzük, és ez egy fontos paraméter, amely meghatározza a műveletek átlagos végrehajtási idejét.

Hash tábla tulajdonságai

A hash táblák fontos tulajdonsága, hogy bizonyos ésszerű feltételezések mellett mindhárom művelet (keresés, beillesztés, elemek törlése) átlagosan időben befejeződik . Ez azonban nem garantálja, hogy egyetlen művelet végrehajtási ideje kicsi. Ez annak a ténynek köszönhető, hogy a kitöltési tényező egy bizonyos értékének elérésekor újra kell építeni a hash tábla indexét: növelni kell a tömb méretét , és minden párt újra hozzáadni az üres hash táblához.

Ütközésfelbontás

Az ütközések megoldásának többféle módja van .

Láncmódszer

A H tömb minden cellája egy mutató az azonos kulcskivonat-értéknek megfelelő kulcs-érték párok összekapcsolt listájára (láncára). Az ütközések egyszerűen egy elemnél hosszabb láncokat eredményeznek.

Egy elem megkereséséhez vagy törléséhez meg kell keresni a megfelelő lánc összes elemét, hogy megtaláljuk az adott kulcsú elemet. Egy elem hozzáadásához hozzá kell adni egy elemet a megfelelő lista végéhez vagy elejéhez, és ha a kitöltési tényező túl nagy lesz, növelje meg a H tömb méretét, és építse újra a táblázatot.

Feltételezve, hogy minden elem azonos valószínűséggel eshet a H táblázat tetszőleges pozíciójába, függetlenül attól, hogy hova került a másik elem, az elemkeresési művelet átlagos ideje Θ (1 + α ), ahol α  a táblázat kitöltési tényezője.

Címzés megnyitása

A H tömb magát a kulcs-érték párokat tárolja. Az elembeillesztési algoritmus a H tömb celláit bizonyos sorrendben ellenőrzi, amíg meg nem találjuk az első szabad cellát, amelybe az új elemet írjuk. Ezt a sorrendet a rendszer menet közben számítja ki, így memóriát takarít meg a láncolt hash táblákban szükséges mutatók számára.

Azt a szekvenciát , amelyben a kivonattábla celláit kikeresi, próbasorozatnak nevezzük . Általános esetben csak az elemkulcstól függ, vagyis egy h 0 ( x ), h 1 ( x ), ..., h n  - 1 ( x ) sorozatról van szó, ahol x  az elemkulcs , és h i ( x ) - tetszőleges függvények, amelyek az egyes kulcsokat a hash tábla egy cellájára képezik le. A sorozat első eleme általában megegyezik a kulcsból származó hash függvény értékével, a többit pedig ebből számítják ki a következő módok egyikével. A keresési algoritmusok sikeres működéséhez a próbák sorrendjének olyannak kell lennie, hogy a hash tábla minden celláját pontosan egyszer vizsgálják meg.

A keresési algoritmus a hash tábla celláiban a beszúrással megegyező sorrendben keres, amíg vagy a kívánt kulcsú elemet vagy egy szabad cellát (ami azt jelenti, hogy nincs elem a hash táblában) nem talál.

Az elemek eltávolítása egy ilyen rendszerben kissé nehézkes. Általában ezt teszik: minden cellához beállítanak egy logikai jelzőt, jelezve, hogy egy elemet töröltek-e vagy sem. Ekkor egy elem eltávolítása abból áll, hogy beállítjuk ezt a jelzőt a hash tábla megfelelő cellájára, ugyanakkor módosítani kell egy meglévő elem keresési eljárását úgy, hogy az a törölt cellákat foglaltnak tekintse, és az eljárást hozzáadásához, így szabadnak tekinti őket, és visszaállítja a jelzőértéket, amikor hozzáadják őket.

Mintasorozatok

Az alábbiakban bemutatunk néhány gyakori mintasorozattípust. Rögtön megadjuk, hogy a hash tábla mintasorozatának és celláinak elemeinek számozása nullától legyen, N  pedig a hash tábla mérete (és ahogy fentebb megjegyeztük, a minták sorozatának hossza is).

• Lineáris próba : a hash tábla celláit szekvenciálisan pásztázzuk, valamilyen rögzített k intervallummal a cellák között (általában k = 1), azaz a vizsgáló sorozat i -edik eleme a (hash( x ) +  ik ) mod  N számú cella . Annak érdekében, hogy az összes cellát egyszer be lehessen vizsgálni, szükséges, hogy k a hash tábla méretével párhuzamos legyen.
• Kvadratikus szondázás : a cellák közötti intervallum minden lépéssel állandóval növekszik. Ha a hash tábla mérete kettő hatványa ( N = 2 p ), akkor egy példa egy olyan sorozatra, amelyben minden elemet egyszer megkeresünk: hash( x ) mod N , (hash( x ) + (1+1*1)/2) mod N , (hash( x ) + (2+2*2)/2) mod N , (hash( x ) + (3+3*3)/2) mod N , … háromszög számok .
• Dupla hash : a cellák közötti intervallum fix, mint a lineáris próbánál, de ettől eltérően az intervallum méretét a második, kiegészítő hash függvény számítja ki, ami azt jelenti, hogy a különböző kulcsoknál eltérő lehet. A hash függvény értékeinek nullától eltérőnek kell lenniük, és egy prímnek kell lenniük a hash tábla méretével, ami a legkönnyebben úgy érhető el, ha méretként prímszámot veszünk, és megkövetelik, hogy a hash segítő 1 és N közötti értékeket vegyen fel.  - 1.

Az alábbiakban látható a kettős kivonatolást bemutató kód: