java - 删除时哈希表重新散列

Question

有谁知道为什么 hashtable 的 java jdk 实现在删除时不重新散列表？

如果空间使用率太低怎么办？这不是减小尺寸和重新散列的理由吗？

就像负载因子 0.75 触发 rehash on put 一样，我们可以在表的密度上设置一个像 0.25 这样的下限（当然可以在此处对最佳值进行分析）并再次触发 rehash，前提是表的大小大于初始容量。

Answer 1

重新散列是一项昂贵的操作，基于 java 散列的数据结构试图避免它。他们仅在查找性能不佳时才进行重新散列。这就是这种数据结构的目的：查找性能。

这是来自 HashMap java 文档的引用：

在设置其初始容量时，应考虑映射中的预期条目数及其负载因子，以尽量减少重新哈希操作的次数。如果初始容量大于最大条目数除以负载因子，则不会发生重新哈希操作。

如果要在 HashMap 实例中存储许多映射，则创建具有足够大容量的映射将比让它根据需要执行自动重新散列以增长表更有效地存储映射。

除了这个论点，Java 的创建者可能会认为，如果您的哈希表中有这么多元素，那么再次拥有它们的可能性非常大，因此无需重新哈希表两次。

Answer 2

您应该询问 Sun/Oracle 工程师以了解为什么没有减小大小的阈值。

这是我的两分钱：

• 重新散列表格需要时间
• 检查每个删除操作都需要时间

另一方面：

• 可能您不会节省太多内存（表中的对象和节点将使用更多空间）
• 可能没有很多场景首先创建（一些）非常大的哈希表，然后清空它们并渴望未使用的空间。
• 您知道任何包含该行为的流行实现（减小表大小）

在编程和生活中一样，有很多事情可以做。有些仅适用于非常特定的情况。有些根本不值得痛苦。