Hash

• Szerző: Sallai András
• Copyright © 2014, Sallai András
• Licenc: CC BY-SA 4.0
• Web: https://szit.hu

A hash jelentése zagyvalék, vagdalék, de elegánsabban úgy szoktuk fordítani az informatikában, hogy hasítás. Esetünkben természetesen adatok hasításáról van szó. Az informatikában a hasítást mindig egy függvénnyel végezzük, így ezen túl hasítófüggvényekről beszélünk.

Az informatika két területén is használjuk a hasítófüggvényeket. Az egyik biztonság, a másik az adattárolás területe. Az adattárolás területén már az 1950-es évek elejétől ismerős ez a fogalom. A biztonság területén csak 1980-as évek végétől használjuk.

Ha általánosítjuk a hasítást, az életben is találhatunk hasonló jelenséget. Ha például informatikai könyveket keresek egy könyvtárban, akkor egyenest az informatikai polcokhoz megyek, és nem nézem egyenként végig az összes polc, összes könyvét, mert tudom hol kell keresni.

A számítógép memóriájában is ehhez hasonlóan szeretnénk adatokat tárolni. Ha keresünk egy adatot ne kelljen végig menni az összes adaton. A hasítótáblák hatékonysága O(1). Vagyis az adatok számának növekedése nem jár több művelettel. Összehasonlítva a láncolt lista O(n), a bináris keresőfák O(log n) hatékonyságúak.

A hasítófüggvényeknek nagy hasznát vesszük szótárak megvalósításánál, ahol alapvetően három művelet van, új elem hozzáadása, keresés és törlés.

A hasító függvények egy értékből egy hasítóértéket állítanak elő. A hasító érték megmutatja az érték helyét a hasítótáblában.

Legyen például néhány főnév, amit szeretnénk tárolni és amelyben szeretnénk keresni. Az egyszerűség kedvéért most ezek csak az angol ábécé betűit tartalmazzák.

• hal
• kutya
• ablak
• akta
• atka
• akna
• ajak
• kaja
• alga
• talaj

Számozzuk meg az ábécé betűit:

Vegyünk egy nagyon nagyon egyszerű hasító függvényt. Egy szó kulcsának meghatározásához adjuk össze a hozzátartozó számokat.

A hal szó kulcsa például:

8 + 1 + 12 = 21

A kutya ugyanezt az algoritmust követve:

11 + 21 + 20 + 25 + 1 = 68

Az ablak szó kulcsa:

1 + 2 + 12 + 1 + 11 = 25

A hasítófüggvényünk úgy tűnik kielégítően működik, a sok üres hely azonban szembetűnő.

Jó lenne ha szűkíteni tudnánk a kulcsok tartományát. Ezt egy maradékképzéses osztással megtehetjük. Az összeadás végét osszuk el az elemek számával.

A hal szó kulcsa:

8 + 1 + 12 = 21
21 % 10 = 1

A kutya szó kulcsa:

11 + 21 + 20 + 25 + 1 = 78
78 % 10 = 8

Az ablak szó kulcsa:

1 + 2 + 12 + 1 + 11 = 27
27 % 10 = 7

Az atka és kaja eredménye viszont megegyezik. Az összeadás eredménye ugyan különböző, de 10-zel osztva mindkét esetben 3-t kapunk:

kaja:

11 + 1 + 10 + 1 =23
23 % 10 = 3

atka:

1 + 20 + 11 + 1 = 33
33 % 10 = 3

Ezért célszerűbb címterületet 10-ről valamelyik közeli prímszámra változtatni. Legyen 13. Az osztás újra elvégezve a 13-as értékkel a következő helyeket kapjuk:

A következő problémát az anagrammák okozzák. Vegyük az akta szót. A maradékos osztás mellett ütközést kapunk. Az ütközés oka, hogy a betűk egyeznek, csak más a sorrendjük. Az eddigi algoritmusunk nem veszi figyelembe a sorrendet.

akta:

1 + 11 + 20 + 1 = 23
23 % 13 = 10

atka:

1 + 20 + 11 + 1 = 23
23 % 13 = 10

Mindkettő kulcsa egyezik.

A Java nyelv java.lang.String osztályának hashCode() metódusa 31-gyel való szorzással oldja meg problémát. Minden elemhez, csak úgy adjuk a következő értéket, hogy előtte megszorozzuk 31-gyel.

Legyen címtér 43. Ekkor 43-mal kell maradékos osztást végezni.

hal:

(8 * 31 + 1) * 31 + 12 = 7731
7731 % 43 = 13

kutya:

(((11 * 31 + 21) * 31 + 20) * 31 + 25) * 31 + 1 = 10804338
10804338 % 43 = 29

ablak:

((1 * 31 + 12) * 31 + 1) * 31 + 11 = 994677
994677 % 43 = 1

akta:

((1 * 31 + 11) * 31 + 20) * 31 + 1 = 40983
40983 % 43 = 4

atka:

((1 * 31 + 20) * 31 + 11) * 31 + 1 = 49353
49353 % 43 = 32

Ezzel az 5 szóval persze a 11 prímszám is megfelelne, de a többi 5 esetén már ismétlődést tapasztalnánk.

A táblázat kihasználtsága nagyon rossz. A tábla mérete 43 és 10 értéket tárolunk benne.

(10 / 43) * 100 = 23 %

Megkeressük a következő szabad helyet. A következő szó az akna. Az akna a 9-es számot generálja, mint a hal szó. Az akna szó számára megkeressük a következő szabad helyet, ami a 10:

A 9-es index után a 10-es szabad.

A következő szó a kaja. A kaja ütközik az atka szóval. Mindkettő a 7-es helyen lenne. A kaja számára megkeressük a következő szabad helyet. A táblázat végéig nincs üres hely. A táblázat elejéről kezdem a keresést.

Az első hely szabad, ezért ott elhelyeztük.

Ez már működik. A hatékonyság a O(1) viszont tart a O(n)-be.

Ha ütközés van, egyszerűen hozzáfűzöm a már meglévő adathoz az újabbat. A technikát láncolásnak vagy vödörmódszernek is hívják, mivel egymás után láncoljuk az értékeket, illetve vödrökbe rakjuk azokat.