Problem: Hashkollisionen

• Was tun, wenn x≠y, aber h(x)=h(y)?

• Möglichkeit 1: Listen bilden? [➸Tafelbild]

  • u.U.: Lange Laufzeit, bis freier Platz gefunden

• Möglichkeit 2: Multiple Probing? [➸Tafelbild]

  • Versuche zunächst bei h(x,0), dann h(x,1), dann h(x,2)…
  • u.U.: Lange Laufzeit, bis freier Platz gefunden

• Möglichkeit 3: Einfach überschreiben???

  • Verlustbehaftetes Hashing
  • Ungewisser Gewinn

Notizen: