Lastfaktor einer Hashtabelle berechnen

Dieser Rechner führt die Berechnung aus, vergleicht das Ergebnis mit einem von Ihnen gewählten Schwellenwert und empfiehlt bei Bedarf eine Größenänderung. Zusätzlich ermittelt er die kleinste Bucket-Anzahl, mit der die aktuellen Elemente den Grenzwert sicher unterschreiten. Nutzen Sie das Werkzeug zur Prüfung einer Implementierung, zur Kapazitätsplanung, zur Bewertung eines beobachteten Tabellenzustands oder um eine Resize-Richtlinie in einen wiederholbaren automatisierten Test zu überführen.

Lastfaktor mit konsistenten Zählwerten berechnen

Geben Sie die Zahl der momentan gespeicherten Elemente und die Zahl der zugewiesenen Buckets ein. Der Rechner teilt die Elementanzahl durch die Bucket-Anzahl. 600 Elemente in 800 Buckets ergeben daher einen Lastfaktor von 0.75 beziehungsweise 75%. Zählen Sie logische Einträge und nicht belegte Buckets: Zwei kollidierende Einträge in demselben Bucket gelten weiterhin als zwei Elemente. Verwenden Sie außerdem die tatsächliche Bucket-Kapazität der Tabelle und nicht nur die Zahl der Buckets, die gerade einen Eintrag enthalten. Diese Definitionen müssen konsistent bleiben, denn der Lastfaktor beschreibt die durchschnittlichen Einträge je Bucket und nicht den Anteil nicht leerer Buckets. Die Elementanzahl darf null sein; die Bucket-Anzahl muss jedoch eine positive Ganzzahl sein, da eine Division durch null keinen Tabellenzustand darstellen kann. Berechnen Sie unabhängige Tabellen, Shards oder Partitionen getrennt. Zusammengefasste Werte können eine stark belastete Partition hinter freien Kapazitäten anderer Bereiche verbergen. Der ausgegebene Dezimalwert und Prozentsatz beschreiben dasselbe Verhältnis in Formaten für Programmcode und Berichte.

Schwellenwert für die Größenänderung festlegen

Der Schwellenwert ist der Lastfaktor, bei dem Ihre Richtlinie eine Größenänderung vorsieht. Standardmäßig gilt 0.75; Sie können jedoch jeden endlichen positiven Wert angeben, der zum Tabellenentwurf passt. Tabellen mit offener Adressierung benötigen häufig einen Wert unter 1, weil jedes Element einen Platz belegt und Suchfolgen länger werden, wenn freie Plätze verschwinden. Implementierungen mit separater Verkettung können über 1 arbeiten, da mehrere Elemente einen Bucket teilen dürfen. Dennoch steigen die Kollisionskosten meist mit dem Verhältnis. Der Rechner setzt keine Kollisionsstrategie voraus, sondern wendet Ihren Wert an. Die Grenze wird eingeschlossen: Eine Größenänderung wird empfohlen, wenn der ungerundete Lastfaktor gleich dem Schwellenwert oder größer ist. Für den Vergleich wird der vollständige Wert genutzt; nur die Anzeige wird für eine stabile Ausgabe gerundet. So beeinflusst eine optische Rundung keine grenznahe Entscheidung. Verstehen Sie das Ergebnis als Prüfung einer festgelegten Richtlinie und nicht als Beleg dafür, dass derselbe Grenzwert für jede Arbeitslast, Hashfunktion, Speichergrenze oder Latenzvorgabe optimal wäre.

Aus dem Ergebnis eine Kapazitätsentscheidung ableiten

Wenn eine Größenänderung empfohlen wird, enthält das Ergebnis die mathematisch kleinste Bucket-Anzahl, bei der die vorhandenen Elemente den gewählten Schwellenwert sicher unterschreiten. Dazu wird der Quotient aus Elementanzahl und Schwellenwert abgerundet und anschließend um eins erhöht. Die Ausgabe nennt außerdem die zusätzlich zur aktuellen Zuweisung erforderlichen Buckets. Dieser Wert ist ein richtlinienbezogenes Minimum, aber nicht zwingend die exakte Kapazität für Ihre Implementierung. Viele Hashtabellen wachsen geometrisch und verdoppeln ihre Kapazität; andere verlangen eine Zweierpotenz, eine Primzahl oder eine von einem festen Speicherverfahren unterstützte Größe. Runden Sie das Minimum auf die nächste zulässige Kapazität auf und berücksichtigen Sie erwartete Einfügungen, damit die Tabelle den Grenzwert nicht sofort erneut erreicht. Wird keine Änderung empfohlen, beträgt der Zusatzbedarf null, auch wenn das berechnete Minimum unter der vorhandenen Zuweisung liegt. Verwenden Sie bei Automatisierungen das boolesche Resize-Signal als stabile Bedingung und protokollieren Sie Zählwerte, Schwelle und Faktor. Die deterministische API kostet $0.002 pro Anfrage und nutzt dieselbe Berechnung wie der Browser.