Doppio hashing - Double hashing

Il doppio hashing è una tecnica di programmazione del computer utilizzata in combinazione con l'indirizzamento aperto nelle tabelle hash per risolvere le collisioni di hash , utilizzando un hash secondario della chiave come offset quando si verifica una collisione. Il doppio hashing con indirizzamento aperto è una struttura dati classica su una tabella . ${\displaystyle T}$

La tecnica del doppio hashing utilizza un valore hash come indice nella tabella e quindi avanza ripetutamente di un intervallo finché non viene individuato il valore desiderato, viene raggiunta una posizione vuota o è stata eseguita la ricerca nell'intera tabella; ma questo intervallo è impostato da una seconda funzione hash indipendente . A differenza dei metodi alternativi di risoluzione delle collisioni di sondaggio lineare e sondaggio quadratico , l'intervallo dipende dai dati, in modo che i valori mappati nella stessa posizione abbiano sequenze di bucket diverse; questo riduce al minimo le collisioni ripetute e gli effetti del clustering.

Date due funzioni hash casuali, uniformi e indipendenti e , la esima posizione nella sequenza del bucket per il valore in una tabella hash di bucket è: Generalmente, e sono selezionati da un insieme di funzioni hash universali ; è selezionato per avere un intervallo di e per avere un intervallo di . Il doppio hashing approssima una distribuzione casuale; più precisamente, le funzioni hash indipendenti a coppie danno una probabilità che qualsiasi coppia di chiavi segua la stessa sequenza di bucket. ${\displaystyle h_{1}}$${\displaystyle h_{2}}$${\displaystyle i}$${\displaystyle k}$${\displaystyle |T|}$${\displaystyle h(i,k)=(h_{1}(k)+i\cdot h_{2}(k)){\bmod {|}}T|.}$${\displaystyle h_{1}}$${\displaystyle h_{2}}$${\displaystyle h_{1}}$${\displaystyle \{0,|T|-1\}}$${\displaystyle h_{2}}$${\displaystyle \{1,|T|-1\}}$${\displaystyle (n/|T|)^{2}}$

Selezione di h ₂ (k)

La funzione hash secondaria dovrebbe avere diverse caratteristiche: ${\displaystyle h_{2}(k)}$

• non dovrebbe mai produrre un indice pari a zero
• dovrebbe scorrere l'intera tabella
• dovrebbe essere molto veloce da calcolare
• dovrebbe essere indipendente a coppie da ${\displaystyle h_{1}(k)}$
• Le caratteristiche di distribuzione di sono irrilevanti. È analogo a un generatore di numeri casuali.${\displaystyle h_{2}}$
• Tutti sono relativamente primi a | T |.${\displaystyle h_{2}(k)}$

In pratica:

• Se si usa l'hashing della divisione per entrambe le funzioni, i divisori vengono scelti come primi.
• Se la T è una potenza di 2, il primo e l'ultimo requisito sono generalmente soddisfatti facendo restituire sempre un numero dispari. Questo ha l'effetto collaterale di raddoppiare la possibilità di collisione a causa di un bit sprecato.${\displaystyle h_{2}(k)}$

Analisi

Sia il numero di elementi memorizzati in , quindi il fattore di carico è . Cioè, inizia selezionando casualmente, uniformemente e indipendentemente due funzioni hash universali e costruisci una doppia tabella di hashing . Tutti gli elementi vengono inseriti mediante doppio hashing utilizzando e . Data una chiave , la -st posizione dell'hash è calcolata da: ${\displaystyle n}$${\displaystyle T}$${\displaystyle T}$${\displaystyle \alpha =n/|T|}$${\displaystyle h_{1}}$${\displaystyle h_{2}}$${\displaystyle T}$${\displaystyle T}$${\displaystyle h_{1}}$${\displaystyle h_{2}}$${\displaystyle k}$${\displaystyle (i+1)}$

$${\displaystyle h(i,k)=(h_{1}(k)+i\cdot h_{2}(k)){\bmod {|}}T|.}$$

Lascia un fattore di carico fisso . Bradford e Katehakis hanno mostrato che il numero previsto di probe per una ricerca non riuscita in , utilizzando ancora queste funzioni hash inizialmente scelte, è indipendentemente dalla distribuzione degli input. È sufficiente l'indipendenza a coppie delle funzioni hash. ${\displaystyle T}$${\displaystyle \alpha :1>\alpha >0}$${\displaystyle T}$${\displaystyle {\tfrac {1}{1-\alpha }}}$

