HashMap 要点

几个主要的变量

• capacity, size, loadFactor, threshold

capacity 是 Map 中 table 数组的大小，capacity 必定是 2 的幂。

size 元素数量。

loadFactor 负载系数，默认是 0.75，可以在初始化的时候设置。

threshold 阈值，threshold = capacity * loadFactor，当 size > threshold 时，会触发 map 的 resize 操作。

要点

capacity 为何是 2 的幂？

答：简化实现，提高性能。

解释： capacity 必须是 2 的幂，是因为 hashmap 是使用 位运算(&) 获取下标的，即 hash & (size - 1)。如果 size 不是 2 的幂的话，结果不是连续的，就会浪费空间。为什么要用 位运算(&) 运算获取下标，是因为一般情况都是通过 hash % size，而位运算(&) 直接对内存数据进行操作，不需要转成十进制，效率要比代替取模运算(%)高很多，所以要采用 & 操作。用 & 操作 size 必须是 2 的幂。

什么时候 resize

答：第一次put 的时候；当 size > threshold 时；数组中某个位置是链表结构，并且链表长度大于8时，并且 capacity < 64 时；

什么时候 链表转为红黑树

数组中某个位置是链表结构，并且链表长度大于8时，并且 capacity >= 64 时

初始化的时候，容量参数与真实容量的关系

public HashMap(int initialCapacity) 构造方法的参数值并不是最终真实的参数，在构造函数执行时会执行 tableSizeFor(int cap) 方法，该方法会根据参数返回一个大于或者等于 cap 的最小的 2次幂。具体算法解释：tableSizeFor算法解析