对于小 x、大 y 值，有效的 HashCode() 是什么？

我使用 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 对。也不确定这是否是最有效的解决方案。

有时，最好的了解方法就是对您的范围进行一些强力测试。但最终，您始终可以编写一个哈希函数，如果性能不佳，稍后再返回并修复它。过早的优化是邪恶的。尽管如此，测试哈希还是很容易的。

我运行这个程序并得到 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在这次测试中，我发生了非常多的碰撞。
• 使用质数进行乘法。素数具有有趣的二进制属性，导致乘法更加不稳定。
• 避免使用移位运算符（除非您真的知道自己在做什么）。它们在数字的二进制中插入大量的零或一，减少其他操作的波动性，甚至可能减少可能的输出数量。