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;
}


我在使用双重哈希运算时非常困难。完成此代码以使哈希加倍的任何帮助都将非常有用。

最佳答案

您正在执行的操作不是双重哈希。对于双重哈希,您需要两个单独的哈希函数,而不是一个以两种方式处理的哈希函数。您也不会继续探测,直到找到一个空插槽为止。您只是假设如果第一个位置被占用,第二个位置将为空。您不处理table[col] == null情况,hashFunc2(key) == 0情况或col超出表末尾的情况。有关您应该做什么的更多详细信息,请参见Wikipedia

如果要执行双重哈希,则需要两个哈希函数。 Java仅提供一个,因此也许用Hasher<K>方法定义一个hash(K key)接口,并在哈希表的构造函数中使用一个Hasher。然后您的代码可能看起来像

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;


reduce将哈希散列到表中的索引的功能可能非常简单,但是convertToStep可能更微妙。

要找到另一个要使用的哈希函数,请使用Google string hash并查看出现的选项。许多将相当复杂,但是应该可以处理的范围之内。您将要避免the hash code Java already uses;您需要两个哈希函数,而不是两个名字的哈希函数。

为了正确处理null,最好在创建table时用PairHolder填充。您可以在插入项目时填写键和值。

为确保始终确保步长找到一个空插槽,您需要确保convertToStep始终返回步长GCD和表长度为1的结果。这可能和总是返回一样简单奇数,使用2表大小的幂。

07-24 09:49
查看更多