双哈希java [英] Double Hashing java

问题描述

  public class HashTable< K，V>实现表< K，V> {
 int idx; 
 PairHolder表[]; 
 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）; （table [index]！= null&& amp; 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）; 
返回绝对值; 
} 
 
 public int hashFunc2（int key）{
 int abs = Math.abs（5-key％5）; 
返回绝对值; 
} 
  

我在使用双重哈希时非常困难。任何帮助完成这个代码来加倍散列会很好。

解决方案

你在做什么不是双重哈希。对于双重散列，您需要两个单独的散列函数，而不是一个散列函数以两种方式处理。你也没有继续探测，直到你找到一个空插槽;你只是假设第二个点将被清空，如果第一个点被占用。你不处理表[col] == null 的情况，或者 hashFunc2（key）== 0 大小写，或 col 超过表格末尾的情况。请参阅维基百科，了解您应该做什么的更具体细节。

如果你想执行双重哈希，你将需要两个哈希函数。 Java只提供一个，所以也许用散列（K key）方法定义一个 Hasher< K> 接口，哈希表的构造函数中有一个哈希函数。然后你的代码可能看起来像

  hash1 = reduce（key.hash（））; 
 hash2 = convertToStep（hasher.hash（key））; 
 while（table [hash1]被另一个键占用）{
 hash1 + = hash2; 
 hash1％= table.length; 
} 
 table [hash1] =键值对; 
  

函数减少索引到表中可能非常简单，但 convertToStep 可能更加微妙。

要找到另一个哈希函数使用Google 字符串哈希并查看出现的选项。许多将会相当复杂，但应该有一些在你能处理的范围内。您需要避免使用散列码Java已经使用了;你需要两个哈希函数，而不是一个有两个名字。

为了正确处理null，最好填写你的表在创建时使用 PairHolder s。您可以在插入项目时填写键和值。

为了确保您的步长始终保证找到空插槽，您需要确保 convertToStep 总是返回步长和表长度的GCD为1的结果。这可能就像总是返回一个奇数并使用两个表大小的幂一样简单。 / p>

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.

解决方案

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.

这篇关于双哈希java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！