Hash Table: Soll ich die Elementzählwert auf Kollisionen erhöhen?

Question

Im Moment meine Hash-Tabellen zählen die Anzahl der jedes Element in die Hash-Tabelle eingefügt. Ich benutze diese Zählung mit der Gesamt Hashtabellengröße, den Lastfaktor zu berechnen, und wenn es wie 70% erreicht, ich aufwärmen es.

Ich dachte, dass vielleicht sollte ich nur die eingefügten Elemente mit Füllungen einen leeren Slot zählen statt alle von ihnen. Ursache der Kollision Methode verwende ich getrennt Verkettungs. Der Faktor Belastung steigt weiter, aber wenn es kann ein paar Kollisionen viele leere Slots auf der Hash-Tabelle zu verlassen.

Sie denken wahrscheinlich, dass, wenn ich, dass viele Kollisionen haben, vielleicht nicht die beste Hashing-Methode Ich verwende. Aber das ist nicht der Punkt, ich bin mit einem der Know-Hashing-Algorithmen gibt, die ich getestet 3 von ihnen auf meine Beispieldaten und die einen ausgewählten, die weniger Kollisionen erzeugt werden.

Meine Frage bleibt. Soll ich jedes Element eingefügt, oder nur diejenigen zählen, die einen leeren Platz in der Hash-Tabelle zu füllen?

Answer 1

Wiederkäuen soll die Wahrscheinlichkeit von Kollisionen zu reduzieren, so systematisch Kollisionen ignorieren zu entscheiden, wann zu Aufguss scheint selbstzerstörerische.

Die Besten sein könnten, wenn Sie mit jedem Eintrag halten den ursprünglichen vollen Hash-Wert (eine Kollision natürlich wird stattdessen durch den Hash bestimmt Modulo Ihrer aktuelle Größe) und nur die Kollisionen gezählt, die die Modulo-Operation zurückzuführen sind - implizit anerkannt, dass wenn eine Kollision aufgrund identischer vollständiger Hash-Werte für verschiedene Einzelteile ist, gibt es nichts Wiederkäuen zu Hilfe tun kann (es sei denn durch „Wiederkäuen“ Sie auch auf eine andere Hash-Funktion implizieren Schalen, aber es sieht nicht aus wie das, was Sie hier bedeuten; -).

Halten Sie die vollständigen Hash-Werte bedeutet auch billiger Aufguss, da Sie nicht die Hash-Funktion wieder ausführen müssen (wie relevant ist das hängt davon ab, wie teuer Ihre Hash-Funktion ist natürlich zu berechnen).