Hasító tábla és a hasító függvény (Hash table and hash function)

A hasító táblák célja egy olyan adattárolási eljárás megvalósítása, amelyben a keresés, beszúrás és törlés nagyon hatékonyak. Akár 1-2 lépéssel megtalálható minden keresett kulcs.

Jelölések:

• $m$ hasító tábla mérete
• $T[0..m)$ hasító tábla
• $T[x]$ hasító tábla $x$-edik helye, más néven rése
• $\emptyset$ üres rés a hasító táblában
• $n$ hasító táblában tárolt adatok száma
• $\alpha = \frac{n}{m}$ tábla kitöltöttségi aránya
• $U$ kulcsok univezuma
• $h : U \rightarrow 0..(m-1)$ hasító függvény

• $E$ nyílt címzésnél üres rés
• $D$ nyílt címzésnél törölt rés

Hasító függvények:

A hasító függvényt arra használjuk, hogy meghatározzuk a rést a $k$ kulcsból. A kulcsok nem feltétlenül természetes számok, viszont természetes számokként kell megjeleníteni őket. A $k$ kulcsú elem, így a $h(k)$ résre képződik le. A hasító függvény célja még, hogy csökkentsük a szükséges tömbindexek tartományát. Fontos az is, hogy gyorsan számolható legyen, kiszámítása ne legyen túlságosan költséges. Továbbá fontos az is, hogy korlátos legyen. Egy jó hasító függvény egyszerű egyenletes hasítás, ha minden kulcs egyforma valószínűséggel képződik le az $m$ rés bármelyikére függetlenül attól, hova képződik le a többi kulcs. Tetszőleges hasító függvénnyel kapcsolatos elvárás, hogy egyszerű egyenletes hasítás legyen. Ha a kulcsaink nem számok, hanem például stringek, akkor valamely egyszerű transzformációval könnyen képezhetünk belőlük egészeket, amelyhez aztán az osztó vagy szorzó módszerrel készíthetünk alkalmas hasító függvényeket.

Osztó módszer:

Ha a kulcsok egész számok, gyakran választják a $h(k) = k \space mod \space m$ hasító függvényt, ami gyorsan és egyszerűen számolható. Egyenletessége nagyban függ az $m$ megválasztásától. Érdemes olyan prímnek választani, amely nincs közel a kettő hatványokhoz.

Kulcsok a $[0 ; 1)$ intervallumon:

Ha egyenletesen oszlanak el, a $h(k) = \lfloor k \cdot m \rfloor$ függvény is kielégíti az egyszerű, egyenletes hasítás feltételét.

Szorzó módszer:

Ha a kulcsok valós számok, tetszőleges $0 < A < 1$ konstanssal alkalmazható a $h(k)=\lfloor \{k \cdot A \} \cdot m \rfloor$ hasító függvény ({x} az x törtrészét jelöli). Kihívást jelent a jó $A$ konstans értékének megválasztása. Nem minden lehetséges konstanssal szór egyformán jól. Az $m$ megválasztása kevésbé jelentőségteljes az egyenletes hasítás eléréséhez.

Gyakorlati alkalmazása:

Egy programozási nyelv fordítóprogramja szimbólumtáblát használ, melyben az elemek kulcsai a nyelv azonosítóinak megfelelő karakterláncok. A hasító táblázat hatékony adatszerkezet szótárak megvalósítására.