Wie viele hash-buckets

Question

Wenn ich merke, dass eine hash-Tabelle (oder eine andere Daten-Struktur gebaut, auf einer hash-Tabelle) füllt sich, an welchem Punkt sollten Sie erstellen Sie eine neue Tabelle mit mehr buckets.Und bei n Elementen in der Tabelle so weit, wie wollen Sie herausfinden, wie viele Eimer zu verwenden in die neue?

Also sagen wir, ich habe 100 Eimer.Sollte ich reorganisieren Sie es, wenn es sind 50 Stück in es?500?5000?Oder sollte ich suchen für die meisten vollen Eimer und Schlüssel auf?Dann, wenn ich Treffer, die zeigen, wie groß mache ich den neuen hash-Tabelle?

Im Zusammenhang mit diesem, wenn Sie im Voraus wissen, ungefähr, wie viele Elemente gehen wird, gibt es eine Möglichkeit zu berechnen, die Anzahl der Eimer, um eine gute Durchschnittliche Leistung?

Ich weiß die richtige Antwort hängt von einer Menge anderer überlegungen, wie, wie wichtig ist die Geschwindigkeit vs.Größe in einem bestimmten Beispiel, aber ich bin auf der Suche nach Allgemeinen guildlines.

Ich weiß auch, dass ich nicht die sein, die Optimierung von dieser Art der Sache, es sei denn, guten profiling hat angedeutet, dass dies ein Engpass.Ich bin einfach nur zu denken über ein Projekt, würde eine Menge von hash-Tabellen und fragte sich, wie man diesen Ansatz.

Answer 1

Eine gute Regel der Daumen (nicht immer ideal, gut, nur eine Faustregel) ist die re-hash, wenn die hashtable ist gefüllt bis zu 80%.Das heißt, wenn Sie 100 Eimer und 80 Elemente im inneren, unabhängig davon, wie viele Kollisionen, die Sie vorher hatte, es ist schon Zeit um die Kapazität zu erhöhen.

Wie viel sollte man steigern?Gut, es gibt auch keine perfekten Wert.Einfachste Lösung ist die doppelte Kapazität auf den einzelnen erhöhen.So geht es nach 200, 400, 800, und so auf.Wenn Sie denken, das ist zu viel (es sind schließlich springen von 8-MB-Speicher auf 16 MB, wenn die hashtable wird wirklich groß ist und Sie vielleicht nie füllen die 16 MB), wählen Sie eine kleinere wachsen Faktor.Mindestens 1/3 empfehlen (es wächst von 100 auf 133), würde ich sagen, vielleicht lassen Sie es ein Wachstum von 50% in jeder Zeit, als ein Kompromiss.

Beachten Sie, dass all dies hängt auch davon ab, wie Kollisionen behandelt werden.Ein einfacher Weg, Sie zu behandeln (mein persönlicher Favorit) ist zu speichern Sie die Elemente in einer verknüpften Liste, wenn es ist eine Kollision.Wenn 3 Elemente befinden sich auf der gleichen Taste, es sind immer noch nur bis zu 3 vergleicht, um es finden.Seit verlinkten Liste sind sehr effektiv für die Suche, möchten Sie vielleicht Erhöhung der Kapazität früher, z.B.wenn 60% der Kapazität ist verwendet zu halten die Hashtabelle schnell.OTOH, Sie können etwas tun, raffinierter und halten Sie Statistiken über die Anzahl der Kollisionen.Solange du kaum Kollisionen (wenn Sie haben eine sehr gute hash-Funktion) es besteht keine Notwendigkeit zu re-hash an alle, auch wenn 99% seiner Kapazität verwendet wird.Auch wenn Sie mit Kollisionen in eine anspruchsvolle Art und Weise (z.B.jeder Knoten ist wieder eine sortierte Tabelle, und Sie können eine binäre Suche innerhalb dieser) lookup vielleicht noch schnell genug sein, wenn die Tabelle geladen wird bis 200% (so haben Sie doppelt so viele Punkte wie Kapazität).In diesem Fall können Sie halten Statistiken, wie groß die größten sortierte Tabelle ist, und wenn es größer als, sagen wir, 8 Einträge, Sie denken, das ist zu langsam und dann re-hash.

Re-hashing ist sehr langsam, so sollte es vermieden werden, so oft wie möglich.So wenn Sie brauchen, um re-hash, nicht nur mehr Kapazität zu wenig, sonst, Sie haben zu re-hash wieder sehr schnell, wenn das hinzufügen von mehr Einzelteile.So, wenn Sie benötigen, um re-hash, stellen Sie die Kapazität deutlich größer als die Anzahl der Elemente, die derzeit in der Tabelle, alles andere ist zu wenig Kapazität.

