当前位置: 首页 > 面试题库 >

对于小的x,大的y值,有效的HashCode()是什么?

陆俊迈
2023-03-14
问题内容

我正在使用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在此测试中使用,我发生了很多碰撞。
  • 使用质数进行乘法。质数具有有趣的二进制性质,导致乘法更不稳定。

  • 避免使用移位运算符(除非您真的很清楚自己在做什么)。它们在数字的二进制数中插入大量零或一,从而降低了其他运算的波动性,甚至可能缩小您可能的输出数。



 类似资料:
  • 问题内容: 我有点被php / Mysql查询卡住了。我有2张桌子: 我需要这样的输出: 用户_1 = lvl0(因为用户有2分) User_2 = lvl1(因为用户刚达到10分) … User_4 = lvl2(因为用户尚未达到30分) 想你:) 问候。 问题答案: 你可以这样 小提琴 输出

  • 问题内容: 我需要在Seaborn distplot上绘制与某些X值相对应的点,以使它们落在密度曲线上或低于密度曲线。这是来自以下URL的distplot: 从Seaborn网站-distplot示例 因此,例如,在上面显示的曲线图中,我需要以编程方式确定与落在密度曲线上的X值0对应的Y轴值是多少。从图中看来,它大约在0.37左右。如何在我的程序中得到它? 假设可以做到,那么我如何在所示的图中显示

  • 在下面的代码中,我希望减小y轴和x轴值的字体大小。我搜索并找到了以下代码: 假设您想减少数轴的字体大小,请使用以下代码: 假设要减小CategoryAxis的字体大小,请使用以下代码: 但不幸的是,轴的大小并没有减小。我做错什么了吗? 此示例代码:

  • 我有以下功能: 此代码给出了

  • 问题内容: 考虑以下示例: 我不确定Java语言规范中是否有一项规定要加载变量的先前值以便与右侧()进行比较,该变量应按照方括号内的顺序进行计算。 为什么第一个表达式求值,而第二个表达式求值?我本来希望先被评估,然后再与自身()比较并返回。 这个问题与Java表达式中子表达式的求值顺序不同,因为这里绝对不是“子表达式”。需要 加载 它以进行比较,而不是对其进行“评估”。这个问题是特定于Java的,