HashMap的秘密隐藏大小

为什么更好地定义HashMap的初始大小

没有参数构造函数…

Java中,初始化集合和映射的初始容量是一种好习惯。

许多开发人员(包括我在内)习惯于使用no参数构造函数声明新的Collection或Map,例如:

Map exampleMap = new HashMap();

Java使用此指令初始化了一个新的HashMap对象,其loadFactor属性为0.75, DEFAULT_INITIAL_CAPACITY为16。

HashMap在内部将其值存储在HashMap $ Node对象的数组中(至少直到大小不会变得太大时)。

初始化还没有创建数组,它只会在映射中的第一个插入处被实例化(例如,使用put ),
Java将使用以下内容创建内部数组: Node[] tab = (Node[])new Node[16]

…它将增长

每次将条目添加到Map中时,HashMap实例都会检查存储区数组中包含的值的数量是否不超过其容量乘以负载系数(默认值为0.75)。
在我们的示例中:16(容量)* 0.75(负载系数)= 12(阈值)。

将第13个值插入数组时会发生什么? 数组中的条目数大于阈值,并且HashMap实例调用该方法: final Node[] resize()

此方法创建一个新的Node数组,其当前存储容量为(16)* 2:
(Node[])new Node[32]

当前存储区数组的值在新数组中“传输”,新阈值也乘以* 2。

下表显示了存储桶阵列的大小如何增加新条目。

resize()完成的重新哈希处理需要计算能力,应尽可能避免。

在构造函数中定义初始大小

您有一个已定义的数字或条目,或者知道映射将包含的值的数目应该是多少,那么建议相应地设置“初始容量”。

例如,您将有100个条目,而没有另一个? new HashMap(100)将生成仅包含100个节点的存储桶数组,而在插入过程中无需重新哈希。

如果使用构造函数定义了初始容量,则使用以下算法来计算阈值的大小:

 /** 
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

…结果是128。

如果您的地图增长不会超过初始大小,则不会重新哈希您的数据。

如果您知道HashMap的最大大小,则此解决方案是最佳的。

来自代码源的一般提示

映射时应考虑映射中的预期条目数及其负载系数
设置其初始容量,以最大程度地减少重新哈希操作的次数。

如果初始容量大于最大条目数除以负载因子,则将不会发生任何哈希操作。

测试使用的JDK版本

OpenJDK版本11.0.1

文章来自: https : //javaee.ch