[[oktatas:programozás:algoritmusok|< Algoritmusok]]

====== Hash ======

  * **Szerző:** Sallai András
  * Copyright (c) 2014, Sallai András
  * Licenc: [[https://creativecommons.org/licenses/by-sa/4.0/|CC BY-SA 4.0]]
  * Web: https://szit.hu
===== 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.

{{:oktatas:programozás:algoritmusok:hash.png|}}



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 =====

{{:oktatas:programozás:algoritmusok:kozvetlen_cimzes.png|}}


===== Hasítás =====

{{:oktatas:programozás:algoritmusok:has_felepitese.png|}}

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 | |
| <nowiki>...</nowiki> | |
| 20 | |
| 21 | hal |
| <nowiki>...</nowiki> | |
| 25 | ablak |
| <nowiki>...</nowiki> | |
| 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.

<m 16>(((a_0 * 31 + a_1) * 31 + a_2) * 31 + a_3) ... * 31 + a_n</m>

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 | |