Double hashing

In the double -scattering value method or double hashing (English double hashing ) is a method for implementing a closed hash method. In closed hashing attempts defector to be accommodated in the hash table, instead of being stored within the cell (for example, as a list ). (Open hashing entries can name twice and do not require probing. ) Note: As it is under " variants of hashing " in the article hash table, the terms " open " or be "closed hashing " in exactly the opposite meaning used.

To implement this, one uses a probe, the double - hash function that includes a secondary hash function, for example, and is applied, if the computed hash function with the primary index is already occupied.

The full hash function is then: where j is the number of already " ausprobierter " Indexes, i.e., that j is incremented each time by 1, when an index is already occupied.

The exploratory function is intended to form a permutation of the indices of the hash table.

The sequence of hash functions that are now being formed by and looks like this:

The cost of this method is close to the cost of a base hashing.

Independence of the hash functions

In the double - hashing two independent hash functions and are applied. These are called independent if the probability of a so-called double collision, that is the same and so is minimal.

Examples

Sample functions

Size of the array: m

Indices: { 0; m- 1}

Primary Hash function: ( division remainder method)

Secondary Hash function:

Exploratory function:

A complete double - hash function:

Example of calculation

Size of the array: m = 7

Hash table:

The filled using hash table and exploratory function array:

Statement on Example 31: Why does the 31 index 0? The 10 and 19 do not need a second hash function ( i = 0), and the index of h1 can be taken directly because the array at the positions 3 and 5 is still available. With a collision occurs, because 3 is already occupied. Now take the second hash function:

The point 5 is also already occupied, so it goes on with i = 2:

The point 0 is free, and thus gets the 31 index 0