Double hashing

When double spread value method or double hashing ( English double hashing ) is a method for realizing a closed hash method . In closed hash procedures, attempts are made to accommodate defectors in the hash table instead of storing them within the cell (e.g. as a list). (Open hash procedures can assign entries twice and therefore do not require any exploration.) Attention: As it is in the article hash table under "Variants of the hash procedure", the terms "open" or "closed hashing" are used in exactly the opposite way.

To do this, double hashing uses a probing function that includes a secondary hash function, e.g. B. , and which is used if the index calculated by the primary hash function is already occupied. ${\displaystyle \;s(j,k):=j\cdot h'(k)}$ ${\displaystyle \;h(k)}$

The full hash function then reads:, where j is the number of already "tried" indices, i. This means that j is increased by 1 every time an index is already used. ${\displaystyle \;h(k)-s(j,k)}$

The probing function is supposed to form a permutation of the indices of the hash table. ${\displaystyle \;s(j,k)}$

The sequence of hash functions that are now formed using and looks like this: ${\displaystyle h}$ ${\displaystyle h'}$

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

The cost of this method is close to the cost of ideal hashing.

Independence of the hash functions

Double hashing uses two independent hash functions and . These are called independent if the probability of a so-called double collision, i.e. H. , is less than or equal to and therefore minimal, where is the size of the array. ${\displaystyle h}$ ${\displaystyle h'}$ ${\displaystyle h(k)=h(y)\land h'(k)=h'(y)}$ ${\displaystyle 1/m^{2}}$ ${\displaystyle m}$

Examples

Example functions

Size of the array: m

Indices: {0; m-1}

Primary hash function: ( division remainder method ) ${\displaystyle h(k):=k\;{\bmod {\;}}m}$

Secondary hash function: ${\displaystyle \;h'(k):=k\;{\bmod {\;}}(m-2)+1}$

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

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

Calculation example

Size of the array: m = 7

Hash functions

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

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

Exploratory function

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

Hash table:

k	10	19th	31	22nd	14th	16
H	3	5	3	1	0	2
H'	1	5	2	3	5	2

The array filled with the help of hash table and probe function:

0	1	2	3	4th	5	6th
31	22nd	16	10	-	19th	14th

Explanation using the example : ${\displaystyle k=31}$

${\displaystyle k=10}$and do not generate a collision and therefore do not need the double hash function . The index of the hash function can be read off here. creates a collision in the array at the point , which is why you now use the double hash function with : ${\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}$

The point creates a collision again, which is why the following is called with: ${\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}$

The position is vacant and thus receives the content . ${\displaystyle 0}$ ${\displaystyle 31}$

Web links

• Closed hashing
• Open hashing