Hashing mit offener Adressierung

Beispiele:

• Lineares Sondieren (linear Probing)
• Quadratisches Sondieren
• Double Hashing
• Robin-Hood-Hashing
• ...

Bei dieser Methode werden die Elemente nicht in der Liste, sondern direkt in der Hash-Tabelle gespeichert. Wird bei Insert oder IsElement , angewendet auf Schlüssel k, ein Element mit Schlüssel $\neq k$ an der Adresse h(k) gefunden, so wird auf deterministische Weise eine alternative Adresse berechnet. Für jeden Schlüssel $k\in U$ wird somit eine Reihenfolge (Sondierungsfolge), in der alle slots in T[ ] betrachtet werden, um k zu speichern bzw. zu finden, festgelegt. Dieser Vorgang heißt sondieren.

Sondieren:

Sei $s(j,k) : [0..m-1] \times U \rightarrow [0..m-1]$;
Definiere $h(j,k)= \left(h(k)-s(j,k)\right) \text{\underline{mod} } m$ ;$(0\leq j \leq m-1)$;
Starte mit h(k), dann (falls (h(k)) belegt) Index $\left(h(k)-s(1,k)\right) \text{\underline{mod} } m$;

Problem: Sei h(k) = h(k') für 2 Schlüssel $k,k'\in S \subset U$. Werde zunächst k eingefügt, dann k', dann k gelöscht. Wie findet man k' (Beachte: k' steht nicht unmittelbar an h(k'))?
Lösungsvorschlag: Markiere k als gelöscht! Wenn Speicher gebraucht wird, k überschreiben. Alternativ: Hashtabelle neu aufbauen/überarbeiten.

Beispiele für Sondierungen:

• Lineares Sondieren: Setze s(j,k)=j d.h. sondiere gemäß $h(k),h(k)-1,\dots,0,m-1,..,h(k)+1$
  Es wird für IsElement solange rückwärts gesucht, bis entweder das Element mit Schlüssel k oder eine freie Position gefunden ist. Im letzteren Fall ist das gesuchte Element nicht in der Hash-Tabelle enthalten.
  Problem: Es entstehen primäre Häufungen (primary Clustering) um diejenigen Schlüssel herum, die beim Einfügen eine Kollision hervorgerufen haben.
  
  

  $$\beta$$ erfolgreich erfolglos

  0.5 1.5 2.5

  0.9 5.5 50.5

  0.95 10.5 200.5

• Quadratisches Sondieren
  Setze $s(j,k)=(-1)^j\lceil\frac{j}{2}\rceil^2$, d.h. sondiere nach $h(k),h(k)+1,h(k)-1,h(k)+4,h(k)-4,\dots$
  Frage: Ist das überhaupt eine Permutation von [0..m-1]? Ist s(j,k) geeignet alle slots zu erreichen?
  Man kann zeigen, daß für ein primes m von der Form 4i+3 die Sondierungsgröße (h(k)-s(j,k)) mod m Permutation von [0..m-1] ist.
  
  

  $$\beta$$ erfolgreich erfolglos

  0.5 1.44 2.19

  0.9 2.85 11.4

  0.95 3.52 22.05

• Double Hashing
  Setze s(j,k)=jh'(k), wobei h' eine zweite Hashfunktion ist. h'(k) muß relativ prim zu m gewählt werden, damit (h(k)-s(j,k)) mod m eine Permutation der Hashadressen wird.
  
  

  $$\beta$$ erfolgreich erfolglos

  0.5 1.39 2

  0.9 2.55 10

  0.95 3.15 20

  Zum Beispiel: h'(k)=1+k mod n-2 (mit n prim).