Ez egy Redditen talált könyv egyik alfejezetének egy kivonatolt változata. A hash algoritmusok lényege, hogy vannak valami adatok, amiknek marha sok LEHETSÉGES értéke van, amikből viszonylag kevés valósul meg. Vegyünk például a neveket: mondjuk ha egy nevet maximum 50 karakteren tárolunk, akkor arról van szó, hogy borzalmasan sok lehetséges 50 karakteres string létezik, de ennek szinte leírhatatlanul kis része név, és még kisebb része az, ami ténylegesen elő is fog fordulni. Ugyanakkor Nagy Attilából, asszem az a leggyakoribb név, tutira lesz több is.
Alapból az ember úgy áll neki ennek a dolognak, hogy van egy üres listája, aztán amikor egy név befut, beleteszi a listába, és amikor keresni kell, akkor végigmegy a lista elejétől kezdve, és ha megtalálta a nevet, akkor szépen kiírja. Namost ez 'drága', mert minden alkalommal meg fogod nézni az A,B,C,... kezdetű embereket, holott neked éppen a Kovács kell, ami úgyis K-val kezdődik. Neveknél éppen ezért úgy szokás hash-elni, hogy a név első betűje a hash kulcs, persze sok embernek a neve kezdődik K-val, ezért a K betű mögött egy ún. 'vödör' lesz, amiben a K-val kezdődő nevek vannak, és azokon megint egyesével kell végigmenni, de azért az sokkal kevesebb, mint az összes név.
Általánosságban véve nem lehet jó hash algoritmust mondani. Ha azt mondod, hogy van egy N bit hosszú bináris adat, amiből marha sok darab fog beesni, egyenletes eloszlással, és mondjon erre valaki hash algoritmust, akkor az lesz a válasz, hogy vagy listába fűzöd, vagy bináris fát csinálsz belőle, vagy lefoglalsz 2^N db N bites helyet, és azokba rakod bele őket, mert így általánosan nem lehet jobbat mondani. (Biztos lehet, de most így hirtelen nem tudok.)
Ha viszont tudsz valamit mondani arról, hogy nagyjából mekkora adatmennyiségre számítasz, akkor elkezd a helyzet javulni. Tegyük fel, hogy úgy gondolod, hogy egyidejűleg kb. 120-125 adatnak kell a memóriában lennie. A teendőd az alábbi:
1. Megduplázod ezt a számod, biztos, ami biztos alapon.
2. Megkeresed a felette lévő első prímszámot. A tesztünk esetében ugye a 125 duplája a 250, a legközelebbi prímszám a 257.
3. Legyen N az ÖSSZES lehetséges adat száma. Bontsd fel N-et valami alkalmas módon részekre, mondjuk k darab részre. A lényeg, hogy n^k >= N teljesüljön.(n=257 esetén ez könnyű, mert pont byte-okra kell bontani.)
4. Generálj egy k db-ból álló sorozatot, amelynek minden eleme 1..n között van, egyenletes eloszlású véletlenszámokból.
Amikor egy hash-elendő érték befut, fel kell bontanod k részre, minden részt megszorozni a generált véletlensorozat idevágó elemével (az első részt a sorozat első elemével, stb.), az így kapott szorzatokat összeadni, tenni mindezt modulo n. (Vagyis ha az eredmény nagyobb, mint n, akkor addig vonod ki belőle n-t, amíg újra 0 és n-1 között nem lesz. Épelméjű nyelvekben van operátor a maradékos osztásra, MOD vagy % szokott lenni.) A végén a kapott szám a hash kulcs, persze 0 és n-1 között, tehát ha a nyelved olyan, akkor még 1-et hozzá kell adni.
Ez az algoritmus azt garantálja, hogy az ütközés veszélye 1/n, vagyis ennyi a valószínűsége annak, hogy ugyanaz a kulcs kijöjjön két különböző értékre. Persze lehetne feltolni n-et a csillagos égig, hogy szinte kizárt legyen az ütközés, és amikor n = N, akkor pont nulla is lesz a valószínűsége, de ennek pont az a lényege, hogy ha a várható adatmennyiséget jól becsülted meg, akkor elhanyagolható a valószínűsége annak, hogy egy vödörben akár csak két kulcs is legyen, viszont a memóriából se használtál sokkal többet, mint amit muszáj.
Biztosan vannak jobb módszerek is, csak megtaláltam ezt, és mivel többször fordult már elő velem, hogy valami tipp kellett volna hash-eléshez, gondoltam, közzéteszem.

w