0

HashMap 内部有方法hash()通过应用特殊函数来防止写得不好的哈希码。下一步是hash()方法的返回值用于计算新条目存储在名为table的支持数组中的索引。两个不同键的索引可能相同。因为使用了该链接列表，但我很清楚。

为什么两个不同键的后备表索引可以相同？

我知道哈希码可能很难被覆盖，但方法hash()声明它可以防止哈希码冲突。那么为什么后备表的索引可以相同呢？

编辑感谢大家的回复。当您放入 HashMap ( size ) 的元素数量大于或等于 threshhold 时，@Dunkan Jones 会自动调整大小（根据构造函数中提供的 initialCapacity 和 loadFactor 计算）。查看方法 createEntry -每当创建新条目时，大小都会增加。我的问题是为什么 hash() 方法 + indexFor() 方法为不同的对象返回相同的索引。由于这个相同的索引，两个条目通过链表放在同一个桶中。

是什么导致 hash() + indexFor() 方法返回相同的索引？

我认为并且无法意识到那些棘手的 >>> 和 & 运算符的 hash() 和 indexFor() 做什么？

HashMap 中的散列是什么意思？

再次感谢！

4

2 回答 2

1

如果我没记错的话，每个可以成为哈希映射键的对象都应该覆盖hashCode()方法，所以一般合同（来自 Javadoc）是

如果根据方法两个对象相等equals(Object)，则对两个对象中的每一个调用该hashCode方法必须产生相同的整数结果。

换句话说：

o1.equals(o2)然后o1.hashCode() == o2.hashCode()

哈希映射在内部使用另一个函数从值hash()创建另一个哈希码。hashCode()此函数在某些时候使用模数（用于空间效率），因此不同的hashCode()值可以具有相等hash()的值（键与hash()值映射）。

这不是问题，因为如果 map 中的两个键值相等hash()，则在搜索时将与equals()方法进行比较，以确保它们具有相同的键，并且没有两个巧合的对象具有相同的哈希码。

一些资源：

OP编辑后编辑

我认为indexFor计算模数。功能是

static int  indexFor(int h, int length) {
   return h & (length-1);
}

我们知道（从理论上）a % b == a & (b - 1)当且仅当b是 2 n。长度字段（我们的“ b ”）是 2 n的倍数：

对给定的 hashCode 应用补充散列函数，以防止质量差的散列函数。这很关键，因为 HashMap 使用长度为二的幂的哈希表，否则会遇到低位没有差异的 hashCode 的冲突。注意：空键总是映射到哈希 0，因此索引为 0。

所以不同的哈希值可以有相同的模数，因此不同的对象可以有相同的索引。

于 2013-07-23T07:45:31.410 回答
1

你是对的，内部hash()方法是用来提高结果的质量的hashCode()。内部 Javadocs 描述了原因：

检索对象散列码并将补充散列函数应用于结果散列，以防止质量差的散列函数。这一点很关键，因为 HashMap 使用长度为二的幂的哈希表，否则会遇到低位没有差异的 hashCode 的冲突。注意：空键总是映射到哈希 0，因此索引为 0。

但是，您的基本问题似乎是：为什么哈希映射允许多个值位于同一个“桶”中，而不仅仅是扩展映射的大小？

答案将是性能。在调整大小操作期间重新计算地图中的所有哈希值非常昂贵。直到某一点，将多个值填充到同一个存储桶中会更便宜。

于 2013-07-23T07:43:01.353 回答