java - 由于每个 hashmap 桶可以包含大量条目，因此如何确定 hashmap 已满

Question

hashmap的大小会根据负载因子而增加，但是如何确定hashmap已满，因为每个hashmap桶可以包含大量条目。为什么它创建新的存储桶而不是向现有存储桶添加条目？有没有办法确定桶中的条目数？负载因子如何发挥作用？假设初始容量为 16，负载因子为 0.75，那么在存储多少个条目后， HashMap 将被重新哈希？因为16*0.75是12，所以我们存储12个条目后会重新散列，还是在12个桶有条目而其余桶为空后重新散列？这12到底代表什么？

Answer 1

如何判断 HashMap 已满？

理论上不能说是完整的。我们仍然可以将任意数量的对象添加到存储桶的链接列表中(正如您所说)。

假设有很多(键，值)条目添加到 HashMap 中。理想情况下，HashMap 函数(get、put、contains)必须在 O(1) 内工作。为了实现这一点，HashMap 的每个桶只能存储一对(键，值)。每当 HashMap 发生冲突时，它就必须重新组织其底层数据结构以促进理想的哈希。每次碰撞时重新组织内部数据结构是一个复杂的操作，并且会降低 HashMap 的性能。

因此决定，一些碰撞是可以容忍的。当 HashMap 中的元素数量达到最大阈值时，就会进行 HashMap 的重新哈希。在重新哈希时，底层存储桶将变为双倍，并且(键，值)将映射到这些新的存储桶集。

通过这样做，桶中的(键，值)对的数量通常会减少。因此，通过使用额外的空间， HashMap 可以更好地工作。

有什么方法可以确定桶中的条目数吗？

在HashMap中，我们无法知道每个桶中的条目数。即使我们知道我们不能只拆分那个桶。例如，当前HashMap中有16个桶，如果我们知道有很多(Key，Value)对映射到一个桶，我们不能简单地将那个桶分成2个。我们不能显式地创建一个新的桶来分担负载那个桶的。在这两种情况下，桶数应为 17。但 HashMap 的桶数应始终为 2 的 n 次方。因此，我们无法对了解桶中条目的数量做任何特殊的事情。所以在HashMap中，不会做bucket级别的决策。全局决策将根据 HashMap 中的条目数进行。