Strutture Hashing-Based

• famiglia di f. hash: H funzioni hash con lo stesso dominio e codominio

• f. hash ideale sse $\forall k \in U, \ h(k)$ vale indipendentemente un valore uniformemente distribuito su [0 … m-1]

• membership problem: T se $y \in S$, $\perp$ altrimenti

  con hash table + collisioni risolte x concatenazione non va benissimo se vogliamo veri positivi e veri negativi

  • approximate membership: si falsi positivi ma non falsi negativi
    • otteniamo $y\not \in S = \perp$ con $P\geq 1-\delta$ ($\delta \rarr 0)$
    • H famiglia universale di f. hash con $m = \frac n \delta$ (grandezza codominio), prendo casualmente una funzione hash e popolo bitvector $|A|=m$ con $1$ se $\exist k \in S$ t.c. $h(k)=i$, 0 altrimenti
    • $A$ richiede $\frac n \delta$ bit

• bloom filter: miglioriamo approx. membership

  • risposta in $O(1)$-time
  • $O(n \log \frac 1 \delta)$ bit
  • ancora possiamo avere falsi positivi