HASH TÁBLÁZATOK
1. BEMUTATKOZÁS.
A kereséshez képest az előzőektől gyökeresen eltérő megközelítés a folytatásból áll, nem a kulcsértékek összehasonlításával, hanem valamilyen h (k) függvény megkeresésével, amely közvetlenül megadja a k kulcs helyét a táblázatban.
Az első kérdés, amelyet feltehetünk magunknak, hogy könnyű-e ilyen h funkciókat találni. A válasz elvileg meglehetősen pesszimista, mivel ha ideális helyzetnek vesszük, hogy egy ilyen függvény mindig különböző helyeket ad meg különböző kulcsoknak, és például egy 40-es méretű táblára gondolunk, ahol 30 kulcsot akarunk címezni, azt találjuk, hogy a táblázatban 40 30 = 1,15 * 10 48 lehetséges kulcstartó funkció van, és csak 40 * 39 * 11 = 40!/10! = 2,25 * 10 41 közülük nem generál ismétlődő helyeket. Más szavakkal, a 10 millió ilyen funkció közül csak 2 lenne „tökéletes” céljainkra. Ez a feladat csak abban az esetben valósítható meg, ha a hash-táblához tartozó értékek eleve ismertek. Vannak olyan algoritmusok, amelyek tökéletes hash függvényeket hoznak létre, amelyek a kulcsszavak rendszerezésében szolgálnak a fordítóban, így a kulcsszavak bármelyikének keresése állandó időben történik.
Az ismétlődő értékeket elkerülő funkciókat meglepően nehéz megtalálni, még a kis táblák esetében is. Például a híres "születésnapi paradoxon" biztosítja, hogy ha 23 vagy több ember van jelen egy értekezleten, jó eséllyel kettőjük ugyanazon a hónap ugyanazon a napján született. Más szavakkal, ha kiválasztunk egy véletlenszerű függvényt, amely 23 kulcsot alkalmaz egy 365 méretű táblához, annak valószínűsége, hogy két kulcs nem esik ugyanarra a helyre, csak 0,4927.
Következésképpen a h (k) alkalmazásoknak, amelyeket ezentúl hash függvényeknek hívunk, megvan az a sajátosságuk, hogy számíthatunk arra, hogy h (k i) = h (k j) jó néhány különböző pár esetén (k i, k j). A cél tehát egy olyan hash függvény megtalálása, amely a lehető legkevesebb ütközést okozza (szinonimák előfordulása), bár ez csak a probléma egyik aspektusa, a másik az ütközés feloldási módszerek megtervezése, amikor azok bekövetkeznek.
2. HASH FUNKCIÓK.
Az első probléma, amellyel foglalkoznunk kell, az a hash függvény kiszámítása, amely a kulcsokat táblázat helyekké alakítja. Pontosabban szükségünk van egy olyan függvényre, amely a kulcsokat (általában egész számokat vagy karakterláncokat) átalakítja egész számokká egy tartományban [0.M-1], ahol M az a regiszterek száma, amelyeket a rendelkezésre álló memóriával kezelhetünk. a funkció kiválasztásakor h (k) Úgy tervezték, hogy minimalizálják az ütközéseket, és hogy viszonylag gyorsan és könnyen kiszámíthatók legyenek, bár az ideális helyzet egy funkció megtalálása lenne h amely véletlenszerű értékeket generál egységesen az [0.M-1] intervallum alatt. A látni kívánt két megközelítés erre a célra irányul, és mindkettő véletlenszám-generátorokon alapul.
Multiplikatív üldözés.
Ez a technika a kulcs szorzásával működik k önmagában vagy konstanssal, majd a termékbitek egy részét hash-tábla helyeként használja.
Amikor a választás a szorzás k Önmagában és a középső bitek egy részének megtartásával a módszert átlag négyzetnek nevezzük. Ez a módszer még mindig egyszerű és megfelel annak a kritériumnak, hogy a hely megjelölésére kiválasztott bitek az összes eredeti bit függvényei k, Legfőbb hátrányai, hogy a sok nullával rendelkező kulcsok a hash értékekben is tükröződnek, sok nullával is, és hogy a táblázat mérete 2-es hatványra korlátozódik.
Egy másik multiplikatív módszer, amely elkerüli a korábbi korlátozásokat, h (k) = Int [M * Frac (C * k)] kiszámításából áll, ahol M a táblázat mérete és 0
Osztás általi üldözés.
Ebben az esetben a függvény egyszerűen kiszámításra kerül h (k) = k mod M 0-t használva az M méretű hash-tábla első indexeként.
Bár a képlet bármilyen méretű táblákra alkalmazható, fontos, hogy gondosan megválasszuk az M értékét. Például, ha M páros lenne, akkor az összes páros (páratlan ill.) Kulcs páros helyekre vonatkozna (páratlan ill.), Ami nagyon erős torzítást jelentene. Az M kiválasztásának egyszerű szabálya, hogy prímszámnak vesszük. Mindenesetre vannak kifinomultabb szabályok az M megválasztására (lásd Knuth), amelyek mind a véletlenszámok előállításának kongruens módszerének működésével kapcsolatos elméleti tanulmányokon alapulnak.
3. AZ OSZTÁLYOK MEGOLDÁSA.
A hasingban tanulmányozandó második fontos szempont a szinonimák közötti ütközések feloldása. Az ütközések feloldásának három alapvető módszerét tanulmányozzuk, az egyik a szinonimák összekapcsolt listáinak vezetésétől függ, a másik kettő pedig a hash-táblázatban található helyek sorozatának kiszámításától, amíg meg nem jelenik egy üres. A módszerek összehasonlító elemzését a vizsgálandó helyek számának tanulmányozása alapján végzik, amíg meg nem határozják, hogy az egyes új kulcsokat hová tegyék a táblázatba.
Az összes példa esetében a táblázat mérete M = 13 lesz, és a h 1 (k) hash függvény, amelyet használni fogunk:
HASH = Mod M kulcs
és a k kulcs értékei, amelyeket figyelembe veszünk, a következő táblázatban láthatók:
Feltételezve, hogy k = 0 nem fordul elő természetesen, a táblázat összes helyét eleinte üresen jelölhetjük meg, megadva nekik a 0 értéket. Végül és mivel a keresési és beillesztési műveletek szorosan kapcsolódnak egymáshoz, algoritmusok kerülnek bemutatásra egy elem keresésére ha szükséges (kivéve, ha ez a művelet a táblázat túlcsordulását idézi elő), az elem helyét, vagy -1 (NULL) értéket adja vissza túlcsordulás esetén.
Külön láncolás vagy nyílt üldözés.
Az ütközés megoldásának legegyszerűbb módja, ha a táblázat minden helyéhez összeállít egy összekapcsolt listát azokról a rekordokról, amelyek kulcsai ebbe az irányba esnek. Ez a módszer általánosan ismert külön láncolás és nyilvánvalóan a kereséshez szükséges idő a listák hosszától és a bennük levő kulcsok relatív helyzetétől függ. Vannak változatok a szinonim listák karbantartásától függően (FIFO, LIFO, Key érték szerint stb.), Bár a legtöbb esetben, és mivel az egyes listáknak nem kell túl nagynak lenniük, általában a a legegyszerűbb alternatíva, a LIFO.
Mindenesetre, ha a listákat rendben tartják, ez a szekvenciális keresési módszer általánosításának tekinthető a listákban. A különbség az, hogy ahelyett, hogy egyetlen listát kellene tartani egyetlen fejléccsomóval, az M fejléc-csomópontokkal rendelkező M-listákat úgy tartják fenn, hogy a szekvenciális keresés összehasonlításainak számát átlagosan M faktorral csökkentik extra hely az M mutatók számára. Példánkban és a LIFO alternatívájával a táblázat az alábbi ábrán látható:
Néha és ha a táblázatba való bejegyzések száma viszonylag mérsékelt, akkor nem kényelmes a hash tábla bejegyzéseinek a listafejlécek szerepét adni, ami egy másik láncolási módszerhez vezetne, belső láncolás. Ebben az esetben a szinonimák közötti egyesülés magában a hash táblában található, olyan kurzor mezők (mutatók) segítségével, amelyek -1-re (NULL) vannak inicializálva, és amelyek a megfelelő szinonimáikra mutatnak.