HashMap 实现

initialCapacity 是其中构造方法一个参数，用于开发者初始化容器大小，此值会被加工为 2 的幂
size 变量指的是容器目前存在的 (key, value) 对总和
threshold 变量指的是容器最大可以容纳的 (key, value) 对
table.length 指的是底层实现数组的真正长度
loadFactor 变量是一个浮点数类型被称为 加载因子

HashMap 实例创建后并不会立刻创建 table 数组占用空间。

通过 table.length 和 loadFactor 计算最大容纳（threshold = table.length * Load factor）

结合负载因子的定义公式可知，threshold就是在此Load factor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。

HashMap 为什么需要扩容

因为 Map 接口在长度上设计是可变，HashMap 可以在构造方法上指定初始大小和扩容因子，初始大小会被通过位运算选取最近2的幂。

为什么 initialCapacity 需要为 2 的幂

尽量希望减少 Hash 碰撞，使内部元素在数组中分配均匀。

hash(Object key)这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

在HashMap中，哈希桶数组table的长度length大小必须为2的n次方(一定是合数)，这是一种非常规的设计，常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数，具体证明可以参考http://blog.csdn.net/liuqiyao_01/article/details/14475159，Hashtable初始化桶大小为11，就是桶大小设计为素数的应用（Hashtable扩容后不能保证还是素数）。HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。

在什么时候扩容

当 Table 为空会立即扩容。当元素被插入后，如果容器内实际元素大小大于 threshold 则按照 loadFactor进行扩容 ，默认的扩容因子为 0.75 也就是当实际容量达到 75% 的时候进行扩容。

扩容因子的目的的是什么

HashMap 此处设计希望开发者针对特殊场景可以灵活实现，而不是像 ArrayList 一样扩容 50%
同样，越大的数组碰撞的几率越低，不必要再去遍历链表或者查询红黑树。

HashMap 长度的无限的吗

Map 接口定义 size() 方法返回为 int 类型，理论上应最大支持 Integer.MAX_VALUE 个元素，HashMap中有定义最大可容纳元素 MAXIMUM_CAPACITY = 1 << 30 这个值也是 2 的幂，同 ArrayList 一样超过这个值则设定为 Integer.MAX_VALUE 防止 int 溢出。

HashMap Put 方法分析

HashMap 和 ArrayList 一样都没有在构造方法中初始化容器大小，可有效减少空 HashMap 带来的空间浪费。

1. 在put方法中如果 table 没有创建则进行创建。
2. 计算 hash 确定元素下标，如果下标位置为空直接放入并返回。
3. 如果当前下标存在元素则进行比较是否“相等” p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) 如果两元素 hash 值相等并且 key 引用相等，或者两 key equals 方法返回 true 则认为找到目标元素，则进行原地覆盖。
4. 如果当前下标元素未能确认相等，则判断当前下标下元素 Node 是否为红黑树，若为红黑树则进行红黑树插入逻辑（这里不进行展开）
5. 如果当前下标未能确认相等，并且，当前下标节点也不是红黑树则进行链表逻辑操作，遍历链表到末尾并计算总长度，如果长度大于 8 则立即进行红黑树转换，同时遍历过程中进行 Key 的比较如果相同进行原地覆盖。
6. 根据 threshold 判断 size 是否溢出，如果溢出则立即进行扩容。
7. 返回（注意，如果以上流程存在替换 Value 行为则返回 oldValue）
   以上操作都必须经历 6 - 7 操作
   扩容大小永远是原大小的两倍 oldCap << 1

如何计算 Hash和确定位置？

如果 key 为 null 则返回 null 其他情况直接获取对象的 hashCode() 方法无符号右移 16 位并与原 hashCode() 进行 ^ （按位异或，同为 1 则为 0）运算。

static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

例如字符串 xxx 计算结果为 119161 二进制为 11101000101111001 当前HashMap数组长度为 16 下标总长为 15 将 15 & 119161（与运算，同为 1 则为 1）即 1111 & 11101000101111001 结果为 1001 下标为 9 将 Key 与 Value 包装成 Node 放入下标位置执行上方 2-7逻辑。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
}

扩容是如何转移元素的？

需要 rehash 吗

JDK 1.7 可能需要 rehash 在 JDK 1.8 对 rehash 进行了优化，因为 table 长度恒定 2 的幂，例如扩容前为 16 - 1 （0000 1111）扩容后为 32 - 1（0001 1111），某元素 hash 为 1100 0101 在经过扩容后重新进行下标计算 0000 1111 & 1100 0101 == 0001 1111 & 0001 1111 与 16 是一致的，如果某元素为 hash 1101 0101 结果为 0001 0101 其下标新增 16 所以仅需要判断高位是 1 还是 0 如果是 0 位置保持不变，如果为 1 则为 原索引+oldCap

红黑树相关

UNTREEIFY_THRESHOLD = 6 注意当红黑树长度小于此值时，当退化为链表。

总结

• 非线程安全的
• HashMap 严重依赖对象的 hashCode() 和 equals() 方法 重写 equals需要注意
• HashMap 存在空间浪费，如果可以则尽量指定容器大小
• 同 ArrayList / LinkedList 一样存在快速失败机制 modCount 主要应用场景在迭代器上
• Key 值的 HashCode 需要足够分散

相关资料

• https://tech.meituan.com/2016/06/24/java-hashmap.html
• https://www.cnblogs.com/chinajava/p/5808416.html