Dubbel hasning

När metoden med dubbel spridningsvärde eller dubbel hashing ( engelsk dubbel hashing ) är en metod för att förverkliga en sluten hashmetod . I slutna förfaranden hash, görs försök att rymma avhoppare i den hashtabellen stället för att lagra dem i cellen (t ex som en lista). (Öppna hashprocedurer kan tilldela poster två gånger och kräver därför ingen sondering.) Observera: Som det är i artikelns hashtabell under "Varianter av haschproceduren" används termerna "öppen" eller "sluten hashing" i exakt tvärtom.

För att göra detta använder dubbel hashing en sonderingsfunktion som inkluderar en sekundär hash-funktion, t.ex. B. , och som används om indexet som beräknats av den primära hashfunktionen redan är upptagen. ${\ displaystyle \; s (j, k): = j \ cdot h '(k)}$${\ displaystyle \; h (k)}$

Full hash-funktionen läser sedan :, där j är antalet redan "försökta" index, dvs. Detta innebär att j ökas med 1 varje gång ett index redan används. ${\ displaystyle \; h (k) -s (j, k)}$

Sondfunktionen är tänkt att bilda en permutation av indexen för hashtabellen. ${\ displaystyle \; s (j, k)}$

Sekvensen av hashfunktioner som nu bildas med och ser ut så här: ${\ displaystyle h}$${\ displaystyle h '}$

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

Kostnaden för denna metod ligger nära kostnaden för idealisk hasning.

Hashfunktionernas oberoende

Dubbel hashing använder två oberoende hashfunktioner och . Dessa kallas oberoende om sannolikheten för en så kallad dubbelkollision, dvs. H. , är mindre än eller lika med och därför minimal, var är arrayens storlek. ${\ displaystyle h}$${\ displaystyle h '}$${\ displaystyle h (k) = h (y) \ land h '(k) = h' (y)}$${\ displaystyle 1 / m ^ {2}}$${\ displaystyle m}$

Exempel

Exempel på funktioner

Matrisens storlek: m

Index: {0; m-1}

Primär hashfunktion: ( metod för återstoden av divisionen ) ${\ displaystyle h (k): = k \; {\ bmod {\;}} m}$

Sekundär hashfunktion: ${\ displaystyle \; h '(k): = k \; {\ bmod {\;}} (m-2) +1}$

Utforskande funktion: ${\ displaystyle \; s (j, k): = j \ cdot (k \; {\ bmod {\;}} (m-2) +1)}$

Full dubbel hash-funktion: ${\ displaystyle \; h_ {j} (k): = (k \; {\ bmod {\;}} m + j \ cdot (k \; {\ bmod {\;}} (m-2) +1 )) {\ bmod {m}}}$

Beräkningsexempel

Matrisstorlek: m = 7

Hash-funktioner

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

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

Utforskande funktion

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

Hash-bord:

Matrisen fylld med hjälp av hash-tabell och sondfunktion:

Förklaring med exemplet : ${\ displaystyle k = 31}$

${\ displaystyle k = 10}$och generera inte en kollision och behöver därför inte den dubbla hashfunktionen . Indexet för hashfunktionen kan avläsas här. skapar en kollision i matrisen vid punkten , varför du nu använder den dubbla hashfunktionen med : ${\ 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 \ ​​equiv 5 \; {\ bmod {\;}} 7 \ ​​equiv 5}$

Poängen skapar en kollision igen, varför följande nu kallas: ${\ 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 \ ​​equiv 7 \; {\ bmod {\;}} 7 \ ​​equiv 0}$

Anställningen är ledig och får därmed innehållet . ${\ displaystyle 0}$${\ displaystyle 31}$

webb-länkar

• Stängd hashing
• Öppen hashing