werden gelöschte Einträge im Lastfaktor einer Hash -Tabelle unter Verwendung einer offenen Adressierung gezählt

Question

Bei der Berechnung des Lastfaktors eines Hashtabels mit einer Open-Ad-Address-Array-Implementierung verwende ich:

numberOfKeysInArray/sizeOfArray

Mir kam jedoch ein, da gelöschte Einträge als solche gekennzeichnet werden müssen (um sie von leeren Räumen zu unterscheiden), könnte es sinnvoll sein, diese in die Anzahl der Schlüssel einzubeziehen.

Ich denke, dass die Schätzung der durchschnittlichen Anzahl von Sonden, um einen Eintrag zu finden, gelöschte Einträge zum Lastfaktor zählen sollten, aber das Einfügen eines neuen Schlüssels sollten sie nicht.

Welches ist die richtige Berechnung: einschließlich gelöschter Schlüssel oder nicht?

Answer 1

Nein, per Definition ist der Lastfaktor das Verhältnis der Anzahl der Elemente zu Bucket Array -Größe. Siehe zB Wikipedia oder diese Vortrag.

Es würde auch ein praktisches Problem beim Zählen von geschmierten Einträgen im Lastfaktor geben. Die meisten Implementierungen haben einen maximalen Lastfaktor. Wenn die tatsächliche maximal zulässige Größe übertrifft, wird die Größe der Unterstützung der Array erhöht. Wenn gelöschte Einträge auf einen höheren Lastfaktor gezählt wurden, kann dies zu einer unnötigen Anstieg der Arraygröße für eine fast leere, aber hohe Tabelle des Trümmerinhalts führen.