Hash tömb

A hash-elés egy érdekes trükk. Ha megnézünk egy szótárat, akkor sok esetben oldalról ránézve látszik, hogy hol kezdődnek az egyes betűk. Miért jó ez? Azért, mert egyből tudjuk, hogy nagyjából hol van az, amit keresünk. Így egy csomó keresési időt megspórolhatunk: ránézünk a keresett elemre (most éppen szóra), és egyből tudjuk, hogy a tömbnek (na jó, szótárnak) melyik részén kell keresni.

Mi is történik itt? Van egy függvény, ami minden lehetséges elemhez (akár benne van a tömbben, akár nincs), hozzárendel egy számot (pl. "G" betűsök első oldala). Így ha keresünk valamit, akkor először megkérdezzük, hogy nagyjából hol lehet, és csak onnan kezdünk el keresgélni. Ezt a függvényt hívják hash függvénynek.

A nyitott címzéses hash-elés alapvetően úgy működik, hogy van egy nagy tömb, és minden elemet oda rakunk, amilyen indexet a hash-függvény visszaad. (Például ha 256 helyünk van és szavakat tárolunk, akkor egy nagyon egyszerű hash függvény lehetne a "szo[0]" is: az első karakter kódja.) Ez szép és jó, amíg nem akarunk "barackfa" után "búgócsigá"-t beszúrni. Akkor mi van? A nyitott címzésű hash-elés azt mondja, hogy ilyenkor a kapott index-től előre haladva az első szabad helyre kerül a búgócsiga. (A vödrös hash-elég például minden indexhez több elemet is tud tárolni, mert ott mindhez létrehozunk egy külön tömböt... de az éppen ezért bonyolultabb is.)

Új elem beszúrása a hash táblába:

• Hash kód kiszámítása (hash függvény használata)
• A kapott indextől kezdve az első szabad helyre beírjuk az új elemet

Elem keresése:

• Hash kód kiszámítása a keresett elemhez
• Kapott indextől addik keresünk, amíg üres helyhez nem érünk. Ha közben megtaláljuk, akkor sikerült. Ha nem, akkor máshol nem is lehet, így kijelenthetjük, hogy nem szerepel a hash táblában.

Elem törlése:

• Törlendő elem hash-kódjának kiszámítása
• Törlendő elem megkeresése
• Törlendő elem helyét... hmmm... simán csak töröljük? Neeeem, ugyanis...

...itt vigyázni kell! Ha például egymás után van "barackfa" és "búgócsiga", utána pedig töröljük a barackfát, akkor utána keresésnél azt fogjuk hinni, hogy nincsen búgócsiga, mivel a hash-függvény által adott indexnél nincsen semmi (így feltételezzük, hogy utána sincsen, mert ha lenne, ide raktuk volna.) A megoldás: ha törlünk valamit, akkor a helyét csak megjelöljük, hogy "törölve, felül lehet írni, de még vannak utána dolgok, így keresésnél itt ne állj meg!".

Tehát a hash tábláknál mindig nagyon figyeljetek arra, hogy a törölt elemeket hogyan jelölitek és hogy egy elem keresésekor meddig nem adjátok fel a keresést!

A hash függvény: sokféle lehet. Célja az, hogy az elemeket jól szétszórja a hash táblában (akkor is, ha például csak B betűs szavakat tárol valaki), így az általános írányelv az, hogy a hash-kód lehetőleg az egész adattól függjön és ne csak egy részétől. (Pl. összeadhatjuk a karakterek kódjait, majd osztjuk a táblamérettel és vesszük a maradékot.)

Egy nyílt címzéses hash tábla általában addig működik normálisan, amíg a telítettsége 70-80% alatt van. Utána már nagyon durván vergődik szegény, mert folyton hatalmas területeket kell végigszaladnia, ha meg akar találni valamit... Ha viszont nincs ennyire telítve, akkor nagyon hasznos, mert az elemeket gyakorlatilag azonnal (1-2 lépésben) megtalálja.