Come tutte le altre forme di indirizzamento aperto, il doppio hashing diventa lineare man mano che la tabella hash si avvicina alla capacità massima. La solita euristica consiste nel limitare il caricamento della tabella al 75% della capacità. Alla fine, sarà necessario il rimaneggiamento a una dimensione maggiore, come con tutti gli altri schemi di indirizzamento aperti.

varianti

La tesi di dottorato di Peter Dillinger sottolinea che il doppio hashing produce funzioni di hash equivalenti indesiderate quando le funzioni di hash sono trattate come un insieme, come nei filtri Bloom : Se e , allora e gli insiemi di hash sono identici. Ciò rende una collisione doppia rispetto a quella sperata . ${\displaystyle h_{2}(y)=-h_{2}(x)}$${\displaystyle h_{1}(y)=h_{1}(x)+k\cdot h_{2}(x)}$${\displaystyle h(i,y)=h(ki,x)}$${\displaystyle \left\{h(0,x),...,h(k,x)\right\}=\left\{h(0,y),...,h(k,y) \Giusto\}}$${\displaystyle 1/|T|^{2}}$

Esiste inoltre un numero significativo di set di hash per lo più sovrapposti; if e , then , e il confronto di valori hash aggiuntivi (espandendo l'intervallo di ) non è di alcun aiuto. ${\displaystyle h_{2}(y)=h_{2}(x)}$${\displaystyle h1(y)=h1(x)\pm h_{2}(x)}$${\displaystyle h(i,y)=h(i\pm 1,x)}$${\displaystyle i}$

Hashing triplo

L'aggiunta di un termine quadratico (un numero triangolare ) o pari ( triplo hashing ) alla funzione hash migliora in qualche modo la funzione hash ma non risolve questo problema; Se: ${\displaystyle i^{2},}$ ${\displaystyle i(i+1)/2}$${\displaystyle i^{2}\cdot h_{3}(x)}$

${\displaystyle h_{1}(y)=h_{1}(x)+k\cdot h_{2}(x)+k^{2}\cdot h_{3}(x),}$

${\displaystyle h_{2}(y)=-h_{2}(x)-2k\cdot h_{3}(x),}$ e

${\displaystyle h_{3}(y)=h_{3}(x).}$

poi

${\displaystyle {\begin{allineato}h(ki,y)&=h_{1}(y)+(ki)\cdot h_{2}(y)+(ki)^{2}\cdot h_{3 }(y)\\&=h_{1}(y)+(ki)(-h_{2}(x)-2kh_{3}(x))+(ki)^{2}h_{3}( x)\\&=\ldots \\&=h_{1}(x)+kh_{2}(x)+k^{2}h_{3}(x)+(ik)h_{2}(x )+(i^{2}-k^{2})h_{3}(x)\\&=h_{1}(x)+ih_{2}(x)+i^{2}h_{3 }(x)\\&=h(i,x).\\\end{allineato}}}$

Doppio hashing migliorato

L'aggiunta di un termine cubico o (un numero tetraedrico ) risolve il problema, una tecnica nota come doppio hashing avanzato . Questo può essere calcolato in modo efficiente mediante differenziazione diretta : ${\displaystyle i^{3}}$${\displaystyle (i^{3}-i)/6}$

struct key;	/// Opaque
/// Use other data types when needed. (Must be unsigned for guranteed wrapping.)
extern unsigned int h1(struct key const *), h2(struct key const *);

/// Calculate k hash values from two underlying hash functions
/// h1() and h2() using enhanced double hashing.  On return,
///     hashes[i] = h1(x) + i*h2(x) + (i*i*i - i)/6.
/// Takes advantage of automatic wrapping (modular reduction)
/// of unsigned types in C.
void ext_dbl_hash(struct key const *x, unsigned int hashes[], unsigned int n)
{
	unsigned int a = h1(x), b = h2(x), i;

	for (i = 0; i < n; i++) { 
		hashes[i] = a;
		a += b;	// Add quadratic difference to get cubic
		b += i;	// Add linear difference to get quadratic
		       	// i++ adds constant difference to get linear
	}
}

Oltre a correggere il problema della collisione, il doppio hashing avanzato rimuove anche le restrizioni numeriche del doppio hashing sulle proprietà di 's, consentendo l'utilizzo di una funzione di hash simile nella proprietà (ma comunque indipendente da) . ${\displaystyle h_{2}(x)}$${\displaystyle h_{1}}$

Guarda anche

• Hashing del cuculo
• Hashing a 2 scelte

Riferimenti

link esterno

• Come la memorizzazione nella cache influisce sull'hashing di Gregory L. Heileman e Wenbin Luo 2005.
• Animazione tabella hash
• klib una libreria C che include la doppia funzionalità di hashing.