为什么调整大小的方式是实现的？ [英] Why is resize implemented the way it is?

问题描述

在添加新的键值对时，我有几个关于重建 HashMaps 的问题。我将根据这些事实提出问题（对于Oracle JVM来说，它们是正确的，不知道它们对于其他JVM是否正确）：

1. 调整大小重建 HashMap 每次当您增加大于阈值（threshold = loadFactor * numberOfEntries）的HashMap时，可以拥有更大的内部表数组。新创建的条目在哪个bucket中无关紧要 - 地图仍然会变大。即使所有的条目都进入一个数据桶（即它们的键' hashCode（）返回相同的数字）。


2. HashMap 在数据被删除时不会缩小。即使从 HashMap 中删除​​所有密钥，表的内部大小也不会更改。

现在的问题：

1. 这些事实是否正确？

如果是，那么：

2. 为什么要这样调整大小？即使显然没有必要，是否有意增长内表？还是一个错误？


3. 为什么不缩小？

解决方案>

是的，这些事实是正确的。

1. 检测是否显然不是必需花费很多时间，几乎总是多余的，因为所有的密钥具有相同的哈希码的情况很少见。简而言之，为了节省一些极少数情况下的工作，您将花费大量的费用（跟踪每个人的常见代码），这样可以节省更多的成本。


2. 因为删除是一个不那么常见的操作，通常后面是重新填充地图。如果你想用一个较小的表格来启动地图，你可以将它分配给一个新的HashMap 并让旧的垃圾回收。

I have several questions about rebuilding HashMaps when adding new key-values pair. I will ask questions based on these facts (they are true for Oracle JVM, not sure if they are correct for other JVMs):

1. Resize rebuilds HashMap to have a bigger inner table array every time when you grow HashMap bigger than threshold (threshold = loadFactor*numberOfEntries). It does not matter in which bucket the newly created Entry is put - Map will still grow bigger. Even if all of the Entries go into one bucket (i.e. their keys' hashCode() return the same number).
2. HashMap does not shrink when data is removed. Even if all keys are removed from HashMap, the inner size of it's table does not change.

Now the questions:

1. Are these facts correct?

If they are, then:

2. Why resize implemented this way? Is it the intention to grow the inner table even when it is obviously not necessary? Or a bug?
3. Why it does not shrink?

解决方案

Yes, these facts are correct.

1. Detecting whether it is "obviously not necessary" would take a lot of time, and it's almost always redundant, since the case where all the keys have the same hash code is rare. In short, you're paying a significant expense (tracking how common one particular hash code is) for everybody just to save some work in an extremely rare case, which will end up costing more than it saves.
2. Because removing is a somewhat less common operation, and it's usually followed by refilling the map. If you want to start the map over with a smaller table, you can just assign it to a new HashMap and let the old one be garbage-collected.

这篇关于为什么调整大小的方式是实现的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！