Math
Hashes und Fächer
Ein Sortiertisch: Schlüssel als Papieranhänger, ein Schlitten, der jeden hasht und in das Fach mit der Nummer seines Hashes fallen lässt, eine Kollision als zwei verschiedene Schlüssel in einem Fach. Der Hash ist eine benannte Funktion – Summe der Codes, Polynom zur Basis 31, FNV-1a – oder das gleichverteilte Orakel hinter der Geburtstagskurve. Ändern Sie einen Schlüssel, sehen Sie seinen Hash Zeichen für Zeichen, kippen Sie ein Bit und zählen Sie die bewegten Hash-Bits; vergleichen Sie zwei Funktionen auf denselben Schlüsseln.
Was passiert
Dreiundzwanzig Menschen in einem Raum teilen öfter einen Geburtstag als nicht, und dieselbe Arithmetik bemisst eine Hashtabelle. Hier sind die Schlüssel echte Zeichenketten und der Hash eine BENANNTE Funktion: die Summe der Zeichencodes, das Polynom zur Basis 31, FNV-1a – oder das gleichverteilte Orakel, das gar keinen Schlüssel hat und das Modell hinter der Kurve ist. Ein Schlitten auf der Schiene hasht jeden Anhänger und lässt ihn in das Fach seines Index fallen; ein Anhänger, der auf einem anderen landet, ist eine Kollision, und beide Schlüssel bleiben beleuchtet. Das Blatt berechnet den Hash des Probeschlüssels Zeichen für Zeichen, kippt ein Bit des Schlüssels und zählt die bewegten Hash-Bits. Drei Fragen bleiben getrennt: Kollisionen, Gleichverteilung (χ² der Belegungen gegen n/m, Erwartung m − 1) und der Lawineneffekt; ein Histogramm, das auf zufälligen Wörtern gleichmäßig aussieht, ist kein Urteil über die Funktion – geben Sie der Buchstabensumme eine Liste von Anagrammen, und jeder Schlüssel landet in einem Fach. Nichts davon ist kryptographische Stärke.
Gleichungen des Moduls
Gleichungen n Schlüssel gleichmäßig auf m Fächer verteilt P(mindestens eine Kollision) = 1 − Produkt (1 − i/m), EXAKT: n = 23, m = 365 -> 0.50729723432398566; n = 50 -> 0.97037357957798842 erwartete leere Fächer = m·(1 − 1/m)^n EXAKT - nicht das übliche m·e^(−n/m): bei n = m = 100 sind es 36.603234127322921 und 36.787944, und der Unterschied ist sichtbar Schlüssel bis zur ersten Kollision, im Mittel: sqrt(pi·m/2) + 2/3 = 24.611199639354552 für m = 365 (gezählt 24.6767 in 20 000 Läufen) die maximale Belegung bei n = m verhält sich wie ln n / ln ln n - eine ASYMPTOTIK, keine Formel: das gemessene Verhältnis WÄCHST, 1.32 bei m = 64, 1.49 bei 256, 1.55 bei 1024 daher wird es als Einschließung und als monotoner Trend geprüft, nie auf eine Zahl festgelegt gemessen gegen die exakte Kurve (je 20 000 Läufe): n = 10 -> 0.11605 gegenüber 0.11695; n = 23 -> 0.50800 gegenüber 0.50730; n = 70 -> 0.99920 gegenüber 0.99916 benannte Funktionen auf einem Schlüssel k = c₁c₂…c_n (Zeichencodes), alle modulo 2³²: Summe: h = Σ c_i; Basis 31: h ← 31·h + c_i; FNV-1a: h₀ = 2166136261, h ← (h xor c_i)·16777619 Fach = h mod m; das gleichmäßige Orakel zieht das Fach aus dem Startwert und der NUMMER des Schlüssels - es hat keinen Schlüssel Gleichmäßigkeit: χ² = Σ (load_j − n/m)² / (n/m) über die m Fächer; eine gleichmäßige Verteilung ergibt m − 1 ± √(2(m − 1)) Lawineneffekt: Mittel über die Schlüssel von Hamming(h(k), h(k′)), wobei EIN Bit von k umgekehrt wurde; eine ideale Funktion kippt 16 von 32 gemessen (Startwert 20260913, 40 zufällige Wörter in 64 Fächern): FNV-1a 7 Kollisionen, χ² 46.4, Lawineneffekt 14.6; Basis 31: 9, 52.8, 6.2; Summe: 8, 52.8, 2.05; Orakel: 9, 59.2, keine Bits 40 Anagramme eines Wortes unter der Summe: 39 Kollisionen, eine Kette der Länge 40, χ² = 2520 - die Summe kann die Reihenfolge der Buchstaben nicht unterscheiden
