From 1a7efd92e7caee5dc6493190ba0915dfd88fa7bb Mon Sep 17 00:00:00 2001
From: Martin Kagamino Lehoux <martin@lehoux.net>
Date: Wed, 8 Apr 2026 14:41:33 +0200
Subject: Benchmark framework

---
 hash_distribution.py | 93 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 93 insertions(+)
 create mode 100644 hash_distribution.py

(limited to 'hash_distribution.py')

diff --git a/hash_distribution.py b/hash_distribution.py
new file mode 100644
index 0000000..7fe633a
--- /dev/null
+++ b/hash_distribution.py
@@ -0,0 +1,93 @@
+"""Analyze distribution quality of a polynomial rolling hash function."""
+
+import math
+import random
+import string
+from collections import Counter
+
+
+MAX_BUCKETS = 1000
+MULTIPLIER = 31
+
+
+def hashstring(s: str) -> int:
+    h = 0
+    for c in s:
+        h = h * MULTIPLIER + ord(c)
+    return h % MAX_BUCKETS
+
+
+def chi_squared(counts: list[int], n_samples: int) -> float:
+    """Chi-squared statistic vs uniform distribution."""
+    expected = n_samples / MAX_BUCKETS
+    return sum((c - expected) ** 2 / expected for c in counts)
+
+
+def generate_words(n: int) -> list[str]:
+    """Random lowercase alpha strings of length 3-10."""
+    rng = random.Random(42)
+    return [
+        "".join(rng.choices(string.ascii_lowercase, k=rng.randint(3, 10)))
+        for _ in range(n)
+    ]
+
+
+def analyze(label: str, keys: list[str]) -> None:
+    buckets = Counter(hashstring(k) for k in keys)
+    counts = [buckets.get(i, 0) for i in range(MAX_BUCKETS)]
+
+    filled = sum(1 for c in counts if c > 0)
+    max_count = max(counts)
+    min_count = min(counts)
+    mean = len(keys) / MAX_BUCKETS
+    variance = sum((c - mean) ** 2 for c in counts) / MAX_BUCKETS
+    std_dev = math.sqrt(variance)
+    chi2 = chi_squared(counts, len(keys))
+    # Degrees of freedom = MAX_BUCKETS - 1 = 999
+    # chi2 critical value at p=0.05 is approx 1073.6
+    chi2_critical = 1073.6
+
+    print(f"\n=== {label} ({len(keys)} keys) ===")
+    print(
+        f"  Filled buckets : {filled} / {MAX_BUCKETS} ({100 * filled / MAX_BUCKETS:.1f}%)"
+    )
+    print(f"  Min / Mean / Max count : {min_count} / {mean:.2f} / {max_count}")
+    print(f"  Std dev : {std_dev:.3f}  (ideal ≈ {math.sqrt(mean):.3f})")
+    print(f"  Chi² : {chi2:.1f}  (critical at p=0.05: {chi2_critical})")
+    print(f"  Verdict: {'GOOD' if chi2 < chi2_critical else 'POOR'} distribution")
+
+    # Simple ASCII histogram of top/bottom 5 buckets
+    top5 = sorted(range(MAX_BUCKETS), key=lambda i: -counts[i])[:5]
+    print("  Top-5 hottest buckets:")
+    for b in top5:
+        bar = "#" * min(counts[b], 60)
+        print(f"    bucket {b:4d}: {counts[b]:4d}  {bar}")
+
+
+def sequential_integers(n: int) -> list[str]:
+    return [str(i) for i in range(n)]
+
+
+def short_keys(n: int) -> list[str]:
+    """Single-character and two-character keys to expose low-entropy edge cases."""
+    keys: list[str] = []
+    for c in string.ascii_lowercase:
+        keys.append(c)
+    for a in string.ascii_lowercase:
+        for b in string.ascii_lowercase:
+            keys.append(a + b)
+            if len(keys) >= n:
+                return keys
+    return keys
+
+
+def main() -> None:
+    print(f"Hash parameters: MAX_BUCKETS={MAX_BUCKETS}, MULTIPLIER={MULTIPLIER}")
+
+    analyze("Random strings", generate_words(10_000))
+    analyze("Sequential integers", sequential_integers(10_000))
+    analyze("Short keys (1-2 chars)", short_keys(700))
+
+
+if __name__ == "__main__":
+    main()
-- 
cgit v1.3