Math
Hash e cestini
Un tavolo di smistamento: le chiavi sono cartellini di carta, un carrello calcola l’hash di ciascuna e la lascia cadere nel cestino che il suo hash nomina, una collisione sono due chiavi diverse in un solo cestino. L’hash è una funzione con nome – somma dei codici, polinomio in base 31, FNV-1a – oppure l’oracolo uniforme dietro la curva dei compleanni. Modifica una chiave, guarda il suo hash calcolato carattere per carattere, inverti un bit e conta i bit dell’hash che cambiano; confronta due funzioni sulle stesse chiavi.
Cosa succede
Ventitré persone in una stanza condividono un compleanno più spesso che no, e la stessa aritmetica dimensiona una tabella hash. Qui le chiavi sono stringhe vere e l’hash una funzione CON NOME: la somma dei codici dei caratteri, il polinomio in base 31, FNV-1a – oppure l’oracolo uniforme, che non ha alcuna chiave ed è il modello dietro la curva. Un carrello sulla rotaia calcola l’hash di ogni cartellino e lo lascia cadere nel cestino del suo indice; un cartellino che atterra su un altro è una collisione, ed entrambe le chiavi restano accese. Il foglio calcola l’hash della chiave di prova carattere per carattere, inverte un bit della chiave e conta i bit dell’hash che cambiano. Tre domande restano separate: collisioni, uniformità (χ² dei carichi contro n/m, attesa m − 1) e valanga; un istogramma uniforme su parole casuali non è un verdetto sulla funzione – dai alla somma delle lettere una lista di anagrammi e ogni chiave finisce in un solo cestino. Niente di tutto ciò è robustezza crittografica.
Equazioni del modulo
Equazioni n chiavi in m cestini, in modo uniforme P(almeno una collisione) = 1 − prodotto (1 − i/m), ESATTAMENTE: n = 23, m = 365 -> 0.50729723432398566; n = 50 -> 0.97037357957798842 cestini vuoti attesi = m·(1 − 1/m)^n ESATTAMENTE - non il solito m·e^(−n/m): a n = m = 100 valgono 36.603234127322921 e 36.787944, e la differenza si vede chiavi fino alla prima collisione, in media: sqrt(pi·m/2) + 2/3 = 24.611199639354552 per m = 365 (contato 24.6767 su 20 000 esecuzioni) il carico massimo per n = m si comporta come ln n / ln ln n - un ASINTOTICO, non una formula: il rapporto misurato CRESCE, 1.32 per m = 64, 1.49 per 256, 1.55 per 1024 perciò viene verificato come intervallo e come andamento monotono, mai fissato a un numero misurato a confronto con la curva esatta (20 000 esecuzioni ciascuna): n = 10 -> 0.11605 contro 0.11695; n = 23 -> 0.50800 contro 0.50730; n = 70 -> 0.99920 contro 0.99916 funzioni con nome su una chiave k = c₁c₂…c_n (codici dei caratteri), tutto modulo 2³²: somma: h = Σ c_i; base 31: h ← 31·h + c_i; FNV-1a: h₀ = 2166136261, h ← (h xor c_i)·16777619 cestino = h mod m; l'oracolo uniforme estrae il cestino dal seme e dal NUMERO della chiave - non ha alcuna chiave uniformità: χ² = Σ (load_j − n/m)² / (n/m) sugli m cestini; una ripartizione uniforme dà m − 1 ± √(2(m − 1)) effetto valanga: media sulle chiavi di Hamming(h(k), h(k′)) con UN bit di k invertito; una funzione ideale ne muove 16 su 32 misurato (seme 20260913, 40 parole casuali in 64 cestini): FNV-1a 7 collisioni, χ² 46.4, valanga 14.6; base 31: 9, 52.8, 6.2; somma: 8, 52.8, 2.05; oracolo: 9, 59.2, nessun bit 40 anagrammi di una parola con la somma: 39 collisioni, una catena di 40, χ² = 2520 - la somma non distingue l'ordine delle lettere
