Hashing universale - Universal hashing

In matematica e informatica , hashing universale (in un algoritmo randomizzato o struttura di dati) si riferisce alla selezione di una funzione hash a caso da una famiglia di funzioni hash con una certa proprietà matematica (vedi definizione di seguito). Ciò garantisce un basso numero di collisioni in attesa , anche se i dati sono scelti da un avversario. Sono note molte famiglie universali (per l'hashing di interi, vettori, stringhe) e la loro valutazione è spesso molto efficiente. L'hashing universale ha numerosi usi in informatica, ad esempio nelle implementazioni di tabelle hash , algoritmi randomizzati e crittografia .

introduzione

Supponiamo di voler mappare le chiavi di un universo in contenitori (etichettati ). L'algoritmo dovrà gestire alcuni set di dati di chiavi, che non è noto in anticipo. Di solito, l'obiettivo dell'hashing è ottenere un basso numero di collisioni (chiavi da quella terra nello stesso contenitore). Una funzione hash deterministica non può offrire alcuna garanzia in un ambiente contraddittorio se la dimensione di è maggiore di , poiché l'avversario può scegliere di essere precisamente la preimmagine di un bin. Ciò significa che tutte le chiavi di dati finiscono nello stesso cestino, rendendo inutile l'hashing. Inoltre, una funzione di hash deterministica non consente il rimaneggiamento : a volte i dati di input risultano essere dannosi per la funzione di hash (ad esempio ci sono troppe collisioni), quindi si vorrebbe cambiare la funzione di hash. ${\displaystyle U}$${\displaystyle m}$${\displaystyle [m]=\{0,\dots ,m-1\}}$${\displaystyle S\subseteq U}$${\displaystyle |S|=n}$${\displaystyle S}$${\displaystyle U}$${\displaystyle m\cdot n}$${\displaystyle S}$

La soluzione a questi problemi è scegliere una funzione a caso da una famiglia di funzioni hash. Una famiglia di funzioni è detta famiglia universale se, . ${\displaystyle H=\{h:U\to [m]\}}$${\displaystyle \forall x,y\in U,~x\neq y:~~\Pr _{h\in H}[h(x)=h(y)]\leq {\frac {1}{m }}}$

In altre parole, due chiavi qualsiasi dell'universo si scontrano con probabilità al massimo quando la funzione hash viene estratta casualmente da . Questa è esattamente la probabilità di collisione che ci aspetteremmo se la funzione hash assegnasse codici hash veramente casuali a ogni chiave. A volte, la definizione è rilassata per consentire la probabilità di collisione . Questo concetto è stato introdotto da Carter e Wegman nel 1977, ed ha trovato numerose applicazioni in informatica (vedi, ad esempio ). Se abbiamo un limite superiore di sulla probabilità di collisione, diciamo che abbiamo -quasi universalità. ${\displaystyle 1/m}$${\displaystyleh}$${\displaystyle H}$${\displaystyle O(1/m)}$${\displaystyle \epsilon <1}$${\displaystyle\epsilon}$

Molte, ma non tutte, le famiglie universali hanno la seguente proprietà di differenza uniforme più forte :

${\displaystyle \forall x,y\in U,~x\neq y}$, quando viene estratto a caso dalla famiglia , la differenza si distribuisce uniformemente in .${\displaystyleh}$${\displaystyle H}$${\displaystyle h(x)-h(y)~{\bmod {~}}m}$${\displaystyle [m]}$

Nota che la definizione di universalità riguarda solo se , che conta le collisioni. La proprietà della differenza uniforme è più forte. ${\displaystyle h(x)-h(y)=0}$

(Analogamente, una famiglia universale può essere XOR universale se , il valore è distribuito uniformemente in dove è l'esclusiva bit per bit o l'operazione. Ciò è possibile solo se è una potenza di due.) ${\displaystyle \forall x,y\in U,~x\neq y}$${\displaystyle h(x)\oplus h(y)~{\bmod {~}}m}$${\displaystyle [m]}$${\displaystyle \oplus}$${\displaystyle m}$

Una condizione ancora più forte è l' indipendenza a coppie : abbiamo questa proprietà quando abbiamo la probabilità che venga eseguito l' hashing su qualsiasi coppia di valori hash è come se fossero perfettamente casuali: . L'indipendenza a coppie è talvolta chiamata forte universalità. ${\displaystyle \forall x,y\in U,~x\neq y}$${\displaystyle x,y}$${\displaystyle z_{1},z_{2}}$${\displaystyle P(h(x)=z_{1}\land h(y)=z_{2})=1/m^{2}}$

Un'altra proprietà è l'uniformità. Diciamo che una famiglia è uniforme se tutti i valori hash sono ugualmente probabili: per qualsiasi valore hash . L'universalità non implica l'uniformità. Tuttavia, una forte universalità implica uniformità. ${\displaystyle P(h(x)=z)=1/m}$${\displaystyle z}$

Data una famiglia con la proprietà della distanza uniforme, si può produrre una famiglia hash indipendente a coppie o fortemente universale aggiungendo alle funzioni hash una costante casuale uniformemente distribuita con valori . (Analogamente, se è una potenza di due, possiamo ottenere l'indipendenza a coppie da una famiglia hash universale XOR eseguendo un'esclusiva o con una costante casuale uniformemente distribuita.) Poiché uno spostamento di una costante è talvolta irrilevante nelle applicazioni (ad esempio tabelle hash) , a volte non viene fatta un'attenta distinzione tra la proprietà della distanza uniforme e l'indipendenza a coppie. ${\displaystyle [m]}$${\displaystyle m}$

Per alcune applicazioni (come le tabelle hash), è importante che anche i bit meno significativi dei valori hash siano universali. Quando una famiglia è fortemente universale, questo è garantito: se è una famiglia fortemente universale con , allora anche la famiglia fatta delle funzioni per tutti è fortemente universale per . Sfortunatamente, lo stesso non vale per le famiglie (semplicemente) universali. Ad esempio, la famiglia costituita dalla funzione identitaria è chiaramente universale, ma la famiglia costituita dalla funzione non riesce ad essere universale. ${\displaystyle H}$${\displaystyle m=2^{L}}$${\displaystyle h{\bmod {2^{L'}}}}$${\displaystyle h\in H}$${\displaystyle L'\leq L}$${\displaystyle h(x)=x}$${\displaystyle h(x)=x{\bmod {2^{L'}}}}$

UMAC e Poly1305-AES e molti altri codici di autenticazione del messaggio algoritmi sono basati su hashing universale. In tali applicazioni, il software sceglie una nuova funzione hash per ogni messaggio, in base a un nonce univoco per quel messaggio.

Diverse implementazioni di tabelle hash si basano sull'hashing universale. In tali applicazioni, tipicamente il software sceglie una nuova funzione hash solo dopo aver notato che "troppe" chiavi si sono scontrate; fino ad allora, la stessa funzione di hash continua ad essere utilizzata più e più volte. (Alcuni schemi di risoluzione delle collisioni, come l' hashing dinamico perfetto , selezionano una nuova funzione hash ogni volta che si verifica una collisione. Altri schemi di risoluzione delle collisioni, come l' hashing cuculo e l' hashing a scelta 2 , consentono un numero di collisioni prima di selezionare una nuova funzione hash ). Un'indagine sulle funzioni hash universali e fortemente universali più conosciute per numeri interi, vettori e stringhe si trova in.

Garanzie matematiche

Per qualsiasi set di chiavi fisso , l'utilizzo di una famiglia universale garantisce le seguenti proprietà. ${\displaystyle S}$${\displaystyle n}$

1. Per ogni fisso in , il numero previsto di chiavi nel cestino è . Quando si implementano tabelle hash mediante concatenamento , questo numero è proporzionale al tempo di esecuzione previsto di un'operazione che coinvolge la chiave (ad esempio una query, un inserimento o una cancellazione).${\displaystyle x}$${\displaystyle S}$${\displaystyle h(x)}$${\displaystyle n/m}$${\displaystyle x}$
2. Il numero previsto di coppie di chiavi in ​​con quella collisione ( ) è limitato sopra da , che è dell'ordine . Quando il numero di bin, è scelto lineare in (cioè è determinato da una funzione in ), il numero previsto di collisioni è . Quando si esegue l'hashing nei contenitori, non ci sono affatto collisioni con probabilità almeno della metà.${\displaystyle x,y}$${\displaystyle S}$${\displaystyle x\neq y}$${\displaystyle h(x)=h(y)}$${\displaystyle n(n-1)/2m}$${\displaystyle O(n^{2}/m)}$${\displaystyle m}$${\displaystyle n}$${\displaystyle\Omega (n)}$${\displaystyle O(n)}$${\displaystyle n^{2}}$
3. Il numero previsto di chiavi nei contenitori con almeno chiavi è limitato sopra da . Pertanto, se la capacità di ciascun contenitore è limitata a tre volte la dimensione media ( ), il numero totale di chiavi nei contenitori pieni è al massimo . Questo vale solo con una famiglia hash la cui probabilità di collisione è limitata sopra da . Se viene utilizzata una definizione più debole, delimitandola da , questo risultato non è più vero.${\displaystyle}$${\displaystyle 2n/(t-2(n/m)+1)}$${\displaystyle t=3n/m}$${\displaystyle O(m)}$${\displaystyle 1/m}$${\displaystyle O(1/m)}$

Poiché le garanzie di cui sopra valgono per qualsiasi insieme fisso , valgono se l'insieme di dati viene scelto da un avversario. Tuttavia, l'avversario deve effettuare questa scelta prima (o indipendentemente da) della scelta casuale di una funzione hash da parte dell'algoritmo. Se l'avversario può osservare la scelta casuale dell'algoritmo, la casualità non serve a nulla e la situazione è la stessa dell'hashing deterministico. ${\displaystyle S}$

La seconda e la terza garanzia sono generalmente utilizzate insieme al rimaneggiamento . Ad esempio, un algoritmo randomizzato può essere preparato per gestire un certo numero di collisioni. Se osserva troppe collisioni, ne sceglie un'altra a caso dalla famiglia e ripete. L'universalità garantisce che il numero di ripetizioni è una variabile casuale geometrica . ${\displaystyle O(n)}$${\displaystyleh}$

costruzioni

Poiché qualsiasi dato informatico può essere rappresentato come una o più parole macchina, sono generalmente necessarie funzioni di hash per tre tipi di domini: parole macchina ("interi"); vettori a lunghezza fissa di parole macchina; e vettori a lunghezza variabile ("stringhe").

Hashing di interi

Questa sezione si riferisce al caso dell'hashing di interi che si adattano alle parole delle macchine; quindi, operazioni come la moltiplicazione, l'addizione, la divisione, ecc. sono istruzioni economiche a livello di macchina. Lascia che l'universo da hash sia . ${\displaystyle \{0,\dots ,|U|-1\}}$

La proposta originale di Carter e Wegman era quella di scegliere un primo e definire ${\displaystyle p\geq |U|}$

${\displaystyle h_{a,b}(x)=((ax+b)~{\bmod {~}}p)~{\bmod {~}}m}$

dove sono scelti a caso gli interi modulo con . (Questa è una singola iterazione di un generatore congruente lineare .) ${\displaystyle a,b}$${\displaystyle p}$${\displaystyle a\neq 0}$

Per vedere che è una famiglia universale, nota che vale solo quando ${\displaystyle H=\{h_{a,b}\}}$${\displaystyle h(x)=h(y)}$

${\displaystyle ax+b\equiv ay+b+i\cdot m{\pmod {p}}}$

per un numero intero compreso tra e . Poiché , se la loro differenza è diversa da zero e ha modulo inverso . Risolvere per i rendimenti ${\displaystyle i}$${\displaystyle 0}$${\displaystyle (p-1)/m}$${\displaystyle p\geq |U|}$${\displaystyle x\neq y}$${\displaystyle xy}$${\displaystyle p}$${\displaystyle a}$

${\displaystyle a\equiv i\cdot m\cdot (xy)^{-1}{\pmod {p}}}$.

Sono possibili scelte per (poiché è escluso) e, variando nell'intervallo consentito, possibili valori diversi da zero per il lato destro. Quindi la probabilità di collisione è ${\displaystyle p-1}$${\displaystyle a}$${\displaystyle a=0}$${\displaystyle i}$${\displaystyle \lfloor (p-1)/m\rfloor }$

${\displaystyle \lfloor (p-1)/m\rfloor /(p-1)\leq ((p-1)/m)/(p-1)=1/m}$.

Un altro modo per vedere è una famiglia universale è attraverso la nozione di distanza statistica . Scrivi la differenza come ${\displaystyle H}$${\displaystyle h(x)-h(y)}$

${\displaystyle h(x)-h(y)\equiv (a(xy)~{\bmod {~}}p){\pmod {m}}}$.

Poiché è diverso da zero ed è distribuito uniformemente in , ne consegue che anche modulo è distribuito uniformemente in . La distribuzione di è quindi pressoché uniforme, fino a una differenza di probabilità tra i campioni. Di conseguenza, la distanza statistica da una famiglia uniforme è , che diventa trascurabile quando . ${\displaystyle xy}$${\displaystyle a}$${\displaystyle \{1,\dots ,p-1\}}$${\displaystyle a(xy)}$${\displaystyle p}$${\displaystyle \{1,\dots ,p-1\}}$${\displaystyle (h(x)-h(y))~{\bmod {~}}m}$${\displaystyle \pm 1/p}$${\displaystyle O(m/p)}$${\displaystyle p\gg m}$

La famiglia delle funzioni hash più semplici

${\displaystyle h_{a}(x)=(ax~{\bmod {~}}p)~{\bmod {~}}m}$

è solo approssimativamente universale: per tutti . Inoltre, questa analisi è quasi serrata; Carter e Wegman lo dimostrano ogni volta che . ${\displaystyle \Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m}$${\displaystyle x\neq y}$${\displaystyle \Pr\{h_{a}(1)=h_{a}(m+1)\}\geq 2/(m-1)}$${\displaystyle (p-1)~{\bmod {~}}m=1}$

Evitare l'aritmetica modulare

Lo stato dell'arte per l'hashing degli interi è lo schema a turni multipli descritto da Dietzfelbinger et al. nel 1997. Evitando l'aritmetica modulare, questo metodo è molto più facile da implementare e funziona anche molto più velocemente nella pratica (di solito di almeno un fattore quattro). Lo schema presuppone che il numero di bin sia una potenza di due, . Sia il numero di bit in una parola macchina. Quindi le funzioni hash vengono parametrizzate su numeri interi positivi dispari (che rientrano in una parola di bit). Per valutare , moltiplicare per modulo e quindi mantenere i bit di ordine superiore come codice hash. In notazione matematica, questo è ${\displaystyle m=2^{M}}$${\displaystyle w}$${\displaystyle a<2^{w}}$${\displaystyle w}$${\displaystyle h_{a}(x)}$${\displaystyle x}$${\displaystyle a}$${\displaystyle 2^{w}}$${\displaystyle M}$

${\displaystyle h_{a}(x)=(a\cdot x\,\,{\bmod {\,}}2^{w})\,\,\mathrm {div} \,\,2^{ wM}}$

e può essere implementato in linguaggi di programmazione C- like da

${\displaystyle h_{a}(x)=}$ (size_t) (a*x) >> (w-M)

Questo schema non soddisfa la proprietà della differenza uniforme ed è solo -quasi-universale ; per qualsiasi , . ${\displaystyle 2/m}$${\displaystyle x\neq y}$${\displaystyle \Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m}$

Per comprendere il comportamento della funzione hash, si noti che, se e hanno gli stessi bit "M" di ordine più alto, allora ha tutti gli 1 o tutti gli 0 come bit M di ordine più alto (a seconda che sia o sia più grande). Supponiamo che il bit impostato meno significativo di appaia in posizione . Poiché è un intero dispari casuale e gli interi dispari hanno inversi nell'anello , ne consegue che sarà distribuito uniformemente tra gli interi a bit con il bit impostato meno significativo sulla posizione . La probabilità che questi bit siano tutti 0 o tutti 1 è quindi al massimo . D'altra parte, se , allora M bit di ordine superiore di contengono sia 0 che 1, quindi è certo che . Infine, se allora il bit di è 1 e se e solo se anche i bit sono 1, il che accade con probabilità . ${\displaystyle ascia{\bmod {2}}^{w}}$${\displaystyle ay{\bmod {2}}^{w}}$${\displaystyle a(xy){\bmod {2}}^{w}}$${\displaystyle ascia{\bmod {2}}^{w}}$${\displaystyle ay{\bmod {2}}^{w}}$${\displaystyle xy}$${\displaystyle wc}$${\displaystyle a}$ ${\displaystyle Z_{2^{w}}}$${\displaystyle a(xy){\bmod {2}}^{w}}$${\displaystyle w}$${\displaystyle wc}$${\displaystyle 2/2^{M}=2/m}$${\displaystyle c<M}$${\displaystyle a(xy){\bmod {2}}^{w}}$${\displaystyle h(x)\neq h(y)}$${\displaystyle c=M}$${\displaystyle wM}$${\displaystyle a(xy){\bmod {2}}^{w}}$${\displaystyle h_{a}(x)=h_{a}(y)}$${\displaystyle w-1,\ldots ,w-M+1}$${\displaystyle 1/2^{M-1}=2/m}$

Questa analisi è stretta, come può essere mostrato con l'esempio e . Per ottenere una funzione hash veramente 'universale', si può usare lo schema multiplo-aggiungi-shift ${\displaystyle x=2^{wM-2}}$${\displaystyle y=3x}$

${\displaystyle h_{a,b}(x)=((ax+b){\bmod {2}}^{w})\,\mathrm {div} \,2^{wM}}$

che può essere implementato in linguaggi di programmazione simili al C da

${\displaystyle h_{a,b}(x)=}$ (size_t) (a*x+b) >> (w-M)

dove è un intero casuale dispari positivo con ed è un intero casuale non negativo con . Con queste scelte di e , per tutti . Questo differisce leggermente ma in modo importante dalla traduzione errata nel documento inglese. ${\displaystyle a}$${\displaystyle a<2^{w}}$${\displaystyle b}$${\displaystyle b<2^{wM}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle \Pr\{h_{a,b}(x)=h_{a,b}(y)\}\leq 1/m}$${\displaystyle x\not \equiv y{\pmod {2^{w}}}}$

Hashing vettori

Questa sezione riguarda l'hashing di un vettore a lunghezza fissa di parole macchina. Interpreta l'input come un vettore di parole macchina (interi di bit ciascuno). Se è una famiglia universale con la proprietà della differenza uniforme, anche la seguente famiglia (risalente a Carter e Wegman) ha la proprietà della differenza uniforme (e quindi è universale): ${\displaystyle {\bar {x}}=(x_{0},\dots,x_{k-1})}$${\displaystyle k}$${\displaystyle w}$${\displaystyle H}$

${\displaystyle h({\bar {x}})=\left(\sum _{i=0}^{k-1}h_{i}(x_{i})\right)\,{\bmod { ~}}m}$, dove ciascuno è scelto in modo indipendente a caso.${\displaystyle h_{i}\in H}$

Se è una potenza di due, si può sostituire la sommatoria con l'o esclusivo. ${\displaystyle m}$

In pratica, se è disponibile un'aritmetica a precisione doppia, questa viene istanziata con la famiglia di funzioni hash a spostamento multiplo. Inizializza la funzione hash con un vettore di interi dispari casuali su bit ciascuno. Quindi se il numero di bin è per : ${\displaystyle {\bar {a}}=(a_{0},\dots,a_{k-1})}$${\displaystyle 2w}$${\displaystyle m=2^{M}}$${\displaystyle M\leq w}$

${\displaystyle h_{\bar {a}}({\bar {x}})=\left({\big (}\sum _{i=0}^{k-1}x_{i}\cdot a_ {i}{\big )}~{\bmod {~}}2^{2w}\right)\,\,\mathrm {div} \,\,2^{2w-M}}$.

È possibile dimezzare il numero di moltiplicazioni, che in pratica si traduce approssimativamente in una doppia accelerazione. Inizializza la funzione hash con un vettore di interi dispari casuali su bit ciascuno. La seguente famiglia di hash è universale: ${\displaystyle {\bar {a}}=(a_{0},\dots,a_{k-1})}$${\displaystyle 2w}$

${\displaystyle h_{\bar {a}}({\bar {x}})=\left({\Big (}\sum _{i=0}^{\lceil k/2\rceil }(x_{ 2i}+a_{2i})\cdot (x_{2i+1}+a_{2i+1}){\Big )}{\bmod {~}}2^{2w}\right)\,\,\ mathrm {div} \,\,2^{2w-M}}$.

Se non sono disponibili operazioni a doppia precisione, si può interpretare l'input come un vettore di mezze parole ( -bit interi). L'algoritmo utilizzerà quindi le moltiplicazioni, dove era il numero di mezze parole nel vettore. Pertanto, l'algoritmo viene eseguito a una "velocità" di una moltiplicazione per parola di input. ${\displaystyle w/2}$${\displaystyle \lceil k/2\rceil}$${\displaystyle k}$

Lo stesso schema può essere utilizzato anche per l'hashing di interi, interpretando i loro bit come vettori di byte. In questa variante, la tecnica vettoriale è nota come tabulation hashing e fornisce una pratica alternativa agli schemi di hashing universali basati sulla moltiplicazione.

È anche possibile una forte universalità ad alta velocità. Inizializza la funzione hash con un vettore di interi casuali sui bit. Calcolare ${\displaystyle {\bar {a}}=(a_{0},\dots,a_{k})}$${\displaystyle 2w}$

${\displaystyle h_{\bar {a}}({\bar {x}})^{\mathrm {strong} }=(a_{0}+\sum _{i=0}^{k-1}a_ {i+1}x_{i}{\bmod {~}}2^{2w})\,\,\mathrm {div} \,\,2^{w}}$.

Il risultato è fortemente universale sui bit. Sperimentalmente, è stato scoperto che funziona a 0,2 cicli di CPU per byte sui recenti processori Intel per . ${\displaystyle w}$${\displaystyle w=32}$

Hashing stringhe

Questo si riferisce all'hashing di un vettore di parole macchina di dimensioni variabili . Se la lunghezza della stringa può essere delimitata da un numero piccolo, è meglio usare la soluzione vettoriale dall'alto (concettualmente riempiendo il vettore con zeri fino al limite superiore). Lo spazio richiesto è la lunghezza massima della stringa, ma il tempo per valutare è solo la lunghezza di . Finché gli zeri sono vietati nella stringa, lo zero-padding può essere ignorato durante la valutazione della funzione hash senza influire sull'universalità. Nota che se gli zeri sono consentiti nella stringa, allora potrebbe essere meglio aggiungere un carattere fittizio diverso da zero (es. 1) a tutte le stringhe prima del riempimento: questo assicurerà che l'universalità non sia influenzata. ${\displaystyle h(s)}$${\displaystyle}$

Ora supponiamo di voler eseguire l'hash , dove un buon limite non è noto a priori. Una famiglia universale proposta da tratta la stringa come i coefficienti di un polinomio modulo un primo grande. Se , sia un numero primo e definiamo: ${\displaystyle {\bar {x}}=(x_{0},\dots,x_{\ell })}$${\displaystyle \ell}$${\displaystyle x}$${\displaystyle x_{i}\in [u]}$${\displaystyle p\geq \max\{u,m\}}$

${\displaystyle h_{a}({\bar {x}})=h_{\mathrm {int} }\left({\big (}\sum _{i=0}^{\ell }x_{i} \cdot a^{\ell -i}{\big )}{\bmod {~}}p\right)}$, dove è uniformemente casuale e viene scelto casualmente da un dominio intero di mappatura familiare universale .${\displaystyle a\in [p]}$${\displaystyle h_{\mathrm {int} }}$${\displaystyle [p]\mapsto [m]}$

Usando le proprietà dell'aritmetica modulare, sopra può essere calcolato senza produrre grandi numeri per stringhe di grandi dimensioni come segue:

uint hash(String x, int a, int p)
	uint h = INITIAL_VALUE
	for (uint i=0 ; i < x.length ; ++i)
		h = ((h*a) + x[i]) mod p
	return h

Questo rolling hash di Rabin-Karp si basa su un generatore congruenziale lineare . L'algoritmo di cui sopra è anche noto come funzione hash moltiplicativa . In pratica, l' operatore mod e il parametro p possono essere evitati del tutto semplicemente permettendo a integer di traboccare perché è equivalente a mod ( Max-Int-Value + 1) in molti linguaggi di programmazione. La tabella seguente mostra i valori scelti per inizializzare h e a per alcune delle implementazioni più diffuse.

Consideriamo due stringhe e sia la lunghezza di quella più lunga; per l'analisi, la stringa più corta è concettualmente riempita di zeri fino alla lunghezza . Una collisione prima dell'applicazione implica che sia una radice del polinomio con coefficienti . Questo polinomio ha al massimo radici modulo , quindi la probabilità di collisione è al massimo . La probabilità di collisione attraverso il random porta la probabilità di collisione totale a . Quindi, se il numero primo è sufficientemente grande rispetto alla lunghezza delle stringhe con hash, la famiglia è molto vicina all'universale (in distanza statistica ). ${\displaystyle {\bar {x}},{\bar {y}}}$${\displaystyle \ell}$${\displaystyle \ell}$${\displaystyle h_{\mathrm {int} }}$${\displaystyle a}$${\displaystyle {\bar {x}}-{\bar {y}}}$${\displaystyle \ell}$${\displaystyle p}$${\displaystyle \ell /p}$${\displaystyle h_{\mathrm {int} }}$${\displaystyle {\frac {1}{m}}+{\frac {\ell }{p}}}$${\displaystyle p}$

Altre famiglie universali di funzioni hash utilizzate per eseguire l'hashing di stringhe di lunghezza sconosciuta in valori hash di lunghezza fissa includono l' impronta digitale Rabin e il Buzhash .

Evitare l'aritmetica modulare

Per mitigare la penalità computazionale dell'aritmetica modulare, in pratica vengono utilizzati tre trucchi:

1. Si sceglie il numero primo vicino a una potenza di due, come un numero primo di Mersenne . Ciò consente di implementare il modulo aritmetico senza divisione (utilizzando operazioni più veloci come addizioni e spostamenti). Ad esempio, su architetture moderne si può lavorare con , mentre 's sono valori a 32 bit.${\displaystyle p}$${\displaystyle p}$${\displaystyle p=2^{61}-1}$${\displaystyle x_{i}}$
2. Si può applicare l'hashing vettoriale ai blocchi. Ad esempio, si applica l'hashing vettoriale a ciascun blocco di 16 parole della stringa e si applica l'hashing di stringa ai risultati. Poiché l'hashing di stringa più lento viene applicato su un vettore sostanzialmente più piccolo, questo sarà essenzialmente veloce come l'hashing di vettore.${\displaystyle \lceil k/16\rceil}$
3. Si sceglie una potenza di due come divisore, consentendo l' implementazione del modulo aritmetico senza divisione (usando operazioni più veloci di mascheramento dei bit ). La famiglia di funzioni hash di NH adotta questo approccio.${\displaystyle 2^{w}}$

Guarda anche

• Hashing indipendente dal K
• Hashing a rotazione
• Hashing di tabulazione
• Indipendenza minima
• Funzione hash universale unidirezionale
• Sequenza a bassa discrepanza
• Hashing perfetto

Riferimenti

Ulteriori letture

• Knuth, Donald Ervin (1998). L'arte della programmazione informatica, vol. III: Ordinamento e ricerca (3a ed.). Lettura, Messa; Londra: Addison-Wesley. ISBN 0-201-89685-0.

link esterno

• Strutture di dati aperti - Sezione 5.1.1 - Hashing moltiplicativo , Pat Morin