Rolle des Ladefaktors bei Platzverbrauch eines Hash-Tabelleneintrags Berechnung

Question

Ich lese den Artikel "Rationale for Adding Hash Tables to the C++ Standard Template Library", und ich verstehe nicht, diese scheinbar einfache Aussage:

Mit Hash-Tabellen, um die Menge an zusätzlichen Speichern erforderlich ist abhängig von der Organisation der Tabelle und vom Ladefaktor (dessen Angabe auch von der Organisation abhängt). Der einfachste Fall ist die Organisation namens offene Adressierung, in der alle Einträge in einer einzigen Random-Access-Tabelle gespeichert sind. [...] In diesem Fall ist die Menge an Speicher pro Eintrag M/α.

* M ist die Anzahl der für den Schlüssel und den zugehörigen Wert erforderlichen Bytes, α ist der Ladefaktor.

Warum ist es M/α? Warum ist es nicht einfach M + (Speichermenge für jeden Bucket * insgesamt Buckets)?

Answer 1

Bei der offenen Adressierung haben Sie ein Array fester Größe, in dem die Elemente verteilt sind. Dies ist nur ein einfaches Array mit Platz für Elemente und (optional) einigen Kontrollbits, die geworfen werden, um zu markieren, welche Schlitze voll und welche leer sind.

Nehmen wir an, wir haben eine Tabelle mit s Slots und wollen n Elemente in die Tabelle verteilen. Dies bedeutet, dass α = n/s, die Anzahl der Elemente geteilt durch die Anzahl der Steckplätze. Die Speicherbelegung der gesamten Tabelle ist dann sM, da es Slots gibt und jeder Slot M Bytes verwendet. Wenn wir also den Speicher pro Element berechnen wollen, wollen wir sM/n = M/(n/s) = M/α berechnen, woher kommt die Formel. Intuitiv macht dies Sinn. Wenn Sie ein einzelnes Element in der Tabelle haben, ist der Ladefaktor 1/s und der Gesamtspeicher (Ms) dividiert durch die Anzahl der Elemente (1) ist also Ms. Wenn die Tabelle andererseits voll geladen ist (n = s), dann α = 1 und der Gesamtspeicher (Ms) geteilt durch die Anzahl der Elemente ist gleich M.

Sie sind auf dem richtigen Weg in Ihrer Berechnung, indem Sie auf die Menge von Speicher pro Bucket und multipliziert dies mit der Anzahl der Buckets. Wenn Sie M als die Größe pro Element und s als die Anzahl der Steckplätze betrachten, ergibt sich eine Gesamtplatzbelegung von Ms. (Sie müssen den M-Ausdruck nicht hinzufügen, und Sie erhalten dadurch die falschen Einheiten: M hat Einheiten "Bytes pro Element" und Ms hat Einheiten "Bytes", also sollten sie nicht zusammen addiert werden).