java - Set底层HashMap中的key是什么: hash code or the object itself?

Question

OCP 书中的这句话正确吗？

A HashSet stores its elements in a hash table, which means the keysare a hash and the values are an Object.

我创建了以下代码片段:

class A
{
    private String s;
    public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException  {
        HashSet<A> elems =  new HashSet<>(Set.of(new A("abc"), new A("cba"), new A("a")));
        Field field = elems.getClass().getDeclaredField("map");
        field.setAccessible(true);
        HashMap privateMap = (HashMap) field.get(elems);
    }

    public A(String s)
    {
        this.s = s;
    }
}

结果我检索到了以下 HashMap:

看起来对象本身是 HashMap 中的键，而不是其哈希值。书中是否有错误，或者我是否看到了一些不相关的内容？

Answer 1

当然是对象而不是哈希值。一些单独显而易见或至少易于验证的事实:

• 鉴于哈希值是固定大小的(存在 2^32 个不同的哈希值，仅此而已)，并且存在诸如字符串之类的对象，其存在超过 2^32 个不同的值(数量无限)，因此 < strong>存在不同字符串散列为相同值的数学确定性。如果您更喜欢观看一些视频或类似内容来更详细地解释这个概念，这称为鸽子洞原理。
• 如果 HashMap/HashSet 认为不同的字符串仍然相等只是，因为它们的哈希码碰巧发生冲突，那将是非常烦人的。事实上，这意味着这些类型不符合它们自己的规范 (javadoc)，因为它们明确指出冲突会减慢速度，但在其他方面并不是问题。
• 因此，HashSet/Map 需要原始对象，以便它可以使用 .equals() 来验证事物是否实际上相等。

hashmap/set 的工作方式如下:

• 使用对象的 hashCode 来查找要查找的“存储桶”。
• 然后只需扫描该存储桶中的每个对象，一次一个。是的，这很慢 - 因此您不希望出现大量哈希冲突。

因此得出结论:

• 给定两个对象 a 和 b，如果 a.equals(b) 为 true，则 a.hashCode() == b.hashCode() 必须为 true，否则你不能在 hashset/hashmap 中使用这些对象，因为如果你这样做，就会发生奇怪的事情，而你只使用键/对象添加消失在稀薄的空气中，但在迭代时仍然出现，等等。
• 相反不成立 - 如果a.hashCode() == b.hashCode()为真，则a.equals(b) 不一定是。可能只是一次碰撞，这没关系。
• 理论上这意味着@Override public int hashCode() { return 1; } 有效。它的确是;只要 equals 方法工作正常，HashMap 和 HashSet 就会按照描述的方式运行。然而，这样的 map /集合将是 O(n) - 它们的性能与其中的项目数量成线性关系。这是出乎意料的；哈希集/映射的要点是它们的性能不会随着它们的增长而发生有意义的变化。 HashMap/Set 并不神奇 - 它们需要一个良好的 hashCode() impl 来实现其性能 promise 。

如果您读过一些文档或书籍，说哈希码是关键，那么这要么来自过于简化的部分(重音在over上 - 这可能不是一件好事放在教程或解释)，或者作者误解了这个东西是如何工作的，或者它是另一个系统/语言中对 hashmap impl 的描述，它采用了高度可疑的快捷方式，将“相等的哈希”等同于“..因此相等”。考虑到鸽巢原理和所有这些，这是一个坏主意。如果您必须这样做，请使用良好的哈希算法并使用比 32 位更多的位数!