8.4. Nyílt címzés

Az előbbi esetekben a tömbben csak mutatókat tároltunk, s az adatokat ehhez a tömbhöz láncoltuk. A nyílt címzés esetén a tömbben az adatokat tároljuk. Ebből következik, hogy maximum csak annyi adatot tárolhatunk, amekkora a tömb. (Az előbbi példákban egy nyolc- és kilencelemű tömbhöz kapcsolódóan tíz elemet tároltunk.) Miután az ütközéseket most sem kerülhetjük el, a hasítófüggvény kicsit megváltozik: h(k) helyett h(k, i)-t használunk. A függvény megfelelő megválasztása esetén a {h(k, 0), . . . , h(k,m)} = {0, . . . ,m − 1}. Gyakori választás a

– h(k, i) = (h'(k) + i) mod m (lineáris kipróbálás),

– h(k, i) = (h'(k)+ci+di2) mod m, ahol c és d megfelelően kiválasztott konstansok (négyzetes kipróbálás),

– h(k, i) = (h'(k) + ih''(k)) mod m, ahol h' és h'' kisegítő hasítófüggvények (dupla hasítás).

Az alábbi programokban az egyszerűség kedvéért az adat helyett, csak annak kulcsát jelöljük. A beszúró és kereső művelet a következő:

Procedure HASÍTÓ-BESZÚRÁS(T,k) 
Input: T hasító táblázat, k beszúrandó kulcs 
Eredmény: Az adott kulcsot beszúrja a táblázatba 
1  i = 0 
2  repeat 
3     j = h(k, i) 
4     if T[j] == Nil then 
5        T[j] = k 
6        return 
7     else 
8       i = i + 1 
9     endif 
10 until i == m 
11 hiba”A hasító táblázat túlcsordult!” 

Function HASÍTÓ-KERESÉS(T,k) 
Input: T hasító táblázat, k a keresett kulcs 
Output: A keresett kulcs indexe, illetve Nil 
1 i = 0 
2 repeat 
3    j = h(k, i) 
4    if T[j] == k then 
5       return j 
6    endif
7    i = i + 1 
8 until T[j] == Nil or i == m 
7 return Nil 

Az alábbi ábrákon a lineáris kipróbálást használjuk a szorzásos módszerrel összekapcsolva, ahol m = 15. A megfelelő adatok az 1. táblázatból leolvashatók. A korábbi prímeket helyezzük el újra. Az első ütközés a 19 beszúrásakor történik.

8.7. ábra - Ütközés a 19 beszúrásakor, i = 0

Ütközés a 19 beszúrásakor, i = 0


Az i = 1 esetén is ütközik,

8.8. ábra - Ütközés a 19 beszúrásakor, i = 1

Ütközés a 19 beszúrásakor, i = 1


majd csak i = 2 esetén sikerül elhelyezni.

8.9. ábra - A 19 elhelyezhető i = 2 esetén

A 19 elhelyezhető i = 2 esetén


A 23 beszúrásakor hasonlóan két ütközés történik ,

8.10. ábra - Ütközés a 23 beszúrásakor, i = 0

Ütközés a 23 beszúrásakor, i = 0


8.11. ábra - Ütközés a 23 beszúrásakor, i = 1

Ütközés a 23 beszúrásakor, i = 1


s itt is csak i = 2 esetén sikerül elhelyezni.

8.12. ábra - A 23 elhelyezhető i = 2 esetén

A 23 elhelyezhető i = 2 esetén


A 29 beszúrásakor is lesz egy ütközés,

8.13. ábra - Ütközés a 29 beszúrásakor, i = 0

Ütközés a 29 beszúrásakor, i = 0


és csak a i = 1 esetén kerül helyre.

8.14. ábra - A 29 elhelyezhető i = 1 esetén

A 29 elhelyezhető i = 1 esetén


Hasító törlés nincs, mert ha a példában látható tömbben a 19 kulcsú elemet törölnénk, a 29 kulcsú elemet már nem találná meg a HASÍTÓ-KERESÉS eljárás, mert a ciklusból a T[j] = Nil feltétel miatt eredmény nélkül kilépne.