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]

我使用 .put 方法将两个 x,y 对插入到哈希图的键中，以避免任何重复的 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，我有非常多的碰撞。
  • 使用素数进行乘法运算。素数具有有趣的二进制特性，导致乘法更加不稳定。
  • Avoid using shift operators (unless you really know what you're doing). They insert lots of zeroes or ones into the binary of the number, decreasing volatility of other operations and potentially even shrinking your possible number of outputs.
于 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 回答