Java Map::hashCode()碰撞 - 为什么会发生？

Question

以下代码生成的哈希码相同，有什么想法吗？

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

public class Foo
{
    @SuppressWarnings("unchecked")
    public static void main (String[] args)
    {
        Map map;

        map = new HashMap();

        map.put("campaignId", 4770L);
        map.put("location", "MINI_PROFILE");
        map.put("active", "true");
        map.put("lazy", true);

        System.out.println(map.hashCode());

        map = new HashMap();

        map.put("campaignId", 4936L);
        map.put("location", "MINI_PROFILE");
        map.put("active", "true");
        map.put("lazy", false);

        System.out.println(map.hashCode());


    }
}

结果是：

-1376467648
-1376467648

仅仅更改键名就足以使代码生成两个不同的哈希码。

- Hisham

Answer 1

我怀疑这只是巧合，因为在IT技术中，碰撞是不可避免的。在这种情况下，第一个值中相关的不同位似乎被有效地丢失了。

然而，这并不会有任何影响 - 任何使用哈希码的东西都必须应对碰撞。

编辑：这只是哈希码计算的方式。以下代码展示了正在发生的情况：

import java.util.*;

public class Test
{
    @SuppressWarnings("unchecked")
    public static void main (String[] args)
    {
        AbstractMap.SimpleEntry[] entries = {
            new AbstractMap.SimpleEntry("campaignId", 4770L),
            new AbstractMap.SimpleEntry("campaignId", 4936L),
            new AbstractMap.SimpleEntry("lazy", true),
            new AbstractMap.SimpleEntry("lazy", false)
        };
        for (AbstractMap.SimpleEntry entry : entries) {
            System.out.println(entry + ": " + entry.hashCode());
        }
    }
}

结果：

campaignId=4770: -1318251287
campaignId=4936: -1318251261
lazy=true: 3315643
lazy=false: 3315617

在一对中，第一个映射的哈希值比第二个映射低26，而在另一对中，第一个映射的哈希值比第二个映射高26。

AbstractMap只是将哈希值相加（确保排序无关的一种方法），因此两者最终得到相同的哈希码。

这实际上取决于Boolean.hashCode()，其代码如下：

return value ? 1231 : 1237;

...和Long.hashCode()，它看起来像这样：

return (int)(value ^ (value >>> 32));

在Boolean.hashCode()中，如果你的long值之间仅相差26（或26 * 2^32），则会遇到相同的问题。

- Jon Skeet

Answer 2

我认为这只是一个巧合。根据AbstractMap#hashCode()的Javadoc：

“映射的哈希码被定义为映射的entrySet()视图中每个条目的哈希码之和。”

对于Entry#hashCode()：

“返回此映射条目的哈希码值。 映射条目e的哈希码被定义为：”

 (e.getKey()==null   ? 0 : e.getKey().hashCode()) ^
 (e.getValue()==null ? 0 : e.getValue().hashCode())

因此，地图的哈希码基于地图中包含的键和值。您只是遇到了一个奇怪的情况，即两个地图具有相同的哈希码，但没有明显的原因。

- Vivien Barousse

Answer 3

碰撞是会发生的。实际上，您可以覆盖hashCode()方法，使其始终返回0，对于每个HashMap来说这是正确的（尽管它会使很多结构变得缓慢）。

- gpeche

Answer 4

这不是巧合。

字符串对象在两个地方都是相同的。相同的对象将会有相同的哈希码。

- amit