Esercizio - Liste di collisione con hash universale e dimensionamento della tabella

Teoria: Hashing randomizzato - famiglie universali, filtri di Bloom e fingerprintHashing con catene e costo atteso 1+alfa; famiglie universali (probabilità di collisione al più 1/m) e costruzione h(x)=((ax+b) mod p) mod m con dimostrazione; hashing perfetto a due livelli (spazio lineare, ricerca O(1) nel caso peggiore); filtri di Bloom: falsi positivi (1-e^(-kn/m))^k e k ottimo (m/n) ln 2; fingerprint di stringhe e numero di bit necessari.Hashing randomizzato - famiglie universali, filtri di Bloom e fingerprint → (catene e costo atteso, lista più lunga), Tabelle hashTabella hash per implementare una mappa: funzione hash = hash code + compression function, bucket array, separate chaining; hash code per numeri e stringhe (polynomial, cyclic shift), division e MAD; load factor, complessità al caso pessimo Theta(n) e medio O(1+lambda), rehashing; esempio svolto con inserimenti e collisioni.Tabelle hash →, Linearità del valore atteso e variabili indicatriciLa linearità $E[X+Y]=E[X]+E[Y]$ vale sempre, anche senza indipendenza; con le variabili indicatrici ($E[I_A]=P(A)$) trasforma un conteggio in una somma di probabilità. Applicazioni: attesa del primo successo $1/p$, collezionista di figurine $nH_n$, punti fissi di una permutazione (media $1$), record (media $H_n$), inversioni ($n(n-1)/4$), attesa condizionata, identità di Wald $E[S_N]=E[N]E[X]$.Linearità del valore atteso e variabili indicatrici →.

Testo. Una tabella hash con liste di collisione ha $m$ bucket e usa $h_{a,b}(x)=((ax+b)\bmod p)\bmod m$ con $p=2^{61}-1$ e $(a,b)$ scelti uniformemente a caso. Si inseriscono $n$ chiavi distinte (qualunque, anche scelte da un avversario che conosce la famiglia ma non $(a,b)$).

