OCP 书中的这句话正确吗?
A HashSet stores its elements in a hash table, which means the keys are 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 中的键,而不是其哈希值。书中是否有错误,或者我是否看到了一些不相关的内容?
最佳答案
当然是对象而不是哈希值。一些单独显而易见或至少易于验证的事实:
- 鉴于哈希值是固定大小的(存在 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 位更多的位数!
关于java - Set底层HashMap中的key是什么: hash code or the object itself?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/76155171/