4

多数のオブジェクト (オブジェクトのバイト配列に格納された値の一意の組み合わせ) をハッシュマップ (約 280 万オブジェクト) に格納しています。また、ハッシュ コード (32 ビット ハッシュ)、統計的には、少なくとも 1 つの衝突が発生する可能性がほぼ 100% あるのに、まったくないことに非常に驚いています ( http://preshing.com/20110504/hash-collision-probabilities/を参照)。

したがって、衝突を検出するための私のアプローチにバグがあるのか​​ 、それとも非常に幸運なのか疑問に思っています...

マップに格納されている 280 万の値から衝突を検出する方法を次に示します。

HashMap<ShowdownFreqKeysVO, Double> values;
(...fill with 2.8 mlns unique values...)
HashSet<Integer> hashes = new HashSet<>();
for (ShowdownFreqKeysVO key:values.keySet()){
    if (hashes.contains(key.hashCode())) throw new RuntimeException("Duplicate hash for:"+key);
    hashes.add(key.hashCode());
}

そして、ハッシュ値を作成するためのオブジェクトのアプローチは次のとおりです。

public class ShowdownFreqKeysVO {
    //Values for the different parameters
    public byte[] values = new byte[12];

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + Arrays.hashCode(values);
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        ShowdownFreqKeysVO other = (ShowdownFreqKeysVO) obj;
        if (!Arrays.equals(values, other.values))
            return false;
        return true;
    }
}

私が間違っていることについてのアイデア/ヒントは大歓迎です!

ありがとう、トーマス

4

2 に答える 2

5

運なんて信じない

これは、使用するの実装Arrays.hashCodeです

public static int hashCode(int a[]) {
    if (a == null)
        return 0;

    int result = 1;
    for (int element : a)
        result = 31 * result + element;

    return result;
}

値がたまたま 31 より小さい場合、基数 31 の個別の数値のように扱われるため、それぞれの結果は異なる数値になります (今のところオーバーフローを無視する場合)。それらの純粋なハッシュを呼び出しましょう

もちろん31^11、Javaの整数の数よりもはるかに大きいため、大量のオーバーフローが発生します。しかし、31 の累乗と最大整数は「非常に異なる」ため、ほぼランダムな分布ではなく、非常に規則的な一様分布が得られます。

より小さな例を考えてみましょう。配列には 2 つの要素しかなく、それぞれ 0 から 5 の範囲であると仮定します。「純粋なハッシュ」のモジュロ 38 を使用して、0 から 37 の間の「hashCode」を作成しようとしました。その結果、1 つの衝突ではなく、間に小さなギャップがある 5 つの整数のストリークが得られます。

val hashes = for {
  i <- 0 to 4
  j <- 0 to 4
} yield (i * 31 + j) % 38

println(hashes.size) // prints 25
println(hashes.toSet.size) // prints 25

これが数値に起こるかどうかを確認するには、次のようにグラフを作成します。各ハッシュについて、x の最初の 16 ビットと y の次の 16 ビットを取得し、そのドットを黒にします。非常に規則的なパターンが見られると思います。

于 2013-12-21T15:44:08.897 に答える
0

あなたのコードには何も問題はありませんが、リンク先の分析では、hashCodes が均一に分散されており、さまざまなオブジェクトの hashCodes が独立した確率変数であると想定しています。

後者は正しくない可能性があります。オブジェクトが一意である (したがって独立していない) ことはわかっています。おそらく、その特定のブランドの一意性は、hashCode 関数によって保持されます。

于 2013-12-21T15:03:02.597 に答える