1. Con $n=2000$, $m=1000$: calcolare il limite sulla lunghezza attesa della lista che contiene una chiave presente e il numero atteso di coppie di chiavi in collisione. Dare un limite per $P(\text{lista}\ge20)$.
2. Quanto deve essere grande $m$ perché la ricerca riuscita costi in media al più $1{,}5$ confronti e quella non riuscita al più $0{,}5$ (cioè $\alpha\le0{,}5$)?
3. Con $n=m=1000$ dimostrare che con probabilità almeno $\frac34$ la lista più lunga ha meno di $64$ elementi (usando solo l'universalità).
4. Verificare con una simulazione le risposte ai punti 1 e 3 e commentare lo scarto tra il limite del punto 3 e i valori osservati.

Soluzione

1. Lunghezza attesa. Sia $x$ presente. Gli indicatori $I_y=1$ se $h(y)=h(x)$, per $y\in S\setminus\{x\}$ ($1999$ chiavi), hanno $E[I_y]\le\frac1m$ per l'universalità: la lista di $x$ ha in media al più $$1+\frac{n-1}{m}=1+\frac{1999}{1000}=\boxed{2{,}999}$$ elementi (la chiave stessa più i colliders). Senza ipotesi di indipendenza: basta la linearità. Le coppie in collisione attese sono $\binom{2000}2\cdot\frac1{1000}=\frac{1\,999\,000}{1000}=1999$. Per $P(\text{lista}\ge20)$ Markov sulla lunghezza $\ell\ge0$ dà $P(\ell\ge20)\le\frac{2{,}999}{20}=\boxed{0{,}150}$. Con una funzione ideale le altre chiavi nella lista sarebbero $\mathrm{Bin}(1999,\frac1{1000})\approx\mathrm{Poi}(2)$, e servirebbero almeno $19$ altre chiavi: $P(\mathrm{Poi}(2)\ge19)\approx6\cdot10^{-13}$: l'universalità, controllando solo la media e le coppie, non dà code così sottili.

2. Dimensionamento. Ricerca riuscita: $1+\frac{n-1}m\le1{,}5\iff m\ge\frac{1999}{0{,}5}=3998$. Ricerca non riuscita: $\alpha=\frac nm\le0{,}5\iff m\ge4000$. Basta $\boxed{m=4000}$ (con $\alpha=0{,}5$ e costo riuscito $1{,}49975$). Scegliere $m\approx2n$ costa quindi memoria doppia rispetto a $n$, per il costo quasi minimo.

3. Lista più lunga. Se una lista ha $L$ elementi contiene $\binom L2$ coppie in collisione, quindi $$P(\text{lista}\ge L)\le P\Bigl(\#\text{coppie}\ge\tbinom L2\Bigr)\le\frac{E[\#\text{coppie}]}{\binom L2}\le\frac{\binom n2/m}{\binom L2}=\frac{n-1}{L(L-1)}\quad(m=n).$$ Con $n=1000$, $L=64$: $\frac{999}{64\cdot63}=\frac{999}{4032}=\boxed{0{,}248}<\frac14$. Quindi con probabilità $>\frac34$ nessuna lista ha $64$ o più elementi (per $L=2\sqrt n=63{,}2$ è l'ordine $O(\sqrt n)$ del teorema). Altri valori: $L=32$ dà $1{,}007$ (vuoto), $L=45$ dà $0{,}505$.

4. Simulazione. Per ogni prova si scelgono $(a,b)$ a caso e $n$ chiavi casuali a $40$ bit.

• $n=2000$, $m=1000$ ($4000$ prove): lunghezza media della lista della prima chiave $2{,}997$ (limite $2{,}999$), lista più lunga in media $7{,}91$, massimo osservato $13$.
• $n=m=1000$ ($4000$ prove): lunghezza media $1{,}9995$ (limite $1{,}999$), lista più lunga in media $5{,}52$; vale $\ge8$ nello $0{,}9\%$ dei casi e mai $\ge10$.

Il limite $O(\sqrt n)$ (vale $63$ a $n=1000$) è molto pessimista rispetto al valore tipico $5$-$6$, vicino a $\ln n/\ln\ln n=3{,}6$ più costante, che si avrebbe con una funzione completamente casuale (Palline e urne - compleanno, carico massimo e approssimazione di PoissonModello palline e urne (m palline, n urne, scelte indipendenti e uniformi): paradosso del compleanno con soglia sqrt(2 n ln 2), urne vuote attese n e^(-m/n), carico massimo ln n / ln ln n con dimostrazione (first moment e union bound), approssimazione di Poisson con il fattore e sqrt(m), potere delle due scelte (ln ln n / ln 2).Palline e urne - compleanno, carico massimo e approssimazione di Poisson →). Il valore $2{,}999$ è invece quasi esatto: l'universalità basta per il costo medio, non per il caso peggiore.

Codice di verifica

import random
from collections import Counter

P = (1 << 61) - 1

def prova(n, m):
    a, b = random.randrange(1, P), random.randrange(P)
    chiavi = random.sample(range(1 << 40), n)
    cont = Counter(((a * k + b) % P) % m for k in chiavi)
    x = chiavi[0]
    return cont[((a * x + b) % P) % m], max(cont.values())

random.seed(1)
for n, m in ((2000, 1000), (1000, 1000)):
    r = [prova(n, m) for _ in range(4000)]
    print(n, m, sum(x for x, _ in r) / len(r), sum(y for _, y in r) / len(r),
          max(y for _, y in r), 1 + (n - 1) / m)

Risultato (4000 prove con seed(1)): 2000 1000 2.99675 7.91475 13 2.999 e 1000 1000 1.9995 5.52125 9 1.999.