Kollisionen behandeln:

• außerhalb der Tabelle: t[i] = Liste aller x mit h(x) = i. Nachteil: Extraplatz für Listenzeiger
• innerhalb der Tabelle:
  • speichere y in t[h(y) + 1] odert[h(y) + 2] oder ...

    Nachteil: Tabelle ,,verklebt``
    (belegte Blöcke erzeugen weitere Kollisionen)

  • doppeltes Hashing: benutze h₁, h₂ und benutze Indizes h₁(y), h₁(y) + h₂(y), h₁(y) + 2h₂(y),....

    Vorteil: kein Verkleben (Schrittweiten sind verschieden!)

Übung: diskutiere Löschen aus einer Hashtabelle