Dvojité hašování - Double hashing

Dvojité hašování je technika počítačového programování používaná ve spojení s otevřeným adresováním v hashovacích tabulkách k řešení kolizí hash , pomocí sekundárního hash klíče jako offsetu, když dojde ke kolizi. Dvojité hašování s otevřeným adresováním je klasická datová struktura na stole . ${\ displaystyle T}$

Technika dvojitého hašování používá jednu hodnotu hash jako index do tabulky a poté opakovaně postupuje vpřed o interval, dokud není nalezena požadovaná hodnota, není dosaženo prázdného místa nebo nebyla prohledána celá tabulka; ale tento interval je nastaven druhou, nezávislou hashovací funkcí . Na rozdíl od alternativních metod kolizního rozlišení lineárního snímání a kvadratického snímání závisí interval na datech, takže hodnoty mapující na stejné místo mají různé sekvence vědra; toto minimalizuje opakované kolize a efekty shlukování.

Vzhledem k tomu, dva náhodné, jednotný a nezávislé hash funkce a je th umístění v kbelíku sledu za úplatu v hash tabulce kbelíky je: Obecně platí, a jsou vybrány ze sady univerzálních hash funkce; je vybrána tak, aby měla rozsah a rozsah . Dvojité hašování přibližuje náhodné rozdělení; přesněji, párově nezávislé hašovací funkce poskytují pravděpodobnost, že jakýkoli pár klíčů bude sledovat stejnou sekvenci segmentů. ${\ 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}}$

Volba h ₂ (k)

Sekundární hashovací funkce by měla mít několik charakteristik: ${\ displaystyle h_ {2} (k)}$

• nikdy by neměl přinést index nula
• měl by procházet celou tabulkou
• výpočet by měl být velmi rychlý
• mělo by být párově nezávislé na ${\ displaystyle h_ {1} (k)}$
• Distribuční charakteristiky jsou irelevantní. Je to analogické s generátorem náhodných čísel.${\ displaystyle h_ {2}}$
• Všechny jsou relativně primární | T |.${\ displaystyle h_ {2} (k)}$

V praxi:

• Pokud je pro obě funkce použito dělení hash, jsou jako primární připraveny dělitelé.
• Pokud T je mocnina 2, první a poslední požadavky jsou obvykle splněny tak, že vždy vrátíme liché číslo. To má vedlejší účinek zdvojnásobení šance na kolizi v důsledku jednoho zbytečného kousku.${\ displaystyle h_ {2} (k)}$

Analýza

Nechť je počet prvků uložených v , pak je faktor zatížení . To znamená, že začněte náhodným, jednotným a nezávislým výběrem dvou univerzálních hashovacích funkcí a sestavte dvojitou hashovací tabulku . Všechny prvky jsou vloženy dvojitým hashováním pomocí a . S ohledem na klíč je umístění -st hash vypočítáno podle: ${\ 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 |.}$$

Mějme pevný koeficient zatížení . Bradford a Katehakis ukázali očekávaný počet sond pro neúspěšné vyhledávání , stále využívající tyto původně zvolené hashovací funkce, bez ohledu na rozdělení vstupů. Stačí nezávislost na hašovacích funkcích. ${\ displaystyle T}$${\ Displaystyle \ alpha: 1> \ alpha> 0}$${\ displaystyle T}$${\ displaystyle {\ tfrac {1} {1- \ alpha}}}$

Stejně jako všechny ostatní formy otevřeného adresování se dvojité hašování stává lineárním, protože se hashovací tabulka blíží maximální kapacitě. Obvyklou heuristikou je omezit načítání stolu na 75% kapacity. Nakonec bude nutné přepracování na větší velikost, stejně jako u všech ostatních schémat otevřeného adresování.

Varianty

Disertační práce Petera Dillingera poukazuje na to, že dvojité hašování vytváří nežádoucí ekvivalentní hashovací funkce, když jsou hashovací funkce považovány za sadu, jako ve filtrech Bloom : If a , then a sady hashů jsou totožné. Díky tomu je srážka dvakrát pravděpodobnější, než se očekávalo . ${\ 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) \že jo\}}$${\ displaystyle 1/| T |^{2}}$

Kromě toho existuje značný počet většinou překrývajících se sad hashů; if a then , a porovnávání dalších hodnot hash (rozšiřování rozsahu ) nepomůže. ${\ 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}$

Trojité hašování

Přidání kvadratického výrazu ( trojúhelníkové číslo ) nebo sudého ( trojité hašování ) do hašovací funkce poněkud zlepší hashovací funkci, ale tento problém nevyřeší; li: ${\ 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),}$ a

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

pak

${\ Displaystyle {\ begin {aligned} 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 {zarovnáno}}}$

Vylepšené dvojité hašování

Přidání krychlového výrazu nebo ( čtyřstěnného čísla ) problém vyřeší, což je technika známá jako vylepšené dvojité hašování . To lze efektivně vypočítat dopředným rozlišováním : ${\ 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
	}
}

Kromě odstranění problému s kolizí vylepšené dvojité hašování také odstraňuje numerická omezení dvojitého hashování vlastností ', což umožňuje použít hashovací funkci podobnou vlastnostem (ale stále nezávislou na) . ${\ displaystyle h_ {2} (x)}$${\ displaystyle h_ {1}}$

Viz také

• Hašování kukačky
• Hashování 2 možností

Reference

externí odkazy

• Jak ukládání do mezipaměti ovlivňuje hashování Gregory L. Heileman a Wenbin Luo 2005.
• Animace tabulky hash
• klib knihovnu C, která obsahuje funkce dvojitého hašování.