3

バケットの可変範囲（または必要に応じて素数）のハッシュ関数（重要な場合は文字列）を知っている人はいますか？

基本的に、nが奇数（またはnが小さいため素数）であるn個のバケットに均一に分散するハッシュ関数を探しています。

Java.hashCode()は一様分布を提供しますが、2の累乗に対してのみです。

これは私がこれを主張するいくつかの簡単なテストコードです。

これは理論と工学の中間にあるように思われるので、CSTheoryStackExchangeにクロスポストしました。

4

1 に答える 1

2

バケット長として37を使用してプログラムを実行し、ハッシュ部分を次のように置き換えます

for (String key : keys) {
    int hash = key.hashCode();
    int index = Math.abs(hash % buckets.length);
    buckets[index] = buckets[index] + 1;
}

次の結果につながります。

Bucket 0: 4152
Bucket 1: 2593
Bucket 2: 2703
Bucket 3: 2620
Bucket 4: 2742
Bucket 5: 2647
Bucket 6: 2707
Bucket 7: 2673
Bucket 8: 2664
Bucket 9: 2685
Bucket 10: 2734
Bucket 11: 2708
Bucket 12: 2661
Bucket 13: 2678
Bucket 14: 2681
Bucket 15: 2662
Bucket 16: 2682
Bucket 17: 2667
Bucket 18: 2619
Bucket 19: 2572
Bucket 20: 2608
Bucket 21: 2669
Bucket 22: 2670
Bucket 23: 2629
Bucket 24: 2748
Bucket 25: 2651
Bucket 26: 2618
Bucket 27: 2628
Bucket 28: 2740
Bucket 29: 2608
Bucket 30: 2650
Bucket 31: 2645
Bucket 32: 2687
Bucket 33: 2699
Bucket 34: 2627
Bucket 35: 2715
Bucket 36: 2558
Mean: 2702.7027027027025
Standard Deviation: 245.8085241264752

かなり良さそうです。

の配布をテストしていませんString.hashCode()。キーのhashCodeを使用するHashMapのhash()メソッドが、その容量の一様分布を取得しようとするように設計されている場合、分布をテストしています。これは2の累乗である必要があります。hashCode()すでに十分に分散された値を返す場合は、モジュロを取るだけです。除数として素数を使用すると、良好な分布につながります。

于 2013-02-02T20:31:58.740 に答える