两个具有相同哈希码的不等对象

Question

Hashcode()和equals()的概念是

1)如果两个对象根据equal()相等,则在这两个对象中的每一个上调用hashcode方法应该产生相同的哈希码.

而另一个是

2)如果两个对象根据equal()不相等,则不需要在两个对象中的每一个上调用hashcode方法必须产生不同的值.

我尝试并理解了第一个,这是第一点的代码.

public class Test {
    public static void main(String[] args) {

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(1, 11);
        map.put(4, 11);
        System.out.println(map.hashCode());
        Map<Integer, Integer> map1 = new HashMap<Integer, Integer>();
        map1.put(1, 11);
        map1.put(4, 11);
        System.out.println(map1.hashCode());
        if (map.equals(map1)) {
            System.out.println("equal ");
        }
    }
}

上面的程序为两个不同的对象提供相同的哈希码.

有人可以用一个例子来解释我,根据equals()不同的两个不同对象如何具有相同的哈希码.

Answer 1

2)如果两个对象根据equal()不相等,则不需要在两个对象中的每一个上调用hashcode方法必须产生不同的值.

根据散列函数,2个不同的对象可以具有相同的散列码.但是,两个相同的对象必须在散列时产生相同的结果(除非有人实现了随机数的散列函数,在这种情况下它是无用的)

例如,如果我是哈希整数并且我的哈希函数只是(n % 10)那么数字17和数字27将产生相同的结果.这并不意味着这些数字是相同的.

Answer 2

使用字符串的示例(以下所有字符串的哈希码均为0):

public static void main(String[] args) {
    List<String> list = Arrays.asList("pollinating sandboxes",
                                      "amusement & hemophilias",
                                      "schoolworks = perversive",
                                      "electrolysissweeteners.net",
                                      "constitutionalunstableness.net",
                                      "grinnerslaphappier.org",
                                      "BLEACHINGFEMININELY.NET",
                                      "WWW.BUMRACEGOERS.ORG",
                                      "WWW.RACCOONPRUDENTIALS.NET",
                                      "Microcomputers: the unredeemed lollipop...",
                                      "Incentively, my dear, I don't tessellate a derangement.",
                                      "A person who never yodelled an apology, never preened vocalizing transsexuals.");
    for (String s : list) {
        System.out.println(s.hashCode());
    }
}

(从这篇文章中偷来的).

Answer 3

hashCode()具有32位可能的值.您的对象可以拥有更多,因此您将拥有一些具有相同hashCode的对象,即您无法确保它们是唯一的.

这在有限大小的哈希集合中变得更糟.HashMap的最大容量为1 << 30或大约10亿.这意味着实际上只使用了30位,如果你的集合不使用16+ GB并且只说一千个桶(或技术上1 << 10),那么你真的只有1000个桶.

注意:在HotSpot JVM上,默认的Object.hashCode()永远不会消极,即只有31位,但我不知道为什么.

如果你想生成大量具有相同hashCode的对象,请查看Long.

// from Long
public int hashCode() {
    return (int)(value ^ (value >>> 32));
}

for(long i = Integer.MIN_VALUE; i < Integer.MAX_VALUE;i++) {
    Long l = (i << 32) + i;
    System.out.print(l.hashCode()+" ");
    if (i % 100 == 0)
        System.out.println();
}

这将生成40亿个Long,其hashCode为0.

Answer 4

如果你知道 HashMap 是如何实现的以及它的用途，我就很难理解。哈希图采用大量值，并将它们分成更小的集合（桶），以便更快地检索元素。基本上，您只需要搜索一个存储桶，而不是搜索元素的完整列表。桶位于一个数组中，其中索引是哈希码。每个bucket包含一个具有相同hashcode但不等于()的元素的链表。我认为在 Java 8 中，当存储桶大小变大时，他们转而使用树形图。