A hash függvény egy olyan függvény, amely tetszőleges méretű bemenetet képez le egy adott, fix méretű kimenetre.

Hash függvény pl:

  • f(Személy) = Személy születésnapja (1-365 közötti szám)
  • f(Szám) = Az adott szám utolsó számjegye (0-9 közötti egész)

A hash függvényeket több különböző célra is fel lehet használni, a választott céltól függ, hogy melyik hash függvény lesz nekünk épp jó.

Hash függvény egyirányú, hiszen pl. az ember születésnapjából nem derül ki egyértelműen, kiről van szó.

Átviteli hibaellenőrzés

Lemezek között, hálózaton stb. átvitel közben ritkán, de előfordulhat, hogy megsérül az adat, a cél eszközre más kerül, mint amit szeretnénk. Egy jól megválasztott hash függvénnyel nem kell 2-3x átvinnünk az adatot, hogy biztosak legyünk a sikerben. Egy ilyen hash függvény egymáshoz közel álló bemenethez is teljesen különböző kimenetet ad. Néhány példa:

Paritás

Bemenet: tetszőleges bináris adat

Kimenet: 1 bit: 0 ha az 1-es bites száma páros, 1 ha páratlan

Pl.:

Be: 00010110

Ki: 1 (mert 3 db 1-es szerepel)

Az adat, amit továbbítunk, az a “00010110 1” lesz. A fogadó fél szintén elvégzi a paritás vizsgálatot, és összehasonlítja, hogy a legutolsó, ún. paritásbit stimmel-e. Ha nem, akkor biztosan hiba történt.

Akár hardveresen is nagyon egyszerű implementálni, és ha egy bitnyi tévedés történik, azonnal észre lehet venni.

CRC32 (cyclic redundancy check)

Bemenet: tetszőleges bináris adat

Kimenet: 32 bites (4 bájtos) szám

Pl.:

Be: Hello

Ki: 2880899316

Ha egy betűt is elírunk, akkor a kimenet teljesen megváltozik:

  • Helo - 2822868267
  • Helló - 1330752473
  • hello - 3287646509

A CRC32 algoritmus beépített része a hálózati protokolloknak.

Titkosítás

Ha a hash kódból nem lehet könnyen visszfejteni, hogy milyen adatot hash-eltünk előtte, sem egy másik adatot generálni, ami ugyanarra a hash kódra érkezik, akkor a függvény alkalmas lehet jelszavak egyirányú titkosítására.

Pl. sha512(tesztjelszo) =
8cbcc9f1d40c07bc765d9443f776e0373b59ca3d260b7c13dd883e930a883ee9 a1b8353bd13d20f1bd968be61e87dd7b002ccc0b89adc6086c9b65fdd594effc

Megj.: Hosszabb számoknál szokás a kimenetet hexadecimális (16-os) számrendszerben ábrázolni

A titkosítási, biztonsági témakört itt fejtem ki részletesebben (TODO).

Azonnali adatelérés, hash tábla

Egy adatszerkezetben történő keresés viszonylag lassú művelet lehet.

  • Hagyományos tömbben végig kell nézni az összes elemet (lassú).
  • Rendezett tömbben vagy bináris fában lépésenként ki tudjuk dobni az elemek felét (gyorsabb)

Egy jó hash függvény segítségével azonban még ennél is gyorsabban, akár egy lépésből lekérdezhetjük, hogy egy adott elem szerepel-e az adatszerkezetünk-ben, vagy sem.

Az adatszerkezet

Tegyük fel, hogy a hash függvényünk 10 különböző kimenetet tud adni (0-9). Ilyen pl. az f(x) = x mod 10, vagyis a szám 10-zel vett osztási maradéka.

Ezért vegyünk fel egy 10 elemű tömböt, ami kezdetben üres:

0 1 2 3 4 5 6 7 8 9
                   

Szeretnénk az alábbi elemet beszúrni: 15

Elvégezzük rajta a hash függvényt: f(15) = 15 mod 10 = 5
Vagyis az 5-ös indexre fogjuk beszúrni:

0 1 2 3 4 5 6 7 8 9
          15        

A 121-et az 1-es indexre:

0 1 2 3 4 5 6 7 8 9
  121       15        

A 96-ot pedig a 6-os indexre:

0 1 2 3 4 5 6 7 8 9
  121       15 96      

Kulcsütközés

