Ist es sinnvoll, eine Hash-Tabelle nach unten, um die Größe? Und wann?

Question

My Hash Table Implementierung hat eine Funktion, um die Tabelle, wenn die Last erreicht etwa 70% zu ändern. Mein Hash Table ist für Kollisionen mit separatem Chaining realisiert.

Ist es sinnvoll, dass ich die Hash-Tabelle nach unten an einem beliebigen Punkt Größe ändern sollte oder ich lass es einfach wie es ist? Andernfalls, wenn ich die Größe erhöhen (um fast das Doppelte, ich dies tatsächlich folgen: http://planetmath.org /encyclopedia/GoodHashTablePrimes.html ), wenn die Last 70% ist, sollte ich es die Größe nach unten, wenn die Last 30% bekommt oder unten?

Answer 1

Schreibst du die Hash-Tabelle für allgemeine Zwecke zu verwenden, oder gibt es einen bestimmten Zweck für sie? Ich schlage vor, Ändern der Größe nicht kleiner für eine allgemeine Implementierung. Dies wird Ihren Tisch einfach halten und halten Sie sie aus dem Gedächtnis Dreschen unter Bedingungen, bei denen der Tisch gefüllt ist und oft entleert. Wenn Sie in einen Zustand am Ende laufen, wo der Hash-Tabelle Bedarf in der Größe reduziert werden, erweitert sie zu diesem Zeitpunkt.

Answer 2

Hash-Tabellen müssen Primzahl Längen nicht haben, wenn Sie eine gute Qualität Hash-Funktion (siehe hier ). Sie können sie Potenzen von zwei machen, die im wesentlichen Indices Berechnungen beschleunigt.

Warum ist das auf die Frage relevant? Denn wenn Sie ein Power-of-two hashtable schrumpfen, können Sie alle Einträge in der unteren Hälfte verlassen, wo sie sind und einfach die verknüpfte Liste in Schlitz i (aus der oberen Hälfte) auf die verknüpfte Liste in Steckplatz i - n/2 hängen.

Answer 3

Wenn der Speicher billig ist, lassen sie allein. Wenn der Speicher teuer ist, die Größe mit hysterisis wie Sie vorgeschlagen haben. Wenn Sie fertig sind, das Profil das Ergebnis sicherzustellen, dass es albern gut und haben nicht getan etwas führt.

Answer 4

Erste Idee: Der einzige Grund für eine Hash-Tabelle wächst, weil hashtable Leistung verringert sich, wenn zu viele Kollisionen sind. Wachsende den Tisch, wenn seine Last 70% überschreitet ist eine gute Faustregel dies zu verhindern, aber es ist nur eine Regel des Daumens. Viel besser ist, den Überblick über die Anzahl der Kollisionen zu halten und nur die Hash-Tabelle wachsen, wenn sie eine bestimmte Grenze oder, wenn ein bestimmtes Kollision Verhältnis überschreiten getroffen wird. Schließlich wollen, warum würden Sie eine Hash-Tabelle wachsen, die um 90% geladen ist, hat noch nicht eine einzige Kollision? Es würde keinen Vorteil hat.

Zweite Idee: Der einzige Grund, eine Hash-Tabelle zu schrumpfen ist um Speicherplatz zu sparen, noch schrumpft es könnte die Zahl der Kollisionen erhöhen und damit die Suchleistung verringern. Dies ist eine klassische Geschwindigkeit vs Speicher Handel ab und warum sollten Sie lösen es selbst? Lassen Sie es wem auch immer Ihr Code verwendet. Einfach nie auf eigener Faust schrumpft, sondern ein Schrumpfverfahren bieten. Wenn niedrige Speichernutzung eine Anforderung ist, wer auch immer Ihr Code verwendet, kann regelmäßig aufrufen schrumpfen. Wenn die maximale Leistung, wenn eine Anforderung, wer auch immer Ihr Code verwenden sollte nie schrumpfen nennen. Alle andere eine Art von Heuristik verwenden kann, um zu entscheiden, ob und wann Schrumpf zu nennen.

Dritte Idee: Wenn wachsen oder schrumpfen, immer wachsen / schrumpfen in einer solchen Art und Weise, dass nach der Operation eine gewisse Ladefaktor gewährleistet ist. Z.B. wenn wächst, wächst immer so, dass danach der Lastfaktor 50% und beim Schrumpfen, schrumpft immer so, dass danach der Lastfaktor 70%. Natürlich, sagt, dass nichts über die Anzahl der Kollisionen, ein Element so Zugabe unmittelbar nach wachsen / schrumpfen kann die Hash-Tabelle führt wieder zu wachsen, aber das ist unvermeidbar, da die Wirkung einer Zucht Simulation / Schrumpf ist in der Regel zu teuer. schrumpft auch oft genannt werden, wenn keine weiteren Änderungen geplant sind, so sollte es eher speichert Speicher als avoid in Zukunft wieder wachsen zu müssen.

Letzte Idee: Für jede Entscheidung, die Sie machen, werden Sie die Hash-Tabelle besser für einige Anwendungsfälle und schlechter für andere knüpfen. Wenn Sie wissen, wie Ihre hashtable verwendet werden soll, wird dies kein Problem sein. Doch wenn Sie dies nicht tun, und in der Regel nicht wahr, warum diese Entscheidungen selbst? Gerade sie delegieren. Hiermit kann der Anwender des Codes all die kleinen Details anpassen, zum Beispiel wie viel zu wachsen oder schrumpfen, entweder durch all diese Faktoren erlauben gesetzt werden, wenn der Hash-Tabelle erstellt wird oder von Ihrem hashtable ermöglicht delegieren Funktionen zu haben (Callback-Funktionen, dass man immer fragen kann, wenn sich nicht sicher, was zu tun). Auf diese Weise jeder Benutzer Ihres Codes können für Ihren Code sogar zur Laufzeit anpassen, was auch immer Verwendungsszenario sie es benötigen.