java - 如何以及何时在 HashMap 中完成 Rehashing

Question

我对散列和重新散列有些困惑。以下是我的理解，如有错误请指正。

从图片上看，bucket实际上是Entry类的数组，以链表的形式存储元素。每个新的键值对，其键具有与条目数组桶相同的哈希码，将作为条目对象存储在存储该哈希码元素的桶中。如果 key 具有当前不存在于条目数组存储桶中的新哈希码，则将添加一个具有相应哈希码的新存储桶。

现在的问题是，实际重新散列何时发生？

情况 1:假设我有一个条目数组，其哈希码桶为 1,2 3，并在条目数组桶达到 12 时添加了新元素，但一旦出现哈希码为 13 的新元素(假设我在 hashcode 1 然后 2 等系列中添加元素)，将创建一个新的 Map/Array of Entry Bucket(请说明是哪个)，新容量将为 32，现在 Entry 数组可以保持不同32 个桶。

case 2:bucket dosent matter 的个数，HashMap 的默认容量为 16 意味着它可以在其中存储 16 个元素，dosent matter 在单个 bucket 中或无论如何。由于负载因子为 .75，一旦添加第 13 个元素，就会创建一个新的桶数组，其中包含 32 个，即现在所有链接列表中的总 Entry 节点可以是 32。

我认为情况 2 是正确的。请详细说明Re Hashing过程，如果能用这个图更好。

Answer 1

重新散列会根据当前存储在 HashMap 中的条目数增加可用桶的数量。

当 HashMap 实现确定应该增加桶的数量以维持预期的 O(1) 查找和插入性能时，它就会发生。

关于 .75 的默认加载因子以及它如何导致 HashMap 在添加第 13 个条目时重新散列，您是正确的。

但是，HashMap 的默认容量为 16 意味着它可以在其中存储 16 个元素的说法是不正确的。任何桶都可以存储多个条目。但是，为了保持所需的性能，每个桶的平均条目数应该很小。这就是我们有负载因子的原因，也是我们应该使用适当的 hashCode() 来尽可能均匀地将键分布在桶中的原因。