Felhasználói eszközök

Eszközök a webhelyen


oktatas:programozas:algoritmusok:hash

< Algoritmusok

Hash

  • Szerző: Sallai András
  • Copyright © Sallai András, 2014
  • Licenc: GNU Free Documentation License 1.3

A hasításról

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.

Közvetlen címzés

Hasítá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:

első rész
1 2 3 4 5 6 7 8 9 10 11 12 13
a b c d e f g h i j k l m
második rész
14 15 16 17 18 19 20 21 22 23 24 25 26
n o p q r s t u v w x y z

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 tömb jelenleg
0
1
2
3
4
5
6
...
20
21 hal
...
25 ablak
...
77
78 kutya

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

Tartomány szűkítése

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
a tömb jelenleg
0
1 hal
2
3
4
5
6
7 ablak
8 kutya
9
10

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 tömb jelenleg
0 kutya
1 ablak
2
3
4
5
6
7 atka
8 hal
9
10 kaja
11
12
13

Sorrend figyelembevétele

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.

(((a_0 * 31 + a_1) * 31 + a_2) * 31 + a_3) ... * 31 + a_n

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
a tömb jelenleg
0
1 ablak
2
3
4 akta
5
6
7
8
9
10
11
12
13 hal
14
15
16
17
29 kutya
32 atka
43

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 %

Lineáris vizsgálat

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 tömb jelenleg
0
1
2 ablak
3
4
5
6 kutya
7 atka
8 akta
9 hal
10 akna

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.

a tömb jelenleg
0 kaja
1
2 ablak
3
4
5
6 kutya
7 atka
8 akta
9 hal
10 akna

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.

Láncolás vagy vödör módszer

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.

a tömb jelenleg
0 bolha
1
2 ablak
3
4
5 alga talaj
6 kutya
7 atka kaja
8 akta
9 hal akna
10
oktatas/programozas/algoritmusok/hash.txt · Utolsó módosítás: 2019/12/01 22:19 szerkesztette: admin