Előfordulhat, hogy olyan elemet szeretnénk beszúrni, ami már foglalt. Pl. a 75-nek is 5-ös a hash-e. Ezt úgy hívjuk, hogy kulcsütközés. Ennek a megoldására több módszer is létezik: Láncolás, lineáris ill. kvadratikus próba, kettős hash-elés.

Mi most a lineáris próbát fogjuk használni.

Ez azt jelenti, hogy megpróbáljuk a rákövetkező mezőbe beletenni az elemet, ha az is foglalt, akkor a következőbe… egészen addig, amíg üres mezőt nem találunk.

A jelenlegi példában a 75 a 7-es index alá fog kerülni, mert az 5 és a 6 már foglalt:

0 1 2 3 4 5 6 7 8 9
  121       15 96 75    

Egy hash tábla akkor működik gyorsan, ha minél kevesebb a külcsütközés.

Kikeresés

A 121 elem szerepel a táblában? Ehhez szintén a hash függvényt kell alkalmaznunk:

f(121) = 1, ezért az 1-es index alatt nézzük meg. Ott is van, tehát benne van. Igen, szerepel.

983 elem szerepel? f(983) = 3, a 3 index üres. Nincs ott, ezért máshol sem lehet. Nem, nincs benne.

A 75? f(75) = 5 alatt a 15-ös szerepel. De ilyenkor azonban nem adhatjuk fel, mert mi van, ha kulcsütközés miatt máshova került?

  • Meg kell nézni a 6-os alatt is. Ott sem a 75 van.
  • 7-es alatt? Igen, megtaláltuk!

A 86? f(86) = 6

  • 6-os alatt a 96 szerepel, ezért tovább kell mennünk
  • 7-es alatt a 75
  • 8-as üres, ezért megállhatunk: nem szerepel.

Törlés

A törlés azért bonyolítja meg az életünket, mert a fenti lineáris próbát el tudja rontani. Képzeljük el, hogy naív módon kitöröljük a 96-ot:

0 1 2 3 4 5 6 7 8 9
  121       15   75    

Ez után a 75 kikeresése így zajlik:

  • f(75) = 5
  • 5-ös alatt 15 szerepel
  • 6-os üres nem szerepel <- Ez hibás!

Törléskor ezért egy “jelölést” bent kell hagynunk, hogy tudjuk, az adott mező már egyszer valamikor tartalmazott értéket. Jelöljük pl. X-szel:

0 1 2 3 4 5 6 7 8 9
  121       15 X 75    
  • f(75) = 5
  • 5-ös alatt 15 szerepel
  • 6-os üres, de X van benne, ezért továbbmegyünk
  • 7-es alatt a 75 van: benne van.

Az X helyébe természetesen lehet új értéket is beszúrni, az nem ront el semmit:

Beszúrunk: 455-öt:

  • f(455) = 5
  • 5 már foglalt
  • 6 üres, bár X szerepel, attól még felülírhatjuk:
0 1 2 3 4 5 6 7 8 9
  121       15 455 75    

A jó hash függvény

A jó hash függvény olyan, ami minél egyenletesebben szórja szét az elemeket a hash táblában, hogy minél kevesebbet kelljen próbával továbblépkedni. Az x mod 10 ebben az esetben nem volt jó függvény, mert sok elemet próbált az 5-ös és a 6-os indexre tenni, miközben a tábla fele üres maradt. Ideálisan az összes bitet, a magasabb helyiértékeket is figyelembe veszi.

A hash tábla mérete, születésnap-paradoxon

A hash függvényünk legyen a legelső példánk:

f(Személy) = Személy születésnapja (1-365 közötti szám)

Hány főnél lesz 50%-nál nagyobb a valószínűsége, hogy két embernek ugyanaz a születésnapja (azaz kulcsütközés lép fel)?

A válasz meglepően kicsi: mindössze 23 embernél már több, mint 50%!

Ezt hivják Születésnap-paradoxonnak. Nem azért paradoxon, mert valami matematikai probléma van vele, szimplán azért, mert az intuíciónknak teljesen ellentmond.

Ez azt jelenti, hogy egy jól működő hash táblához a várható elemszámnál nagyságrenddel több memóriára van szükség. A 365-ös példánál is ez már több, mint az elemszám 15×-öse. Ha a memória az alkalmazásunk egy szűk keresztmetszete, akkor érdemsebb lehet egy lassabb, de kisebb memóriaigényű adatszerkezetet választani: pl. egy keresőfát.