2

文字列に 2 つの異なるユニバーサル ハッシュ関数を実装しようとしています。しかし、ハッシュ値が 0 になることがあるという問題があります。ダブル ハッシュを実装したいので、この関数を実装する必要があるため、ハッシュ関数を使用できません: hash_func1(string s) + i * hash_func2(string s)ハッシュテーブルを通過します。しかし、1 つのハッシュ関数が 0 の場合、何も変わらず、無限ループが発生します。これは、ハッシュ テーブルでの衝突検出用です。そのためには、2 つの異なるユニバーサル ハッシュ関数が必要です。

さまざまなハッシュ関数を試しましたが、機能するものが見つかりません。

誰でもこの問題を解決できますか?

これは私が試した機能の一部です。

int h = 0 , r1 = 31415 , r2 = 27183;
 for (int i =0; i < key.length (); i ++) {
 h = ( r1 * h + key.charAt ( i )) % capacity ;
 r1 = r1 * r2 % (capacity -1);
}
return h ;

またはこれ

int seed = 131; 
long hash = 0;
for(int i = 0; i < key.length(); i++)
{
hash = (hash * seed) + key.charAt(i);
}
return (int) (hash % capacity);
4

1 に答える 1

0

ダブルハッシュに関するウィキペディアの記事では、ハッシュ関数を変更してゼロにならないようにすることを提案しています。これを行う最も簡単な方法は、単に追加すること1です。

int h1 = hash_func1(s);
int h2 = (hash_func2(s) % (capacity - 1)) + 1;

// loop over (h1 + i * h2) % capacity

編集:おっと、 でバインドする必要もあると思いcapacity - 1ます。h2 == capacityhash_func2()capacity - 11

于 2013-05-14T07:12:05.210 に答える