In open addressing, when a data item can’t be placed at the index calculated by the hash function, another location in the array is sought.

There are three major methods of open addressing, linear probing, quadratic probing and double hashing. Each of them differ on how the next index is calculated.

Linear Probing

Linear probing is the simplest open addressing scheme. In linear probing when we encounter a cell in which some other data is already present, we simply insert the data in the next available empty cell.

For a given hash value, the indices generated by linear probing are as follows:

H+1, H+2, H+3, H+4, ..., H+k

This method results in primary clustering, and as the cluster grows larger, the search for those items hashing within the cluster becomes less efficient.

Quadratic Probing

Quadratic probing is an attempt to keep clusters from forming. The idea is to probe more widely separated cells, instead of those adjacent to the primary hash site.

In quadratic probing, the distance from the initial probe is the square of the step number

Quadratic Probing

Quadratic probes suffer from a different and more subtle clustering problem. This occurs because all the keys that hash to a particular cell follow the same sequence in trying to find a vacant space.

Double Hashing

In Double Hashing we hash the key a second time, using a different hash function, and use the result as the step size. For a given key the step size remains constant through-out a probe, but it’s different for different keys.

  • It must not be the same as the primary hash function.
  • It must never output a 0 (otherwise, there would be no step; every probe would land on the same cell, and the algorithm would go into an endless loop).

Functions of the following form work very well :

stepSize = constant - (key % constant)

where constant is prime and smaller than the array size.

Table Size a Prime Number

Double hashing requires that the size of the hash table is a prime number.

To see why, imagine a situation in which the table size is not a prime number. For example, suppose the array size is 15 (indices from 0 to 14), and that a particular key hashes to an initial index of 0 and a step size of 5. The probe sequence will be 0, 5, 10, 0, 5, 10, and so on, repeating endlessly. Only these three cells are ever examined, so the algorithm will never find the empty cells that might be waiting at 1, 2, 3, and so on. The algorithm will crash and burn.

Hash Function to Hash Strings

int hashFunc(String string, int arrSize) {

    int hash = 0;

    for (int i=0;i<string.length();i++) {
        char c = string.charAt(i);
        hash += (c - 'a') * Math.pow(27, i);
    }

    return hash % arrSize;
}