Dvojitý hash

Když metoda dvojité hodnoty šíření nebo dvojité hashování ( anglické dvojité hashování ) je metoda pro realizaci metody uzavřeného hash . V uzavřených hash postupů, pokusy o přizpůsobení odpadlíci v na hašovací tabulky namísto jejich uložení v buňce (např. Jako seznam). (Otevřené hashovací postupy mohou přiřadit položky dvakrát, a proto je není nutné prozkoumávat.) Upozornění: Stejně jako v hashové tabulce článku v části „Varianty hashovací procedury“ jsou termíny „otevřený“ nebo „uzavřený hash“ použity přesně opačným způsobem.

K tomu používá dvojitý hash sondovací funkci, která zahrnuje sekundární hashovací funkci, např. B. , a který se používá, pokud je index vypočítaný primární hashovací funkcí již obsazený. ${\ displaystyle \; s (j, k): = j \ cdot h '(k)}$${\ displaystyle \; h (k)}$

Plná hash funkce pak čte :, kde j je počet již „vyzkoušených“ indexů, tj. To znamená, že j se zvýší o 1 při každém použití indexu. ${\ displaystyle \; h (k) -s (j, k)}$

Funkce sondování má tvořit permutaci indexů hash tabulky. ${\ displaystyle \; s (j, k)}$

Sekvence hash funkcí, které jsou nyní vytvořeny pomocí a vypadá takto: ${\ displaystyle h}$${\ displaystyle h '}$

${\ displaystyle h_ {j} (k) = (h (k) + h '(k) \ cdot j) ~ {\ bmod {~}} m}$

Cena této metody se blíží ceně ideálního hašování.

Nezávislost hashovacích funkcí

Double hash používá dvě nezávislé hashovací funkce a . Tito jsou voláni nezávislí jestliže pravděpodobnost takzvané dvojité srážky, tj. H. , je menší nebo rovno, a proto minimální, kde je velikost pole. ${\ displaystyle h}$${\ displaystyle h '}$${\ Displaystyle h (k) = h (y) \ země h '(k) = h' (y)}$${\ displaystyle 1 / m ^ {2}}$${\ displaystyle m}$

Příklady

Ukázkové funkce

Velikost pole: m

Indexy: {0; m-1}

Primární hash funkce: ( metoda rozdělení zbytku ) ${\ displaystyle h (k): = k \; {\ bmod {\;}} m}$

Sekundární hash funkce: ${\ displaystyle \; h '(k): = k \; {\ bmod {\;}} (m-2) +1}$

Průzkumná funkce: ${\ displaystyle \; s (j, k): = j \ cdot (k \; {\ bmod {\;}} (m-2) +1)}$

Plná funkce dvojitého hash: ${\ displaystyle \; h_ {j} (k): = (k \; {\ bmod {\;}} m + j \ cdot (k \; {\ bmod {\;}} (m-2) +1 )) {\ bmod {m}}}$

Příklad výpočtu

Velikost pole: m = 7

Funkce hash

${\ displaystyle h (k): = k \; {\ bmod {\;}} 7}$

${\ displaystyle h '(k): = k \; {\ bmod {\;}} 5 + 1}$

Průzkumná funkce

${\ displaystyle h_ {j} (k): = (h (k) + j \ cdot h '(k)) \; {\ bmod {\;}} m}$

Tabulka hash:

Pole vyplněné pomocí hash tabulky a funkce sondy:

Vysvětlení pomocí příkladu : ${\ displaystyle k = 31}$

${\ displaystyle k = 10}$a negenerují kolizi, a proto nepotřebují funkci dvojitého hash . Zde si můžete přečíst index hashovací funkce . vytváří kolizi v poli v místě , což je důvod, proč nyní funkce dvojitého hash s : ${\ displaystyle k = 19}$${\ displaystyle h_ {j}}$${\ displaystyle h}$${\ displaystyle k = 31}$${\ displaystyle 3}$${\ displaystyle h_ {j}}$${\ displaystyle j = 1}$

${\ displaystyle h_ {1} (31) = (h (31) +1 \ cdot h '(31)) \; {\ bmod {\;}} 7 \ ​​equiv (3 + 1 \ cdot 2) \; { \ bmod {\;}} 7 \ ​​ekviv 5 \; {\ bmod {\;}} 7 \ ​​ekviv 5}$

Bod znovu vytvoří kolizi, a proto se volá: ${\ displaystyle 5}$${\ displaystyle h_ {j}}$${\ displaystyle j = 2}$

${\ displaystyle h_ {2} (31) = (h (31) +2 \ cdot h '(31)) \; {\ bmod {\;}} 7 \ ​​equiv (3 + 2 \ cdot 2) \; { \ bmod {\;}} 7 \ ​​ekviv 7 \; {\ bmod {\;}} 7 \ ​​ekviv 0}$

Pozice je prázdná, a tak přijímá obsah . ${\ displaystyle 0}$${\ displaystyle 31}$

webové odkazy

• Uzavřený hash
• Otevřený hash