Double Hashing java

Question

public class HashTable <K, V> implements Table<K, V>{
int idx;
PairHolder table[];
public HashTable(int size){
    table=new PairHolder[size];
}
public void put(K key, V value) {
    int hVal = key.hashCode();  
    int hashVal = hashFunc1(hVal);
    int stepSize = hashFunc2(hVal);

    while(table[index]!=null&&table[index].getFirst() != null){

        index += temp;
        index %=table.length;
    }
    table[index].value=value;
}
public int hashFunc1(int key){
    int abs = Math.abs(key%table.length);
    return abs;
}

public int hashFunc2(int key){
    int abs = Math.abs(5-key%5);
    return abs;
}

I am having a really hard time with double hashing. Any help to complete this code to double hash would be great.

Answer 1

What you're doing is not double hashing. For double hashing, you need two separate hash functions, not one hash function processed two ways. You're also not continuing the probe until you find an empty slot; you just assume the second spot will be empty if the first one is occupied. You're not handling the table[col] == null case, or the hashFunc2(key) == 0 case, or the case where col is past the end of the table. See Wikipedia for more specific details on what you're supposed to be doing.

If you want to perform double hashing, you will need two hash functions. Java only provides one, so perhaps define a Hasher<K> interface with a hash(K key) method and take a Hasher in the hash table's constructor. Then your code might look something like

hash1 = reduce(key.hash());
hash2 = convertToStep(hasher.hash(key));
while (table[hash1] is occupied by a different key) {
    hash1 += hash2;
    hash1 %= table.length;
}
table[hash1] = key-value pair;

The function to reduce a hash to an index into the table can be pretty simple, but convertToStep may be more subtle.

To find another hash function to use, Google string hash and look at the options that come up. Many will be rather complex, but there should be some within the range of what you can handle. You'll want to avoid the hash code Java already uses; you want two hash functions, not one with two names.

To handle nulls properly, it's probably best to fill your table with PairHolders when you create it. You can fill in keys and values when you insert items.

To ensure that your step size is always guaranteed to find an empty slot, you'll want to make sure convertToStep always returns a result where the GCD of the step and the table length is 1. That may be as simple as always returning an odd number and using power of 2 table sizes.