Answer 2

In der Regel, Sie schauen Sie sich für die Auslastung (informell, Sie haben schon gesagt, dass), die ist formal definiert als α = n / N, d.h.das Verhältnis verwendet, um den gesamten Eimer.Um für eine hash-Tabelle, um ordnungsgemäß zu funktionieren (oder zumindest zu Grunde über seine Leistung in mathematischer Hinsicht), sollte es sein, α < 1.

Alles andere ist wirklich bis zu empirische tests:Wenn Sie sehen, dass Ihre hash-Tabelle nicht gut ab α > 0,5 ist, dann sicher sein, zu bleiben unter diesem Wert.Dieser Wert hängt auch von Ihrer Kollision Auflösung techique.Hashing mit Verkettung erfordert möglicherweise andere Belastungsfaktoren als hashing mit offener Adressierung.Ein weiterer Faktor ist die cache-Lokalität.Wenn Ihre Tabelle zu groß, passt es nicht in den Arbeitsspeicher.Da Ihr Zugang in die Reihe zufällig ist, laden aus dem cache kann zu einem Engpass werden.

Answer 3

Es gibt in der Regel zwei Arten von Hashtabellen:zum öffnen und schließen.

In einem offenen hashtable finden Sie den richtigen Eimer, basierend auf der hash, und erstellen Sie dann eine Liste der Elemente hängen aus, die Eimer.

In einem geschlossenen hashtable finden Sie den ersten Eimer mit dem hash-Wert, und wenn es besetzt ist Sie probe für den nächsten Wert.In der simplen Fall können Sie dies tun durch die Suche nach dem nächsten freien Eimer, oder Sie erstellen einen zweiten hash-Wert, aus Ihrem Element, und Schritt durch die (allerdings müssen Sie sicherstellen, dass diese ist eine Primzahl modulo der hash-Tabellen-Größe, so dass Sie besuchen alle den Eimer).

Eine offene hashtable-in der Regel nicht in der Größe verändert.Legen Sie die Anfangsgröße für das sein, was Sie fühlen, ist es sinnvoll, für das problem.Wie andere haben darauf hingewiesen, Sie könnte die Größe ändern auf eine offene Hashtabelle, aber die Argumentation über die Leistung dieser Datenstruktur wird jetzt sehr hart.Wenn Sie die Größe, wenn die Länge des gegebenen Eimer ist L dann könnte am Ende der Größenänderung nur auf L-Elemente in der ganzen hashtable, das ist sehr ineffizient.

Eine geschlossene Hashtabelle geändert werden, wenn die Auslastung (keine.der Elemente in der hashtable / Nein.der Eimer) hat einige vordefinierte Wert.Ich Neige dazu, verwenden Sie 80% ist, der genaue Wert ist unwahrscheinlich, dass Sie zu kritisch.

Der Vorteil eines geschlossenen Hash-Tabelle ist, dass die fortgeführten Kosten für das einfügen eines Elements ist immer O(1) (vorausgesetzt, eine gute hash-Funktion).Einfügen eines bestimmten Artikels möglicherweise O(N) wegen der Kosten für die Größenänderung, aber das ist sehr selten.

Answer 4

Abhängig vom Typ des hash-Tabelle, die Sie erstellen.Wenn Sie eine Feste array-basierte hash-Tabelle (im Gegensatz zu verlinkten Listen für Eimer), sollten Sie die Größe des Arrays entweder, wenn die Tabelle voll ist oder wenn Sie getroffen haben ein max-Sonde Anzahl (je nachdem, ob Sie kümmern sich mehr um Geschwindigkeit oder Speicher).Wenn Sie mit verknüpften Listen, Speicher ist nicht, wie viel von einer Besorgnis, da und sind nicht an die Sonde für die leeren Räume, so dass die Größenänderung ist nicht so groß von einem deal.

Der Schlüssel mit dem hash-Tabellen ist die hashing-Algorithmus, nicht die Anzahl der buckets.Im Idealfall, Sie wollen immer am meisten ein Element in jeder Gruppe, so sollten Sie idealerweise auch die Größe, wenn die Anzahl der Elemente in der hash-Tabelle = die Anzahl der Perioden.Wenn Ihre Daten nicht gleichmäßig verteilt, Sie sind besser mit einer besseren hash-Algorithmus als eine bessere Größe Strategie.

Answer 5

Wenn Sie Linear Hashing, die Tabelle selbst kümmert sich automatisch um eine Größenänderung durch die Aufrechterhaltung einer Konstanten Belastung.