6  Hashstrukturen

Literatur: Kapitel 12 aus [CLR90]. Hashfunktionen werden auch in [Knu73b] diskutiert.

Inhalt Hashstrukturen ·Hashing mit externer Verkettung ·Hashing mit offener Adressierung ·Hashfunktionen

• drei Operationen eines Wörterbuches (dictionaries)
  • Suchen
  • Einfügen
  • Entfernen
• Hashtabellen: effizient zur Implementierung von Dictionaries

• implementiert mit Arrays, Zugriff direkt über Index = Schlüssel (key, eindeutig)
• Suchen, Einfügen, Entfernen: in konstanter Zeit (O(1)).

Search(T,k)   = return T[k];

Insert(T,x)   = T[key(x)] := x;

Delete(T,x)   = T[key(x)] := nil;

• Problem:
  • machbar nur für kleine Bereiche der Schlüssel, Platzverschwendung
  • nur destruktives Einfügen möglich
• Þ Hashtabellen

• Verallgemeinerung von Arrays mit direkten Zugriff
• gegeben: Bereich U der Schlüssel (``Universum'')
  
  
• hash-Funktion: h : U ® {0,... , m - 1}
  • |U|> m
  • Þ h nicht injektiv Þ Kollision
  • h(k): Hashwert von k
  • ``zufällige'' Funktion

• Verkettung (chaining, auch external chaining)
• Bild
• Varianten: Eindeutiger Schlüssel, implementierbar durch
  • Überschreibendes Einfügen, oder
  • Löschen nur mittels key (Delete(k)) und Löschen von allen Elementen mit passendem key, search gibt nur den ersten Treffer zurück.

Insert(T,x) = T[h(key(x))] := insert x at the head of T[h(key)];

Search(T,k) = Search for an element with key k in T[h(k)];

Delete(T,x) = Delete x  from list  T[h(k)];

• Worst-case: alle Elemente mit dem selben Schlüssel Þ O(n)
• im Mittel:
  • Annahme: Gleichverteilung = einfaches, uniformes Hashing
  • Hashfunktion h(k) mit konstantem Aufwand O(1)
  • Þ Suchen nach Element mit Schlüssel k: linear in der Länge von T[h(k)]

• eine Liste wird bis zum Ende durchsucht
• durchschnittliche Länge der Listen: a = n/m
• ÞO(1+ a)

• alle Schlüssel gleichwahrscheinlich, kein Schlüssel doppelt, Anfügen ans Ende

• Ziel: Gleichverteilung der Ergebnisse j von h(k) (aus dem Bereich 0 bis m-1):

  å {k| h(k) = j}

  P(k) =

  1 m

• falls keys gleichverteilt aus [0,1[ Þ h(k) = ë k m û Î {0, ..., m-1}
• ansonsten: Heuristiken

• Divisionsmethode	h(k) = k mod m
  Multiplikationsmethode	h(k) = ë m(k A - ë k A û) û (mit 0<A<1)
  Universal hashing	``zufällige'' Auswahl von h

• wichtig: Auswahl der Parameter, abhängig auch von den keys
  • Divisionsmethode: m prim, möglichst nicht nahe 2er-Potenz
  • Multiplikation: m egal

• alle Elemente in der Hashtabelle gespeichert (keine Pointer, keine externen Listen) Þ Verkettung wird errechnet
• Belegungsfaktor £ 1
• Sondierung (probe): Suche nach freiem Slot
• Þ Hashfunktion
  h: U * {0,... m-1} ® {0,...,m-1}
• Sondierungs-Sequenz (probe sequence) für Schlüssel k:
  (h(k,0), h(k,1), ..., h(k, m-1))
• gute Hashfunktion: Vermeidung von Häufungen (clusters)

• lineares Probing
  • gegeben: h': U ®{0,... m-1}: gewöhnliche Hashfunktion
    h(k, i) = ((h'(k) + i) mod m)
  • Probe-Sequenz: T[h'(k), h'(k)+1, ...]
  • Problem: primäre Häufung
• Quadratisches Probing
  • h' wie oben
    h(k, i) = ((h'(k) + c₁ i + c₂ i²) mod m)
• Doppeltes Hashing
  • gute Methode
  • h₁, h₂: zwei gewöhnliche Hashfunktionen
    h(k, i) = (h₁(k) + i h₂(k)) mod m
  • h₂(k) sollte relativ prim zu m sein!