Esercizio - Hashing perfetto a due livelli su otto chiavi

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 → (hashing perfetto, famiglia $((ax+b)\bmod p)\bmod m$), Momenti e deviazioni - Markov, Chebyshev e mediana randomizzataVar(ΣX_i) = ΣVar + 2ΣCov, e basta l'indipendenza a coppie perché la varianza si sommi. Chebyshev dà code polinomiali (collezionista: P(T ≥ nH_n + cn) ≤ π²/(6c²)); il metodo del secondo momento dà P(X=0) ≤ Var(X)/E[X]². Algoritmo della mediana: campione di n^(3/4) elementi, due estremi d e u a ±√n, ordinamento dei soli elementi tra d e u; fallisce con probabilità ≤ n^(-1/4) ed è Las Vegas con 2n + o(n) confronti.Momenti e deviazioni - Markov, Chebyshev e mediana randomizzata → (disuguaglianza di Markov).

Testo. Si vuole una tabella statica per l'insieme di chiavi $S=\{5,17,29,41,48,62,73,90\}$ con ricerca in due accessi nel caso peggiore. Si usa $p=97$ e la famiglia $h_{a,b}(x)=((ax+b)\bmod97)\bmod m'$ con $a\in[1,96]$, $b\in[0,96]$ ($9312$ funzioni).

1. Primo livello ($m=n=8$ bucket): con $h(x)=((3x+1)\bmod97)\bmod8$ calcolare i bucket e $\sum_in_i^2$. La funzione si accetta se $\sum n_i^2\le4n$?
2. Secondo livello: per ogni bucket con $n_i\ge2$ usare $m_i=n_i^2$ celle e la funzione $h_i(x)=((2x+1)\bmod97)\bmod m_i$; verificare che non ci siano collisioni.
3. Calcolare lo spazio totale e descrivere la ricerca di $73$, di $62$ e di una chiave assente, $100$.
4. Calcolare esattamente (su tutte le $9312$ funzioni) la media di $\sum n_i^2$ al primo livello, confrontarla con il limite $2n-1$, la frazione di funzioni con $\sum n_i^2\ge4n$ e la frazione di funzioni di secondo livello senza collisioni sui due bucket.
5. Per $n=10^6$ quale spazio e quanti tentativi in media garantisce la teoria?

Soluzione

1. Primo livello. Si calcola $3x+1$, poi il resto mod $97$ e mod $8$:

Bucket: $0:\{5,29,48\}$ ($n_0=3$), $2:\{62,73\}$ ($n_2=2$), $3:\{41\}$, $4:\{17\}$, $5:\{90\}$, vuoti $1,6,7$. $\sum n_i^2=9+4+1+1+1=\boxed{16}\le4n=32$: accettata.

2. Secondo livello.

• Bucket $0$, $m_0=9$: $h_0(x)=((2x+1)\bmod97)\bmod9$: $5\to11\to2$; $29\to59\to5$; $48\to97\bmod97=0\to0$. Posizioni $2,5,0$, diverse.
• Bucket $2$, $m_2=4$: $62\to125\bmod97=28\to0$; $73\to147\bmod97=50\to2$. Posizioni $0,2$, diverse.
• Ogni bucket singolo usa $m_i=1$ cella.

3. Spazio e ricerca. Primo livello $8$ celle di puntatori più $9+4+1+1+1=16$ celle di secondo livello (che contengono le chiavi): $\boxed{24}$ celle per $8$ chiavi, cioè $3n$. Ricerca di $73$: $h(73)=2$, si va al bucket $2$ (parametri $2,1$, $m_2=4$), cella $h_2(73)=2$: contiene $73$, trovata. Di $62$: bucket $2$, cella $0$: trovata. Chiave assente $100$: $3\cdot100+1=301\bmod97=10\to10\bmod8=2$, bucket $2$; $h_2(100)=201\bmod97=7\to7\bmod4=3$: cella $3$ vuota, quindi assente. Se la cella fosse occupata si confronterebbe la chiave memorizzata con quella cercata. In ogni caso due accessi: nel caso peggiore, non solo in media.

4. Calcolo esatto sulla famiglia. L'enumerazione delle $9312$ funzioni del primo livello dà: media di $\sum n_i^2$ pari a $\boxed{14{,}49}\le2n-1=15$; nessuna funzione ha $\sum n_i^2\ge32$ (massimo osservato $30$), l'$80{,}1\%$ ha $\sum n_i^2\le16$. Per il secondo livello, sui bucket $\{5,29,48\}$ ($m_i=9$) e $\{62,73\}$ ($m_i=4$) la frazione di funzioni senza collisioni è $\frac{3263}{4656}=0{,}701$ e $\frac{147}{194}=0{,}758$, entrambe $\ge\frac12$ come prevede il limite: coppie in collisione attese $\binom{n_i}2/n_i^2<\frac12$ e Markov. La media di $\sum n_i^2$ è vicina a $15$: $E[\sum n_i^2]=n+2E[C]\le n+2\binom n2\frac1n=2n-1$.

5. $n=10^6$. Il primo livello ha $m=n$ celle e $\sum n_i^2\le4n$ con probabilità $>\frac12$ (Markov su $E\le2n-1$), quindi meno di $2$ tentativi; ogni bucket ha successo con probabilità $>\frac12$ (meno di $2$ tentativi); lo spazio è $\le n+4n=5\cdot10^6$ celle. Il tempo di costruzione atteso è $O(n)$ operazioni di hashing più le ripetizioni (la somma dei costi dei tentativi sui bucket è $O(\sum n_i^2)=O(n)$).

Codice di verifica

from collections import Counter

p = 97
S = [5, 17, 29, 41, 48, 62, 73, 90]
def h(a, b, mm, x): return ((a * x + b) % p) % mm

bucket = Counter(h(3, 1, 8, x) for x in S)
print(dict(bucket), sum(c * c for c in bucket.values()))
print([h(2, 1, 9, x) for x in (5, 29, 48)], [h(2, 1, 4, x) for x in (62, 73)], h(3, 1, 8, 100), h(2, 1, 4, 100))

somme = [sum(c * c for c in Counter(h(a, b, 8, x) for x in S).values())
         for a in range(1, p) for b in range(p)]
print(len(somme), sum(somme) / len(somme), max(somme), sum(s >= 32 for s in somme), sum(s <= 16 for s in somme) / len(somme))

for B, mi in (([5, 29, 48], 9), ([62, 73], 4)):
    ok = sum(len({h(a, b, mi, x) for x in B}) == len(B) for a in range(1, p) for b in range(p))
    print(B, ok, (p - 1) * p, ok / ((p - 1) * p))

Risultato: {0: 3, 4: 1, 3: 1, 2: 2, 5: 1} 16; [2, 5, 0] [0, 2] 2 3; 9312 14.4948... 30 0 0.8011... (funzioni, media, massimo, quante con somma $\ge32$, frazione con somma $\le16$); infine 6526 9312 0.7008... e 7056 9312 0.7577..., cioè le frazioni $\frac{3263}{4656}$ e $\frac{147}{194}$ del punto 4.