Erwartete Hash-Kollisionen

Wenn n verschiedene Schlüssel gleichmäßig auf m Fächer verteilt werden, teilen sich einige einen Platz schon bei mäßigem Auslastungsfaktor. Die Intuition unterschätzt die Belegung: man erinnert sich an die Wahrscheinlichkeit des Geburtstagsparadoxons, dass mindestens ein Paar kollidiert, und behandelt diese Wahrscheinlichkeit, als wäre sie eine Anzahl. Dieser Rechner für erwartete Hash-Kollisionen beantwortet eine andere Planungsfrage. Er nutzt das klassische Kugeln-in-Urnen-Modell — jedes Element wählt eines von m Fächern unabhängig und gleichmäßig — und liefert die erwartete Zahl kollidierender Schlüssel, also jener, die in ihrem Fach nicht allein sind. Neben dieser Leitkennzahl meldet er Singleton-Schlüssel, belegte und leere Fächer, Überlaufschlüssel jenseits des ersten Insassen, paarweise Kollisionen und den Auslastungsfaktor n geteilt durch m. Die Arithmetik ist eine geschlossene Identität im Logarithmusraum, vollständig deterministisch, ohne Monte-Carlo-Stichprobe und ohne Sprachmodell. Nutzen Sie ihn, um eine Hashtabelle zu dimensionieren, einen Auslastungsfaktor zu justieren, einen 32-Bit-Hashraum mit einem engeren zu vergleichen oder eine Lehrbuchbehauptung zur Belegung zu prüfen, bevor Sie Speicher festlegen.

Was erwartete kollidierende Schlüssel im Kugeln-in-Urnen-Modell messen

Werfen Sie n Kugeln unabhängig und gleichmäßig in m Urnen und Sie haben das Standardmodell eines gleichmäßigen Hashs. Ein kollidierender Schlüssel ist eine Kugel, die ihre Urne mit mindestens einer anderen teilt. Das ist nicht dieselbe Größe wie die Wahrscheinlichkeit des Geburtstagsparadoxons, dass mindestens zwei Kugeln eine Urne teilen, und nicht die Zahl paarweiser Treffer.

Für die Kapazitätsplanung will man gewöhnlich eine Anzahl: wie viele Schlüssel im Mittel keinen privaten Platz bekommen, wie viele Fächer leer bleiben, während andere überlaufen, und wie viele Extra-Schlüssel sich auf den ersten Insassen stapeln. Die Linearität des Erwartungswerts liefert klare Antworten ohne Simulation. Fixieren Sie einen beliebigen Schlüssel.

Die übrigen n minus eins verfehlen das Fach dieses Schlüssels mit Wahrscheinlichkeit eins minus eins durch m, sodass die Chance, dass der gewählte Schlüssel ein Singleton ist, (1 − 1/m) hoch n minus eins beträgt. Multiplizieren Sie mit n und Sie haben die erwartete Zahl von Singleton-Schlüsseln. Ziehen Sie von n ab und Sie haben die erwartete Zahl kollidierender Schlüssel: n mal eins minus (1 − 1/m) hoch n minus eins.

Dasselbe Belegungsargument liefert die erwartete Zahl leerer Fächer, m mal (1 − 1/m) hoch n, und damit die der belegten Fächer. Überlaufschlüssel sind die Elemente jenseits des ersten in jedem belegten Fach, gleich n minus belegt. Paarweise Kollisionen entsprechen n über zwei geteilt durch m, weil jedes bestimmte Paar mit Wahrscheinlichkeit eins durch m zusammenfällt.

Der Auslastungsfaktor ist einfach n durch m. Zusammen sagen diese Kennzahlen, ob eine vorgeschlagene Tabelle zu wenig Fächer hat, lediglich beschäftigt ist oder bereits eine Kettenlängensteuer zahlt, die ein größeres m beseitigen würde.

Kapazitätsplanung, Grenzen, Preis und wo die Zahlen sich lohnen

Nutzen Sie das Browser-Werkzeug, wenn Sie eine Tabellengröße wählen, Auslastungsfaktoren vergleichen oder einem Team erklären, warum ein Auslastungsfaktor von eins noch einen großen Anteil von Schlüsseln ein Fach teilen lässt. Erhöhen Sie m, bis erwartete kollidierende Schlüssel oder Überlaufschlüssel unter Ihr Dienstbudget fallen, und behalten Sie etwas Wachstumsspielraum. Stellen Sie das Ergebnis einer Wahrscheinlichkeit des Geburtstagsparadoxons gegenüber, wenn Sie auch die Chance brauchen, dass irgendeine Kollision existiert; diese Wahrscheinlichkeit sättigt nahe eins lange bevor die erwartete Anzahl kollidierender Schlüssel groß wird, weshalb die zwei Werkzeuge verschiedene Tickets beantworten.

Die Ergebnisse sind vollständig deterministisch: dieselben n und m ergeben stets denselben Belegungsvektor, sodass Sie Beispiele in Tests und Lehrmaterial festnageln können. Es gibt kein Sprachmodell, keinen externen Statistikdienst und keine Zufälligkeit. Verdrahten Sie den Endpunkt in Hashtabellen-Tutorien, Cache-Fragment-Planer, Bloom-nahe Belegungsprüfungen oder Programmierinterview-Orakel, wo Sie die exakten Kugeln-in-Urnen-Identitäten Näherungs-Stichprobenhistogrammen vorziehen, die nie ganz zur Ruhe kommen.