java - hashmap hashcode 以获得最坏情况下的常数时间？

Question

我知道由于可能的冲突，hashmap 操作是 O(1) 摊销的。但在 java 中，integer.hashCode 只是它的值。那么如果你将 m 个不同的整数放入一个 hashmap 中，其中 m = hashmap 的 INITIAL_CAPACITY（假设是 16），这是否意味着会有 16 个不同的桶，每个桶有 1 个整数？那么这会保证 O(1) 查找、删除、插入最坏的时间吗？

Answer 1

不，因为 HashMap 将不得不获取 hashCode 返回的大量可能值并将它们映射到非常少的桶，并且不能保证映射会将不同整数的哈希码映射到不同的桶。

Answer 2

您应该查看 Hashmap 决定密钥/对象属于哪个存储桶的方式，您会看到它不使用对象的 hashCode() 作为存储桶编号，而是稍微操纵它（位移）以将存储桶的数量限制为更少比 Integer.MAX_VALUE

Answer 3

如果您要将 m 个不同的整数放入一个哈希图中，其中 m = hashmap 的 INITIAL_CAPACITY（假设为 16），这是否意味着将有 16 个不同的桶，每个桶有 1 个整数？

取决于这些值，HashMap 可能会创建新的存储桶（增加容量）以将负载因子保持在最小值以下（如果默认情况下负载超过 75%，Java HashMap 会增加大小）。

什么是负载系数

这会保证 O(1) 查找、删除、插入最坏的时间吗？

不，在特别糟糕的情况下，查找时间可能高达 O(n)（取决于元素的数量及其值）。在整数的情况下，所有可能的 int 值都映射到 hashmap 大小，因此对于小尺寸的 map 可能会发生很多冲突。

Answer 4

不，因为HashMap会为了自己的内部目的重新散列哈希。