Dubbel hasch - Double hashing

Double hashing är en datorprogrammeringsteknik som används i samband med öppen adressering i hashtabeller för att lösa hashkollisioner , genom att använda en sekundär hash av nyckeln som en förskjutning när en kollision inträffar. Dubbel hash med öppen adressering är en klassisk datastruktur på ett bord . ${\ displaystyle T}$

Dubbelhashningstekniken använder ett hashvärde som ett index i tabellen och kliver sedan upprepade gånger ett intervall tills det önskade värdet har hittats, en tom plats har uppnåtts eller hela tabellen har sökts; men detta intervall bestäms av en andra, oberoende hash -funktion . Till skillnad från de alternativa metoderna för kollisionsupplösning för linjär sondering och kvadratisk sondering beror intervallet på data, så att värden som mappas till samma plats har olika skoptsekvenser; detta minimerar upprepade kollisioner och effekterna av gruppering.

Med tanke på två slumpmässiga, enhetliga och oberoende hashfunktioner och är th -platsen i skopssekvensen för värde i en hashtabell med hinkar: Generellt och väljs från en uppsättning universella hashfunktioner ; väljs för att ha ett intervall på och att ha ett intervall på . Dubbel hasch approximerar en slumpmässig fördelning; mer exakt, parvisa oberoende hashfunktioner ger en sannolikhet för att alla par nycklar kommer att följa samma bucket-sekvens. ${\ 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}}$

Urval av h ₂ (k)

Den sekundära hashfunktionen bör ha flera egenskaper: ${\ displaystyle h_ {2} (k)}$

• det ska aldrig ge ett nollindex
• den ska gå igenom hela bordet
• det ska vara väldigt snabbt att beräkna
• det bör vara parvis oberoende av ${\ displaystyle h_ {1} (k)}$
• Distributionsegenskaperna för är irrelevanta. Det är analogt med en slumptalsgenerator.${\ displaystyle h_ {2}}$
• Alla vara relativt bra för | T |.${\ displaystyle h_ {2} (k)}$

I praktiken:

• Om divisionshashning används för båda funktionerna väljs delarna som primtal.
• Om T är en effekt på 2, uppfylls vanligtvis de första och sista kraven genom att alltid returnera ett udda tal. Detta har en bieffekt av att fördubbla risken för kollision på grund av en bortkastad bit.${\ displaystyle h_ {2} (k)}$

Analys

Låt vara antalet element som lagras i , då är belastningsfaktorn . Det vill säga, börja med att slumpmässigt, enhetligt och självständigt välja två universella hash funktioner och bygga en dubbel hash bord . Alla element sätts in genom dubbel hashning med hjälp av och . Med tanke på en nyckel , det är -St hash plats beräknas genom: ${\ 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 |.}$$

Låt ha fast lastfaktor . Bradford och Katehakis visade det förväntade antalet sonder för en misslyckad sökning i , fortfarande använder dessa ursprungligen valda hash -funktioner, är oberoende av fördelningen av ingångarna. Hashfunktionernas parvisa självständighet räcker. ${\ displaystyle T}$${\ displaystyle \ alpha: 1> \ alpha> 0}$${\ displaystyle T}$${\ displaystyle {\ tfrac {1} {1- \ alpha}}}$

Liksom alla andra former av öppen adressering blir dubbel hashning linjär när hashtabellen närmar sig maximal kapacitet. Den vanliga heuristiken är att begränsa bordslastningen till 75% av kapaciteten. Så småningom kommer rehashing till en större storlek att vara nödvändig, som med alla andra öppna adresseringsscheman.

Varianter

Peter Dillingers doktorsexamen påpekar att dubbel hashning ger oönskade ekvivalenta hashfunktioner när hashfunktionerna behandlas som en uppsättning, som i Bloom -filter : Om och , då och uppsättningarna hashar är identiska. Detta gör en kollision dubbelt så sannolik som man hoppats på . ${\ 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) \höger\}}$${\ displaystyle 1/| T |^{2}}$

Det finns dessutom ett betydande antal mest överlappande hash-uppsättningar; om och då , och att jämföra ytterligare hashvärden (utöka intervallet ) är till ingen hjälp. ${\ 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}$

Trippel hasch

Att lägga till en kvadratisk term (ett triangulärt tal ) eller till och med ( triple hashing ) till hash -funktionen förbättrar hash -funktionen något men åtgärdar inte detta problem; om: ${\ 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),}$ och

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

sedan

${\ displaystyle {\ begin {align} 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 {align}}}$

Förbättrad dubbel hasch

Att lägga till en kubik term eller (ett tetrahedralt tal ) löser problemet, en teknik som kallas förbättrad dubbel hashning . Detta kan beräknas effektivt genom framåtskillnad : ${\ 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
	}
}

Förutom att åtgärda kollisionsproblemet, tar bort dubbel hasch också bort dubbelhashningens numeriska restriktioner för egenskaper, så att en hash-funktion liknande egenskap som (men fortfarande oberoende av) kan användas. ${\ displaystyle h_ {2} (x)}$${\ displaystyle h_ {1}}$

Se även

• Gök hashing
• 2-valshash

Referenser

externa länkar

• How Caching Affects Hashing av Gregory L. Heileman och Wenbin Luo 2005.
• Hash -tabellanimation
• klib ett C -bibliotek som innehåller dubbla haschfunktioner.