Lastfaktor und Aufwärmen

Der Ladefaktor misst, wie voll eine Hash-Tabelle ist. Wenn der Ladefaktor überschritten wird, erhöhen Sie die Größe der Hash-Tabelle und laden Sie die Einträge neu in eine neue, größere Hash-Tabelle. Dies nennt man Aufwärmen. Der Ladefaktor l (Lambda) misst, wie voll eine Hash-Tabelle ist. Es ist das Verhältnis der Anzahl von
Elemente auf die Größe der Hash-Tabelle, d. h. l = n / N, wobei n die Anzahl der Elemente und N die Anzahl der Stellen in der Hash-Tabelle bezeichnet.

Beachten Sie, dass l Null ist, wenn die Hash-Tabelle leer ist. Für das offene Adressierungsschema liegt l zwischen 0 und 1; l ist 1, wenn die Hash-Tabelle voll ist. Für das separate Verkettungsschema kann l ein beliebiger Wert sein.

Mit zunehmendem l steigt die Wahrscheinlichkeit einer Kollision. Studien zeigen, dass Sie den Lastfaktor unter 0,5 für das offene Adressierungsschema und unter 0,9 für das separate Verkettungsschema halten sollten.

Für die Leistung des Hashings ist es wichtig, den Auslastungsfaktor unter einem bestimmten Schwellenwert zu halten. Bei der Implementierung der Klasse java.util.HashMap in der Java-API wird der Schwellenwert 0,75 verwendet. Immer wenn der Auslastungsfaktor den Schwellenwert überschreitet, müssen Sie die Größe der Hash-Tabelle erhöhen und alle Einträge in der Karte neu aufbereiten in einer neuen, größeren Hash-Tabelle. Beachten Sie, dass Sie die Hash-Funktionen ändern müssen, da sich die Größe der Hash-Tabelle geändert hat. Um die Wahrscheinlichkeit einer erneuten Aufbereitung zu verringern, sollten Sie die Größe der Hash-Tabelle mindestens verdoppeln, da dies kostspielig ist. Selbst bei regelmäßiger Aufbereitung ist Hashing eine effiziente Implementierung für Map.

Das obige ist der detaillierte Inhalt vonLastfaktor und Aufwärmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!