0

2つ以上の整数を持つオブジェクトの衝突を最小限に抑えながら、一般的な（そしてパフォーマンスの高い）方法でハッシュコードを実装するにはどうすればよいですか?

更新：多くの人が述べているように、もちろん衝突を完全に排除することはできません（正直なところ、それについては考えていませんでした）。したがって、私の質問は、それを反映するように編集して、適切な方法で衝突を最小限に抑える方法です。

NetBeans の自動生成を使用すると失敗します。例えば：

public class HashCodeTest {
    @Test
    public void testHashCode() {
        int loopCount = 0;
        HashSet<Integer> hashSet = new HashSet<Integer>();
        for (int outer = 0; outer < 18; outer++) {
            for (int inner = 0; inner < 2; inner++) {
                loopCount++;
                hashSet.add(new SimpleClass(inner, outer).hashCode());
            }
        }
        org.junit.Assert.assertEquals(loopCount, hashSet.size());
    }

    private class SimpleClass {
        int int1;
        int int2;

        public SimpleClass(int int1, int int2) {
            this.int1 = int1;
            this.int2 = int2;
        }

        @Override
        public int hashCode() {
            int hash = 5;
            hash = 17 * hash + this.int1;
            hash = 17 * hash + this.int2;
            return hash;
        }
    }
}
4

5 に答える 5

1

一般的な（そしてパフォーマンスの高い）方法で、2 つ以上の整数を持つオブジェクトの衝突なしでハッシュコードを実装できますか。

32 ビット以上 (2 つ以上の整数など) で構成されるものを 32 ビット (1 つの整数) にハッシュする場合、衝突をゼロにすることは技術的に不可能です。

于 2012-04-05T18:57:55.347 に答える
1

これは、Eclipseが自動生成するものです：

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

そして、このコードであなたのテストケースは合格します...

PS: 実装することを忘れないでくださいequals()!

于 2012-04-05T19:01:31.680 に答える
0

ハッシュの衝突を完全になくす方法はありません。あなたのアプローチは、基本的に、衝突を最小限に抑えるために推奨されるものです。

于 2012-04-05T18:57:08.237 に答える
0

他の人が言ったように、衝突をなくすには衝突を最小限に抑えることがより重要です。2 つのバケットに 5 つのアイテムがある場合よりも、1000 のバケットに 5 つのアイテムがある場合に衝突をゼロにする方がはるかに簡単です! また、バケットがたくさんある場合でも、バケットが 1000 の場合と 1001 の場合では、衝突が大きく異なるように見える可能性があります。

注意すべきもう 1 つの点は、指定したハッシュが HashMap が最終的に使用するものでさえない可能性が高いということです。たとえば、OpenJDK HashMap コードを見ると、キーの hashCode がプライベートhashメソッド (そのリンクの 264 行目) によって再ハッシュされることがわかります。そのため、衝突を減らすために慎重に構築されたカスタム ハッシュ関数を (単純な自動生成ではなく) 作成するという問題を抱えている場合は、誰がどのようにそれを使用するかについても理解しておく必要があります。

于 2012-04-05T19:43:59.893 に答える
0

衝突がゼロのハッシュ メソッドを作成することは不可能です。ハッシュ メソッドの考え方は、オブジェクトの大きなセットを取り、それを整数の小さなセットにマッピングすることです。最善の方法は、オブジェクトのサブセット内で発生する衝突の数を最小限に抑えることです。

于 2012-04-05T18:58:18.923 に答える