Wie kann ein Hash-Set eine Kollision verursachen?

  • Wenn ein Hash-Set nur eine Instanz eines bestimmten Elements enthält, wie könnte in diesem Fall eine Kollision auftreten?

    Und wie könnte der Ladefaktor ein Problem sein, da es nur ein Element eines bestimmten Elements gibt?

    Auch wenn dies Hausaufgaben sind, sind es nicht meine Aufgaben. Ich unterrichte jemanden und muss wissen, wie ich es ihnen erklären kann.

    14 December 2013
    Chris ForrenceKent
2 answers
  • Nehmen wir an, Sie haben ein HashSet von Ganzzahlen und Ihre Hash-Funktion ist Mod 4. Die Ganzzahlen 0, 4, 8, 12, 16 usw. kollidieren, wenn Sie versuchen, sie einzufügen. (mod 4 ist eine schreckliche Hash-Funktion, veranschaulicht jedoch das Konzept.)

    Wenn eine korrekte Funktion vorausgesetzt wird, ist der Lastfaktor mit der Wahrscheinlichkeit einer Kollision verbunden. Bitte beachten Sie, dass ich korreliert und nicht gleich sage, da dies von der Strategie abhängt, mit der Sie Kollisionen behandeln. Im Allgemeinen erhöht ein hoher Lastfaktor die Möglichkeit von Kollisionen. Angenommen, Sie haben 4 Slots und verwenden Mod 4 als Hash-Funktion. Wenn der Lastfaktor 0 ist (leere Tabelle), haben Sie keine Kollision. Wenn Sie über ein Element verfügen, beträgt die Wahrscheinlichkeit einer Kollision 0,25, was die Leistung offensichtlich verschlechtert, da Sie die Kollision lösen müssen.

    Nehmen Sie nun an, dass Sie die lineare Prüfung verwenden (dh bei einer Kollision den nächsten verfügbaren Eintrag verwenden). Sobald Sie 3 Einträge in der Tabelle erreicht haben, besteht eine Wahrscheinlichkeit von 0,75 Kollisionen. Wenn Sie eine Kollision haben, gelangen Sie im besten Fall zum nächsten Eintrag. Im schlimmsten Fall müssen Sie jedoch die 3 Einträge durchgehen. Daher bedeutet die Kollision, dass Sie anstelle eines direkten Zugriffs im Durchschnitt eine lineare Suche mit durchschnittlich 2 Elementen benötigen.

    Natürlich haben Sie bessere Strategien, um mit Kollisionen umzugehen, und im Allgemeinen ist in nicht pathologischen Fällen eine Last von 0,7 akzeptabel, aber danach kollidieren Kollisionen und die Leistung nimmt ab.

    22 November 2011
    Luis
  • Die allgemeine Idee hinter einer "Hash-Tabelle" (von der ein "Hash-Satz" eine Vielzahl ist) ist, dass Sie eine Reihe von Objekten haben, die "Schlüssel" -Werte (z. B. Zeichenfolgen) enthalten, die Sie möchten in eine Art Container stellen und dann einzelne Objekte anhand ihrer "Schlüsselwerte" leicht finden können, ohne jedes Element im Container untersuchen zu müssen.

    Man könnte zB Fügen Sie die Werte in ein sortiertes Array ein und führen Sie dann eine binäre Suche durch, um einen Wert zu finden. Die Pflege eines sortierten Arrays ist jedoch teuer, wenn es viele Aktualisierungen gibt.

    Die Schlüsselwerte sind also "hashed". Man könnte zum Beispiel alle ASCII-Werte der Zeichen addieren, um eine einzige Zahl zu erzeugen, die der "Hash" der Zeichenfolge ist. (Es gibt bessere Hash-Berechnungsalgorithmen, aber der genaue Algorithmus spielt keine Rolle, und dies ist leicht zu erklären.)

    Wenn Sie dies tun, erhalten Sie eine Zahl Für eine Zeichenfolge mit zehn Zeichen wird dies im Bereich von vielleicht 600 bis 1280 liegen. Wenn Sie diese Zahl beispielsweise durch 500 teilen und den Rest übernehmen, haben Sie einen Wert zwischen 0 und 499. (Beachten Sie das Die Zeichenfolge muss nicht aus zehn Zeichen bestehen - längere Zeichenfolgen werden zu größeren Werten hinzugefügt, aber wenn Sie den Rest teilen und den Rest übernehmen, erhalten Sie immer noch eine Zahl zwischen 0 und 499.)

    Erstellen Sie nun ein Array mit 500 Einträgen. Berechnen Sie den Hashwert jedes Mal, wenn Sie ein neues Objekt erhalten, wie oben beschrieben, und verwenden Sie diesen Wert für die Indexierung des Arrays. Platzieren Sie das neue Objekt in den Array-Eintrag, der diesem Index entspricht.

    Aber (insbesondere mit dem oben beschriebenen naiven Hash-Algorithmus) könnten Sie zwei verschiedene Zeichenfolgen mit demselben Hash verwenden. ZB hätten "ABC" und "CBA" den gleichen Hash und würden am selben Platz im Array liegen.

    Um diese "Kollision" zu handhaben, gibt es mehrere Strategien, aber die gebräuchlichste ist das Erstellen einer verknüpften Liste aus dem Array-Eintrag und das Einfügen der verschiedenen Hash-Synonymen

    22 November 2011
    Hot Licks