3. Abbruchbedingungen bei Kollisionsauflösung/Hashtabellen

Abbruchbedingungen bei Kollisionsauflösung/Hashtabellen

  • N

    Hi,

    Ich soll mich gerade mit Hashtabellen beschaeftigen und erstmal eine Klasse schreiben, die Daten einfuegen/suchen/loeschen kann, erstmal mit Open Adressing, verschiedene Arten der Kollisionsaufloesung.
    Tjoar, und da bin ich jetzt etwas verwirrt am Gruebeln, nach wievielen Kollisionsaufloesungen es wohl Sinn macht, auszusteigen.

    Eine Abbruchbedingung ist klar, egal welches Verfahren ich benutze: Leerer Eintrag.
    Aber was, wenn die Tabelle vollgestopft ist?
    Fuer lineares sondieren und double hashing ist der Fall auch noch einfach: naemlich wenn der errechnete Ersatzindex wieder dem urspruenglich errechneten Hashwert entspricht (also die ganze Tabelle einmal abgelaufen wurde).

    Wie sieht das aber nun zB. mit Inkrementellem sondieren (also i[j] = (i[j-1] + j * a) % M , wobei a irgendein statischer Faktor und M die groesse der Tabelle), oder quadratischem Sondieren (i[j] = (i[0] + j^2)%M) aus?

    Ich bin da bisher nur auf die Idee gekommen, die Aufloesung entweder nach M-1 Durchgaengen, oder auch wieder wenn i[j+1] == i[0] (also der urspruengliche Index) ist, aubzubrechen.

    Noch irgendwelche besseren Ideen? Und welche der beiden Varianten ist wohl besser? 😃

    0
Anmelden zum Antworten