1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
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()
|
