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表大小的幂。