java - hashmap 如何识别何时需要重新哈希

Question

Hashmap 如何识别这个存储桶已满并且需要重新哈希，因为如果两个哈希码相同，它会将值存储在链表中，那么根据我的理解，这个链表没有任何固定大小，它可以存储尽可能多的元素，因此这个存储桶永远不会满，那么它如何识别它需要重新哈希？

Answer 1

在 ConcurrentHashMap 中，当发生冲突时(即两个不同的键具有相同的哈希码)，实际上会使用红黑树(对于大量元素)或链表(对于少量元素)。但是当你说链表(或红黑树)可以无限增长(假设你有无限的内存和堆大小)时，你是对的。

HashMap 或 ConcurrentHashMap 的基本思想是，您希望在 O(1) 时间复杂度内根据其键检索值。但实际上，碰撞确实会发生，当发生这种情况时，我们将节点放入链接到存储桶(或数组单元)的树中。因此，Java 可以创建一个 HashMap，其中数组大小将保持固定并且永远不会发生重新哈希，但如果他们这样做，则所有键值都需要容纳在固定大小的数组中(以及它们的链接树)。

假设您有一种 HashMap，其中数组大小固定为 16，并且在其中推送 1000 个键值对。在这种情况下，您最多可以有 16 个不同的哈希码。这反过来意味着您将在所有 (1000-16) 个 put 中发生冲突，并且这些新节点最终将出现在树中，并且无法再以 O(1) 时间复杂度获取它们。在树中，您需要 O(log n) 时间来搜索键。

为了确保这种情况不会发生，HashMap 使用加载因子计算来确定数组中填充有键值对的部分。如果已满 75%(默认设置)，任何新的 put 都会创建一个更大的新数组，将现有内容复制到其中，从而拥有更多的存储桶或哈希码空间。这可以确保在大多数情况下不会发生冲突，并且不需要树，并且您可以在 O(1) 时间内获取大多数键。