2

HashMap を使用して、x、y 値をデカルト平面にマッピングしています。非常に小さな x 値と非常に大きな y 値に対して効果的な HashCode は何でしょうか?

現在私は使用しています：

 public int hashCode() {
    return ((y * 31) ^ x);

 // & Typical x,y values would be, (with many collisions on x):
  [4, 1000001] [9, 1000000] [5, 999996] [6, 999995] [4, 999997] 
  [6, 999997] [6, 1000003] [10, 999994] [8, 999997] [10, 999997] 
  [5, 999999] [4, 999998] [5, 1000003] [2, 1000005] [3, 1000004] 
  [6, 1000000] [3, 1000005]

x、yペアの重複を避けるために、.putメソッドを使用して両方のx、yペアをハッシュマップのキーに挿入しています。それが最も効果的な解決策であるかどうかもわかりません。

4

3 に答える 3

3

時々、知るための最良の方法は、あなたの範囲でいくつかのブルートフォーステストを実行することです。ただし、最終的には、いつでもハッシュ関数を記述して、パフォーマンスが低下した場合に戻って修正することができます。時期尚早の最適化は悪です。それでも、ハッシュをテストするのは簡単です。

このプログラムを実行したところ、衝突は0回でした。

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

public class Testing {

    public static void main(String[] args) {
        int minX = 0;
        int minY = 100000;
        int maxX = 20;
        int maxY = 2000000;

        Map<Integer, Integer> hashToCounts = new HashMap<Integer, Integer>();
        for (int x = minX; x < maxX; x++) {
            for (int y = minY; y < maxY; y++) {
                int hash = hash(x, y);
                Integer count = hashToCounts.get(hash);
                if (count == null)
                    count = 0;
                hashToCounts.put(hash, ++count);
            }
        }

        int totalCollisions = 0;
        for (Entry<Integer, Integer> hashCountEntry : hashToCounts.entrySet())
            if (hashCountEntry.getValue() > 1)
                totalCollisions += hashCountEntry.getValue() - 1;

        System.out.println("Total collisions: " + totalCollisions);
    }

    private static int hash(int x, int y) {
        return 7 + y * 31 + x * 23;
    }
}

そして出力：

総衝突数：0

私の関数はであったことに注意してください7 + y * 31 + x * 23。

もちろん、私の言葉を信じないでください。範囲をいじってデータセットに微調整し、自分で計算してみてください。

あなたの使用(y * 31) ^ xは私に与えました：

総衝突数：475000

そしてちょうど使用するx * y：

総衝突数：20439039

このプログラムはかなりの量のメモリと計算能力を使用できることに注意してください。かなり強力なサーバーで実行しました。ローカルマシンでどのように実行されるかわかりません。

ハッシュのために従うべきいくつかの良いルールは次のとおりです。

  • オペレーターを混同してください。演算子を混在させることで、結果をさらに変化させることができます。このテストで単純x * yに使用すると、非常に多くの衝突が発生しました。
  • 乗算には素数を使用します。素数には興味深い2進数の特性があり、乗算がより不安定になります。
  • シフト演算子の使用は避けてください（自分が何をしているかを本当に理解している場合を除きます）。それらは、数値の2進数に多くのゼロまたは1を挿入し、他の操作の揮発性を減らし、場合によっては出力の可能な数を減らすことさえあります。
于 2012-11-10T02:32:42.747 に答える
0

x * y特に結果が に収まる場合は、うまく機能するようですint。

HashSet を使用できます。これは、内部的にはキーのみを持ち、値を持たない HashMap です。重複を避ける意図がより明確になります。

于 2012-11-10T01:53:30.653 に答える
0

予測するのは難しいです。HashMap は、以下に示す hash() メソッドを使用して再ハッシュを行い、下位 X ビットを取得します。したがって、理想的な世界では、物事をかき立てる hash() メソッドを無視して、最下位ビットを適切に分散する必要があります。

static int hash(int h) {
  // This function ensures that hashCodes that differ only by
  // constant multiples at each bit position have a bounded
  // number of collisions (approximately 8 at default load factor).
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
}

私は通常、非常に単純なものから始めます。たとえば、x^y (または x を何か ^ y だけシフトしたもの、またはその逆) から始めて、HashMap を作成し、衝突が多すぎるかどうかを確認します。

于 2012-11-10T01:56:36.687 に答える