Double hashing - Wikipedia, the free encyclopedia

Double hashing - Wikipedia, the free encyclopedia
Double hashing is a popular collision-resolution technique in open-addressed hash tables. 
Like linear probing, it uses one hash value as a starting point and then repeatedly steps forward an interval until the desired value is located, an empty location is reached, or the entire table has been searched; but this interval is decided using a second, independent hash function (hence the name double hashing). Unlike linear probing and quadratic probing, the interval depends on the data, so that even values mapping to the same location have different bucket sequences; this minimizes repeated collisions and the effects of clustering.
https://leijiangcoding.wordpress.com/2015/04/24/double-hashing/

http://www.sanfoundry.com/java-program-implement-hash-table-with-double-hashing/
For double hashing,one popular choice is f(i)=i·hash2(x).

applying a second hash function to x and probe at a distance hash2(x), 2hash2(x),…, and so on.

The function must never evaluate to zero and all cells can be probed.

Hash2(x) = R − (x mod R), R a prime smaller thanTableSize.

If the table size is not prime, it is possible to run out of alternative locations prematurely. However, if double hashing is correctly implemented,it is almost the same as for a random collision resolution strategy.http://www.sanfoundry.com/java-program-implement-hash-table-with-double-hashing/

public class HashTableWithDoubleHashing {
  private DataItem[] hashArray; 

  private int arraySize;

  private DataItem bufItem; // for deleted items

  HashTableWithDoubleHashing(int size) {
    arraySize = size;
    hashArray = new DataItem[arraySize];
    bufItem = new DataItem(-1);
  }

  public void displayTable() {
    System.out.print("Table: ");
    for (int j = 0; j < arraySize; j++) {
      if (hashArray[j] != null)
        System.out.print(hashArray[j].getKey() + " ");
      else
        System.out.print("** ");
    }
    System.out.println("");
  }

  public int hashFunc1(int key) {
    return key % arraySize;
  }

  public int hashFunc2(int key) {
    return 6 - key % 6;
  }

  public void insert(int key, DataItem item) {
    int hashVal = hashFunc1(key); // hash the key
    int stepSize = hashFunc2(key); // get step size
    // until empty cell or -1
    while (hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {
      hashVal += stepSize; // add the step
      hashVal %= arraySize; // for wraparound
    }
    hashArray[hashVal] = item; // insert item
  }

  public DataItem delete(int key) {
    int hashVal = hashFunc1(key); 
    int stepSize = hashFunc2(key); // get step size

    while (hashArray[hashVal] != null) {
      if (hashArray[hashVal].getKey() == key) {
        DataItem temp = hashArray[hashVal]; // save item
        hashArray[hashVal] = bufItem; // delete item
        return temp; // return item
      }
      hashVal += stepSize; // add the step
      hashVal %= arraySize; // for wraparound
    }
    return null; // can't find item
  }

  public DataItem find(int key) {
    int hashVal = hashFunc1(key); // hash the key
    int stepSize = hashFunc2(key); // get step size

    while (hashArray[hashVal] != null) {
      if (hashArray[hashVal].getKey() == key)
        return hashArray[hashVal]; // yes, return item
      hashVal += stepSize; // add the step
      hashVal %= arraySize; // for wraparound
    }
    return null; // can't find item
  }

Read full article from Double hashing - Wikipedia, the free encyclopedia