前言
一切的源头从类注释开始说起，翻译自 HashMap 类源码上注释
基于哈希表的 Map 接口的实现，这实现提供了所有可选的映射操作，并允许空值和空键。
HashMap 实现为基本的提供了恒定时间的性能操作：get、put 方法，假设哈希函数将元素正确地分散在桶中。 集合视图迭代所需要的时间与集合视图的“容量(capacity)”成正比。HashMap 实例（桶的数量）加上它的大小（键值映射的数量） 因此，若迭代性能很重要，则不要将初始容量设置得太高（或负载因子太低）
HashMap 实例有两个参数会影响其性能：初始容量 initial capacity、负载因子 load factor
容量是哈希表中桶的数量，初始容量只是创建哈希表时的容量。 负载因子是哈希表在其容量自动增加之前允许达到多满的度量。 当哈希表的条目数超过负载因子与当前容量的乘积时，哈希表将被重新哈希（即重新建立内部的数据结构），使哈希表的桶数大约增加一倍。
作为一般规则，默认负载系数 (0.75) 提供了一个很好的时间与空间成本之间的权衡
较高的值会减少空间开销，但会增加查找成本，主要反映在 HashMap 大部分会操作 > get、put
在设置其初始容量时应考虑 Map 中预期的条目数及其负载因子，以尽量减少 rehash 操作的次数
若需要将许多映射存储在一个 HashMap 实例中，创建一个足够大的容量将会使得映射的存储比让它执行自动重新散列来扩大表更有效，所以一般在实际开发中，会预测这个初始的容量并给它指定
使用相同的 hashcode 值键肯定会降低任何哈希表性能的影响，为了改善影响，HashMap 底层数据结构使用了链表+红黑树
HashMap 实现不是同步的，即不是线程安全的，若要实现线程安全应当使用Collections.synchronizedMap 方法或 ConcurrentHashMap，这最好在创建时完成，以防止对 Map 的意外不同步访问
Map m = Collections.synchronizedMap(new HashMap(…))
此类的所有“集合视图方法”返回的迭代器是快速失败 fast-fail：若映射在之后的任何时间进行了结构修改，除了通过迭代器自己的 remove 方法，普通遍历时将抛出 ConcurrentModificationException。 因此，面对并发修改后，迭代器会快速干净地失败，而不是冒着风险任意的在不确定的时间、不确定的行为上操作。
后面会具体介绍 HashMap 数据结构以及它的一些核心方法、属性的部分，比如：初始容量 initial capacity、负载因子 load factor、get、resize、put 等
数据结构
在 HashMap 1.7 版本中，数据结构采用数组+链表组成
在 HashMap 1.8 版本中，数据结构采用数组+链表+红黑树组成
当一个值要存入到 HashMap 中时，会先根据 Key 以低 16、高 16 位方式计算出它的 hash 值，通过 hash 来确认要存放到数组中哪个位置；若发生 hash 值冲突时，则以链表的方式依次向后存储；当链表过长并且数组元素长度到达一定阈值时，HashMap 会将链表转换为红黑树作为存储结构
类属性
在阅读源码之前，先了解 HashMap 它的一些基础属性
// 默认的初始化容量：16 - 必须为 2 的幂次方 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 // 最大容量值，若隐式指定了更大的值，则使用最大容量 MAXIMUM_CAPACITY // 会由任意一个带参数的构造函数进行判断或 resize 方法中进行判断 static final int MAXIMUM_CAPACITY = 1 << 30; // 默认负载因子：0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 当链表长度到达该阈值 & table 数组容量大小到达 MIN_TREEIFY_CAPACITY 阈值会转换为红黑树 static final int TREEIFY_THRESHOLD = 8; // 当 table 数组容量的大小到达该阈值 & 链表长度到达该阈值 TREEIFY_THRESHOLD 就会进行树化 static final int MIN_TREEIFY_CAPACITY = 64; // Node 是 HashMap 中的内部类 > 单链表结构，用来表示 Key-Value，table 数组中存放的就是 Node static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; // ...... public final int hashCode() { // ^ 表示相同返回 0，不同返回 1 return Objects.hashCode(key) ^ Objects.hashCode(value); // Objects.hashCode(o) -> return o != null ? o.hashCode() : 0; } } // 在第一次使用时初始化 transient Node<K,V>[] table; // 键值映射的数量 transient int size; // 扩容的阈值 int threshold; // 哈希表的默认负载因子，不指定默认为 0.75，构造函数中会指定 final float loadFactor;
默认的初始化容量：16、默认负载因子：0.75、默认的扩容阈值：数组长度 * loadFactor，当元素个数大于等于 threshold(容量阈值)时，HashMap 会进行扩容操作、table 数组中指向链表的引用
构造方法
// 最大容量不能大于 1 << 30 = 1073741824，扩容阈值通过 tableSizeFor 计算 public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } /** * 指定了初始化容量，默认负载因子为 0.75 */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * 直接实例化 HashMap，初始化容量为 16、默认负载因子为 0.75 */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } /** * 以旧 HashMap 数据为依据，构建一个新的哈希映射集合 */ public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }
一般在实际开发中，会使用 public HashMap(int initialCapacity) 构造方法指定初始化容量大小
核心方法
在构造方法中，通过 tableSizeFor方法初始化了扩容阈值，该方法主要用来保证 HashMap 的数组长度为 2 的幂次方的
阈值：tableSizeFor
/** * cap 参数是初始化容量值 * 找出大于或等于 cap 的最小 2 的幂次方，用于作容量的阈值 */ static final int tableSizeFor(int cap) { int n = cap - 1; // 先进行位移操作后进行异或操作，最后进行赋值 n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
tableSizeFor 方法功能，在不考虑大于最大容量的情况（最大容量值也是 2 的幂次方整数），是直接返回大于等于输入参数的 2 的幂次方整数的。比方说：传入参数 10，结果会返回 16.
该算法让最高位的 1 后面所有的 bit 位都变为 1，最后再让结果 n + 1，就可以得到 2 次幂整数值
首先让 cap - 1 完成后再赋值给 n 的目的：可以令找到的目标阈值大于或等于原有值。例如：二机制数 1000，十进制数值就为 8；若不对它减 1 而直接操作，得到的结果是 10000，即十进制数 16，显而易见不是想要的结果；减去 1 后二进制数为 111，再进行操作得到的结果会是 1000，即十进制数 8，满足我们想要的结果
通过一系列的位运算能大大提高效率，在实际开发中，我们传入的初始化容量在确定总数时，一般是会传入 2、4、8 这样的值，遵循 2 的幂次方
tableSizeFor 方法执行的结果主要是为了设置 threshold 属性值，在扩容方法 resize 中会使用它来初始化数组长度
将数组长度设置为 2 的幂次方可以带来以下的好处
- 当数组长度为 2 的幂次方时，可以使用位运算来计算元素在数组中的下标
HashMap 中是通过 index = hash & (table.length -1) 算法来计算元素在 table 数组中存放的下标，相当于就是取元素的 hash 值与数组长度减 1 值作一个位运算，即可求出该元素在数组中的下标，该算法等价于 hash % table.length > 对数组长度求模取余，只不过只有在数组长度为 2 的幂次方时，
hash & (length-1) 才等价于 hash % length，使用位运算操作可以提高效率
- 增加 hash 值随机性，减少 hash 值冲突
若 table.length 为 2 的幂次方，则 table.length -1 转化为二进制必然是 1111111… 这样的，如此便可以使得所有位置的 bit 位都能与 hash 值作位运算；若 table.length 不是 2 的幂次方，比如：15，table.length - 1 =14，对应的二进制数为 1110，再和 hash 值作位运算，最后一位永远为 0，浪费计算的空间
插入元素：put
resize 扩容方法也是在 put 方法中进行调用的，所以先从 put 方法开始介绍起，源码如下：
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
在调用 putVal 插入 Key-Value 方法时先要计算 Key Hash 值
在 HashMap 中不是直接通过 Key hashcode 方法获取哈希值的，而是通过内部自定义实现的 hash 方法获取哈希值；当 Key 不为空时，会执行： (h = key.hashCode()) ^ (h >>> 16) 算法让高位数据与低位数据进行异或运算，变相的让高位数据参与到计算中，int 有 32 个 bit 位，右移 16 位就可以让低 16 位与高 16 位进行异或运算，也是为了增加 hash 值的随机性，减少 hash 冲突的发生
当 Key hash 值计算好了以后，再接着分析 putVal 方法，源码如下：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // 指向 Hash 数组 Node<K,V>[] tab; // 待赋值，当前需要插入的 Key-Value 节点 Node<K,V> p; // n：数组长度、i：索引 int n, i; // 延迟插入数据，先进行数组的初始化操作 > 调用 resize 方法 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 若数组中不包含当前通过 hash 计算后所在下标的数据，那么就新建一个 Node 节点存入数组对应的下标 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { // 若待插入的 Key-Value 已存在，用 e 指向该 Node，k 指向 Key 值 Node<K,V> e; K k; // 当前计算所在下标的节点就是要插入的 Key-Value，则让 e 指向该节点 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 若 p 是 TreeNode 类型，则调用红黑树的插入操作 // TreeNode 是 Node 子类 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 对链表进行遍历，并用 binCount 数统计链表长度 for (int binCount = 0; ; ++binCount) { // 若链表中不包含要插入的 Key-Value，则将其插入到链表尾部 > 尾插法 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 若链表长度大于或等于树化的阈值，也就是长度为 8 时 // 会调用 treeifyBin 方法进行树转换逻辑 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 若要插入的 Key-Value 已存在则终止遍历，否则继续向后遍历 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; // 继续向下遍历，取下一条节点数据进行判断 p = e; } } // 若 e 不为空，说明插入的 Key-Value 已存在 if (e != null) { // existing mapping for key V oldValue = e.value; // 根据传入的 onlyIfAbsent 参数值判断是否要覆盖旧值 // putIfAbsent 方法不会覆盖旧值、put 方法会覆盖旧值 if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 键值对数量大于阈值时，则进行扩容操作 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
对以上 putVal 方法源码分析流程如下：
- 当 table 数组为空时，会先调用 resize 方法初始化 table 数组
- 通过计算 Key hash 值，通过
hash & tab.length-1 算法求出下标后，若该下标位置上没有元素，也就是没有发生 hash 冲突，就新建一个 数组 Bucket 插入进去 - 若发生了 hash 冲突，遍历链表查询要插入的 Key 是否已存在
若存在的话根据条件判断是否用新值替换旧值
若不存在，则将元素采用尾插法，插入到链表的尾部，并根据链表的长度决定是否要将链表转换为红黑树
- 键值对数量大于阈值时，则进行扩容操作 > 调用 resize 方法
putVal 方法里面有调用 treeifyBin(tab, hash);，注意：这里并不一定会真正转换为红黑树，它只满足了链表长度大于或等于树化的阈值该条件，另外一个条件未满足
