我知道为每个对象返回相同的值是低效的，但它是为不同实例返回不同值的最有效方法吗？
如果每个对象都获得不同的 hashCode 值，那么这不就像将它们存储在 ArrayList 中一样吗？
问问题
1624 次
5 回答
4
hashCode必须与一致equals，这是第一要务。如果没有两个对象是相等的，那么这将是可取的。请记住，如果您的对象具有超过 32 位的状态，则理论上不可能提供完美传播的哈希码。
于 2012-07-20T12:02:02.403 回答
3
不，实际上不是。
假设您的对象将被存储到 HashMap 中（或 Set... 无关紧要，为简单起见，我们将在此处使用 HashMap），您希望 hashCode 方法以均匀分布对象的方式返回结果尽可能。
哈希码对于不相等的对象应该是唯一的，尽管您不能保证这总是正确的。另一方面，如果a.equals(b)为真，则a.hashCode() == b.hashCode()。这被称为对象契约。
除此之外，还有性能问题。每次两个不同的对象具有相同的 hashCode 时，它们都会映射到 HashMap 中的相同位置（也就是它们碰撞）。这意味着 HashMap 实现必须处理这种冲突，这比简单地存储和检索条目要复杂得多。
还有很多算法依赖于值在 Map 中均匀分布的事实，当冲突数量增加时性能会迅速下降（一些算法假设一个完美的哈希函数，这意味着永远不会发生冲突，没有两个不同的值被映射到地图上的相同位置）。
这方面的好例子是概率算法和数据结构，例如布隆过滤器（使用一个现在看起来很流行的例子）。
于 2012-07-20T12:05:38.693 回答
1
您希望 hashCode() 尽可能多样化以避免冲突。如果没有冲突，每个键或元素将单独存储在底层数组中。（有点像 ArrayList）
问题是，即使 hashCode() 不同，您仍然可能会发生冲突。发生这种情况是因为您没有针对每个可能的 hashCode 的存储桶，并且该值必须减小到较小的范围。例如，你有 16 个桶，范围是 0 到 15。它是如何做到的很复杂，但我相信你可以看到，即使所有的 hashCode 都不同，它们仍然会导致冲突（尽管不太可能）
这是拒绝服务攻击的一个问题。通常字符串的冲突率很低，但是您可以故意构造具有相同哈希码的字符串。这个问题给出了一个 hashCode 为 0 的字符串列表 为什么 String 的 hashCode() 不缓存 0？
于 2012-07-20T12:14:50.610 回答
0
HashMap 类的主要数据结构是这样的：
Entry[] table;
需要注意的是，Entry 类（它是一个实现 Map.Entry 的静态包保护类）实际上是一个链表样式结构。
当您尝试放置元素时，首先会计算键的哈希码，然后将其转换为存储桶编号。“bucket”是上述数组的索引。
找到存储桶后，将在该存储桶内进行线性搜索以查找确切的键（如果您不相信我，请查看 HashMap 代码）。如果找到，则替换该值。如果不是，则将键/值对附加到该存储桶的末尾。
出于这个原因，hashcode() 值不必是唯一的，但是，它们越独特且分布越均匀，您在桶中均匀分布该值的几率就越大。如果您的 hashcode() 方法为所有实例返回相同的值，它们最终都会在同一个存储桶中，因此将您的 get() 方法呈现为一个长线性搜索，产生 O(N)
值分布得越多，桶就越小，因此线性搜索组件就越小。唯一值将产生恒定时间查找 O(1)。
于 2012-07-20T13:13:56.073 回答
0
hashCode() 方法不适合在 ArrayList 中放置对象。尽管它每次都会为同一个对象返回相同的值，但两个对象很可能具有相同的哈希码。
因此，在将项目存储在例如 HashMap 中时，在键 Object 上使用 hashCode 方法。
于 2012-07-20T12:04:27.147 回答