8. fejezet - Hasító táblázatok

Sok gyakorlati feladatban csupán a beszúrás, törlés és a keresés műveleteit kell végrehajtani. Amint azt az előző feladatban láttuk, láncolt listák esetén ezeknek a műveleteknek a bonyolulsága lineáris. (Itt beszúrásnál nem a listafejbe beszúrásról, hanem a rendezett listába szúrásról van szó, ahol a konstans bonyolultságú beszúrást egy keresés előzi meg.) A hasító táblázatok alkalmazásával ez a bonyolultság közel konstanssá redukálható.

8.1. Közvetlen címzés

Tegyük fel, hogy az adataink kulcsai az 1 és m közötti számok közül kerülnek ki, és m viszonylag kicsi. Ekkor készíthetünk egy T[1..m] táblázatot, ahol a táblázat elemei a megfelelő kulcsú adatra mutatnak, ha azok elemei a dinamikus halmaznak, egyébként Nil értékek (8.1.1. ábra). Ekkor a beszúr, töröl és keres műveletek a következőképpen néznek ki:

Function KÖZVETLEN-CÍMZÉS-KERESÉS(T,k) 
Input: T táblázat, k kulcs 
Output: A T táblázat k kulcsú adata 
1 return T[k] 

Procedure KÖZVETLEN-CÍMZÉS-BESZÚRÁS(T,x) 
Input: T táblázat, x beszúrandó adat 
Eredmény: Az adatot beszúrja a táblázatba 
1 T[x.kulcs] = x 

Procedure KÖZVETLEN-CÍMZÉS-TÖRLÉS(T,x) 
Input: T táblázat, x törlendő adat 
Eredmény: Az adatot törli a táblázatból 
1 T[x.kulcs] = Nil 

8.1. ábra - 8.1.1. ábra. Közvetlen címzés

8.1.1. ábra. Közvetlen címzés