HashMap初始化与空间分配

背景

最近在为组里招人经常会问一些hashmap的问题，本文主要针对面试中的问题分析hashmap如何实现。

面试问答

下面将带着面试中提问的一些问题简单分析下hashmap到底是如何实现的。

原理分析

hashmap默认构造方法只将加载因子设置为默认值在无其他逻辑

带有初始化容量的构造方法内部逻辑更多一些

1. 校验容量是否合法即容量必须大于0
2. 校验容量必须小于最大容量
3. 校验装载因子是否合法
4. 设置装载因子和阈值

在阈值设置时调用了**tableSizeFor方法，此方法通过非常丝滑的算法将给定值转换为 大于等于该值 最小2的指数幂**

例如 tableSizeFor(19)=32,tableSizeFor(15)=16

threshold是影响hashmap容量的关键参数，我们先分析下tableSizeFor这个巧妙的算法逻辑

此算法逻辑涉及二进制和位运算因此先看下面内容

在十进制数中2的整数次幂对应的二进制数有效位为1且有效位后均为0，如下图所示

1. 为什么先做cap-1操作？当cap已经为2的整数次幂时通过该方法计算会将原来的cap变为2*cap，其实就是为了处理特殊的数据 

2. 为什么无符号移位操作是1，2，4，8，16？在java中int类型为32位，1+2+4+8+16正好是移动32位，移动32位后的得到的结果是将最高有效位及以后所有位变0位1 

假设cap=14，cap-1 =13 其二进制位1101经过下图的变化后发现在第一次位运算后所有有效位都为1111,因此在剩下的四次位运算后最终结果就是1111，最后将1111+1=10000得到十进制数位16。

此时虽然设置了hashmap的threshold但是并没有真正设置hashmap的容量大小，真正容量大小是在向hashmap中插入第一个元素时

接下来分析容量大小设置与空间分配逻辑

首次插入内存分配逻辑 put->putVal->resize

经过构造函数new的Hashmap对象并未真正分配内存空间，这其实是一种优化因为在构造方法分配内存空间后很久才进行插入操作那么这部分内存其实是闲置的。因此在put操作时会进行判断如果第一次插入则通过resize方法进行进行分配空间。第一次插入时分配的空间大小即为tablesizefor方法返回大小

因为首次插入table为null 所以需要resize操作

resize 包含初始化与扩容逻辑,本文只截取初始化逻辑分析

1. 首先判断table 是否为空，因为初始化阶段table=null所以oldCap=0
2. 由于在hashmap中带参数的构造方法通过tableSizeFor方法设置了threshold因此table数据的容量为oldThr
3. 如果使用无参数构造方法newCap&newThr均使用默认值
4. 最后创建数据并指向table 

总结

1. new hashmap(cap)初始大小为tableSizeFor大小
2. 空间分配是在首次插入时分配
3. 由于tableSizeFor是2的整数幂所以与0.75相乘结果为整数

HashMap使用非常巧妙且高效的算法获取了大于等于给定容量的最小2的整数幂，所以在根据hashcode计算元素所属hash表的位置时通过hashcode与（hash表长度-1）进行取模快速定位。
在首次插入进行内存分配机制极大的避免了内存浪费而且满足了局部性原理同样值得学习