在HashMap中,为什么阈值(调整大小的下一个大小值)是capacity*load factor.为什么不等于地图的大小或容量.
例如,最初默认容量= 16,负载因子= 0.75因此threshold = (capacity * load factor) = (16 * 0.75) = 12.
添加第13个元素的地图调整大小为什么这样,为什么地图的作者决定保留它capacity * load factor(12个)？为什么不与容量相同(16).
为什么不保持阈值等于容量,以便只在hashmap满了时才进行重组？
Javadoc,Javadoc,Javadoc.这是你看的第一个地方.在HashMap它上面说:
作为一般规则,默认加载因子(.75)在时间和空间成本之间提供了良好的权衡.较高的值会减少空间开销,但会增加查找成本(反映在HashMap类的大多数操作中,包括get和put).在设置其初始容量时,应考虑映射中的预期条目数及其加载因子,以便最小化重新散列操作的数量.如果初始容量大于最大条目数除以加载因子,则不会发生重新加载操作.
就像哈希映射理论一样 - 如果你的地图已经满了,那么你正在做一些非常非常错误的事情.到那个时候你可能正在O(sqrt(N))查找随机数据 - BAD.你永远不希望你的hashmap是完整的.但是一张非常稀疏的地图会浪费太多空间(正如你所注意到的那样),并且需要很长时间才能完成迭代.因此,对于大多数用例,应该有一个小于1的负载因子.
注意:"浪费的空间"与地图的大小成正比,与负载系数成反比.但是查找时间具有更复杂的预期性能函数.这意味着相同的加载因子将不适用于不同大小的哈希映射 - 因为它将意味着不同的规模权衡.
关于权衡的一般概述可以在Knuth"The Art of Computer Programming"第3卷中找到.