前言
今天我们来学习Java中较为常用的集合类 HashMap。
另外说明一下，本文的 HashMap 源码是基于Jdk1.8版本的，如果没有特别说明的话，之后的集合类源码解析都是1.8的版本。
HashMap的数据结构
打开HashMap源码文件，可以看到它是继承自 AbstractMap，并实现了Java集合的根接口Map，以及Cloneable和Serializable接口，所以HashMap可以被序列化。
HashMap的底层结构是哈希表的具体实现，通过相应的哈希运算就可以很快查询到目标元素在表中的位置，拥有很快的查询速度，因此，HashMap被广泛应用于日常的开发中。理想的情况就是一个元素对应一个Hash值，这样的查询效果是最优的。
但实际这是不可能的，因为哈希表存在“hash (哈希) 冲突“ 的问题。当发生hash冲突时，HashMap采用 “拉链法“ 进行解决，也就是数组加链表的结构。在HashMap的代码注释中，数组中的元素用 “bucket” (中文读作 桶) 来称呼，而哈希函数的作用就是将key寻址到buckets中的一个位置，如果一个 bucket 有多个元素，那么就以链表的形式存储（jdk1.8之前单纯是这样）。
这是HashMap的存储结构图：
关于 “拉链法” 和 “hash冲突” 的知识点有疑问的读者可以看下我之前的文章 数据结构：哈希表以及哈希冲突的解决方案 。
为了方便，下文的 “bucket“ 都用 “桶“ 替代。
深入源码
两个参数
在具体学习源码之前，我们需要先了解两个HashMap中的两个重要参数，“初识容量” 和 “加载因子”，
初识容量是指数组的数量。加载因子则决定了 HashMap 中的元素在达到多少比例后可以扩容 (rehash)，当HashMap的元素数量超过了加载因子与当前容量的乘积后，就需要对哈希表做扩容操作。
在HashMap中，加载因子默认是0.75，这是结合时间、空间成本均衡考虑后的折中方案，因为 加载因子太大的话发生冲突的可能性会变大，查找的效率反而低；太小的话频繁rehash，降低性能。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。
成员变量
好了，前面说了那么多，现在开始深入源码学习吧，先了解一下HashMap的主要的成员变量：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; static final int MAXIMUM_CAPACITY = 1 << 30; static final float DEFAULT_LOAD_FACTOR = 0.75F; static final int TREEIFY_THRESHOLD = 8; static final int MIN_TREEIFY_CAPACITY = 64; transient HashMap.Node<K, V>[] table; transient Set<Entry<K, V>> entrySet; transient int size; int threshold; final float loadFactor;
可以看出，HashMap主要的成员变量比较多，有些变量还初始化了值，下面一个个来做解释。
DEFAULT_INITIAL_CAPACITY：默认初识容量 1 << 4 ，也就是16，必须是2的整数次方。
DEFAULT_LOAD_FACTOR：默认加载因子，大小为0.75。
MAXIMUM_CAPACITY：最大容量， 2^ 30 次方。
TREEIFY_THRESHOLD ：树形阈值，大于这个数就要树形化，也就是转成红黑树。
MIN_TREEIFY_CAPACITY：树形最小容量。
table：哈希表的链接数组，对应桶的下标。
entrySet：键值对集合。
size：键值对的数量，也就是HashMap的大小。
threshold：阈值，下次需要扩容时的值，等于 容量*加载因子。
loadFactor：加载因子。
介绍完变量，下面介绍HashMap的构造方法。
四个构造方法
HashMap共有四个构造方法，代码如下：
//加载默认大小的加载因子 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; } //加载默认大小的加载因子，并创建一个内容为参数 m 的内容的哈希表 public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; //添加整个集合 putMapEntries(m, false); } //指定容量和加载因子 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); } //指定容量，加载因子默认大小 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
不难发现，上面第三个构造函数可以自定义加载因子和容量，首先判断传入的加载因子是否符合要求，然后根据制定的容量执行 tableSizeFor() 方法，它会根据容量来指定阈值，为何要多这一步呢？
因为buckets数组的大小约束对于整个HashMap都至关重要，为了防止传入一个不是2次幂的整数，必须要有所防范。tableSizeFor()函数会尝试修正一个整数，并转换为离该整数最近的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; }
比如传入一个整数244，经过位移，或运算后会返回最近的2次幂 256
插入数据的方法：put()
在集合中最常用的操作是存储数据，也就是插入元素的过程，在HashMap中，插入数据用的是 put() 方法。
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
put方法没有做多余的操作，只是传入 key 和 value 还有 hash 值 进入到 putVal方法中并返回对应的值，点击进入方法，一步步跟进源码：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //哈希表如果为空，就做扩容操作 resize() if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //要插入位置没有元素，直接新建一个包含key的节点 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //如果要插入的桶已经有元素，替换 else { Node<K,V> e; K k; //key要插入的位置发生碰撞，让e指向p if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //没碰撞，但是p是属于红黑树的节点，执行putTreeVal()方法 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //p是链表节点，遍历链表，查找并替换 else { //遍历数组，如果链表长度达到8，转换成红黑树 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 找到目标节点，退出循环，e指向p if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 节点已存在，替换value，并返回旧value if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //如果超出阈值，就得扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
代码看上去有点复杂，参数有点乱，但理清逻辑后容易理解多了，源码大概的逻辑如下：
- 先调用 hash() 方法计算哈希值
- 然后调用 putVal() 方法中根据哈希值进行相关操作
- 如果当前 哈希表内容为空，做扩容
- 如果要插入的桶中没有元素，新建个节点并放进去
- 否则从要插入的桶中第一个元素开始查找（这里为什么是第一个元素，下面会讲到）
- 如果没有碰撞，赋值给e，结束查找
- 有碰撞，而且当前采用的还是 红黑树的节点，调用 putTreeVal() 进行插入
- 链表节点的话从传统的链表数组中查找、找到赋值给e，结束
- 如果链表长度达到8，转换成红黑树
- 最后检查是否需要扩容
put方法的代码中有几个关键的方法，分别是：
- hash():哈希函数，计算key对应的位置
- resize():扩容
- putTreeVal():插入红黑树的节点
- treeifyBin():树形化容器
前面两个是HashMap的桶链表操作的核心方法，后面的方法是Jdk1.8之后有关红黑树的操作，后面会讲到，先来看前两个方法。
哈希函数：hash()
hash() 方法是HashMap 中的核心函数，在存储数据时，将key传入中进行运算，得出key的哈希值，通过这个哈希值运算才能获取key应该放置在 “桶” 的哪个位置，下面是方法的源码：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
从源码中可以看出，传入key之后，hash() 会获取key的hashCode进行无符号右移 16 位，然后进行按位异或，并把运算后的值返回，这个值就是key的哈希值。这样运算是为了减少碰撞冲突，因为大部分元素的hashCode在低位是相同的，不做处理的话很容易造成冲突。
之后还需要把 hash() 的返回值与table.length - 1做与运算，得到的结果即是数组的下标(为什么这么算，下面会说)，在上面的 putVal() 方法中就可以看到有这样的代码操作，举个例子图：
table.length - 1就像是一个低位掩码（这个设计也优化了扩容操作的性能），它和hash()做与操作时必然会将高位屏蔽（因为一个HashMap不可能有特别大的buckets数组，至少在不断自动扩容之前是不可能的，所以table.length - 1的大部分高位都为0），只保留低位，这样一来就总是只有最低的几位是有效的，就算你的hashCode()实现得再好也难以避免发生碰撞。这时，hash()函数的价值就体现出来了，它对hash code的低位添加了随机性并且混合了高位的部分特征，显著减少了碰撞冲突的发生。
另外，在putVal方法的源码中，我们可以看到有这样一段代码
if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);
上面的注释也说明了，这是检测要插入位置是否有元素，没有的话直接新建一个包含key的节点，那么这里为什么要用 i = (n - 1) & hash 作为索引运算呢？
下面这段解释摘自http://www.importnew.com/29724.html
这其实是一种优化手段，由于数组的大小永远是一个2次幂，在扩容之后，一个元素的新索引要么是在原位置，要么就是在原位置加上扩容前的容量。这个方法的巧妙之处全在于&运算，之前提到过&运算只会关注n
– 1（n =
数组长度）的有效位，当扩容之后，n的有效位相比之前会多增加一位（n会变成之前的二倍，所以确保数组长度永远是2次幂很重要），然后只需要判断hash在新增的有效位的位置是0还是1就可以算出新的索引位置，如果是0，那么索引没有发生变化，如果是1，索引就为原索引加上扩容前的容量。
效果图如下：
这样在每次扩容时都不用重新计算hash，省去了不少时间，而且新增有效位是0还是1是带有随机性的，之前两个碰撞的Entry又有可能在扩容时再次均匀地散布开，真可谓是非常精妙的设计。
动态扩容：resize()
在HashMap中，初始化数组或者添加元素个数超过阈值时都会触发 resize() 方法，它的作用是动态扩容，下面是方法的源码：
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; //‘桶’数组的大小超过0，做扩容 if (oldCap > 0) { //超过最大值不会扩容，把阈值设置为int的最大数 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //向左移动1位扩大为原来2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } //旧数组大小为0，旧阈值>0，说明之前创建了哈希表但没有添加元素，初始化容量等于阈值 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults //旧容量、旧阈值都是0，说明还没创建哈希表，容量为默认容量，阈值为 容量*加载因子 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //新阈值还没有值，重新根据新的容量newCap计算大小 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; //不为空，代表是扩容操作 if (oldTab != null) { //遍历旧数组的每一个‘桶’，移动到新数组newTab for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; //节点是树形节点，需要对红黑树进行拆分 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order //普通链表节点，遍历链表，并将链表节点按原顺序进行分组 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
上面的源码有点长，但总体逻辑就三步：
- 计算新桶数组的容量大小 newCap 和新阈值 newThr
- 根据计算出的 newCap 创建新的桶数组，并初始化桶的数组table
- 将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型，则需要拆分红黑树 (调用**split()**方法 )。如果是普通节点，则节点按原顺序进行分组。
前面两步的逻辑比较简单，这里不多叙述。重点是第三点，涉及到了红黑树的拆分，这是因为扩容后，桶数组变多了，原有的数组上元素较多的红黑树就需要重新拆分，映射成链表，防止单个桶的元素过多。
红黑树的拆分是调用TreeNode.split() 来实现的，这里不单独讲。放到后面的红黑树一起分析。
节点树化、红黑树的拆分
红黑树的引进是HashMap 在 Jdk1.8之后最大的变化，在1.8以前，HashMap的数据结构就是数组加链表，某个桶的链表有可能因为数据过多而导致链表过长，遍历的效率低下，1.8之后，HashMap对链表的长度做了处理，当链表长度超过8时，自动转换为红黑树，有效的提升了HashMap的性能。
但红黑树的引进也使得代码的复杂度提高了不少，添加了有关红黑树的操作方法。本文只针对这些方法来做解析，不针对红黑树本身做展开，想了解红黑树的读者可以看我之前的文章
数据结构：红黑树的结构以及方法剖析 (上) 以及 数据结构：红黑树的结构以及方法剖析 (下)
节点树化
HashMap中的树节点的代码用 TreeNode 表示：
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); }
可以看到就是个红黑树节点，有父亲、左右孩子、前一个元素的节点，还有个颜色值。知道节点的结构后，我们来看有关红黑树的一些操作方法。
先来分析下树化的代码：
//将普通的链表转化为树形节点链表 final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; // 桶数组容量小于 MIN_TREEIFY_CAPACITY，优先进行扩容而不是树化 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; do { //把节点转换为树形节点 TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) //把转化后的头节点赋给hd hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) // 树形节点不为空，转换为红黑树 hd.treeify(tab); } } TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { return new TreeNode<>(p.hash, p.key, p.value, next); }
上面的代码并不太复杂，大致逻辑是根据hash表的元素个数判断是需要扩容还是树形化，然后依次调用不同的代码执行。
值得注意的是，在判断容器是否需要树形化的标准是链表长度需要大于或等于 MIN_TREEIFY_CAPACITY，前面也说了，它是HashMap的成员变量，初始值是64，那么为什么要满足这个条件才会树化呢？
下面这段摘自https://segmentfault.com/a/1190000012926722#articleHeader6
当桶数组容量比较小时，键值对节点 hash
的碰撞率可能会比较高，进而导致链表长度较长。这个时候应该优先扩容，而不是立马树化。毕竟高碰撞率是因为桶数组容量较小引起的，这个是主因。容量小时，优先扩容可以避免一些列的不必要的树化过程。同时，桶容量较小时，扩容会比较频繁，扩容时需要拆分红黑树并重新映射。所以在桶容量比较小的情况下，将长链表转成红黑树是一件吃力不讨好的事。
所以，HashMap的树化过程也是尽量的考虑了容器性能，再看回上面的代码，链表树化之前是先把节点转为树形节点，然后再调用 treeify() 转换为红黑树，并且树形节点TreeNode 继承自 Node 类，所以 TreeNode 仍然包含 next 引用，原链表的节点顺序最终通过 next 引用被保存下来。
下面看下转换红黑树的过程：
final void treeify(Node<K,V>[] tab) { TreeNode<K,V> root = null; for (TreeNode<K,V> x = this, next; x != null; x = next) { next = (TreeNode<K,V>)x.next; x.left = x.right = null; if (root == null) { //第一次进入循环，确定头节点，并且是黑色 x.parent = null; x.red = false; root = x; } else { //后面进入循环走的逻辑，x 指向树中的某个节点 K k = x.key; int h = x.hash; Class<?> kc = null; //从根节点开始，遍历所有节点跟当前节点 x 比较，调整位置， for (TreeNode<K,V> p = root;;) { int dir, ph; K pk = p.key; if ((ph = p.hash) > h) //当比较节点的哈希值比 x 大时， dir 为 -1 dir = -1; else if (ph < h) //哈希值比 x 小时 dir 为 1 dir = 1; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) // 比较节点和x的key dir = tieBreakOrder(k, pk); TreeNode<K,V> xp = p; //把 当前节点变成 x 的父亲 //如果当前比较节点的哈希值比 x 大，x 就是左孩子，否则 x 是右孩子 if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; root = balanceInsertion(root, x); break; } } } } moveRootToFront(tab, root); }
可以看到，代码的总体逻辑就是拿树中的节点与当前节点做比较，进而确定节点在树中的位置，具体实现的细节还是比较复杂的，这里不一一展开了。
红黑树拆分
介绍了节点的树化后，我们来学习下红黑树的拆分过程，HashMap扩容后，普通的节点需要重新映射，红黑树节点也不例外。
在将普通链表转成红黑树时，HashMap 通过两个额外的引用 next 和 prev 保留了原链表的节点顺序。这样再对红黑树进行重新映射时，完全可以按照映射链表的方式进行。这样就避免了将红黑树转成链表后再进行映射，无形中提高了效率。
下面看一下拆分的方法源码：
//map 容器本身 //tab 表示保存桶头结点的哈希表 //index 表示从哪个位置开始修剪 //bit 要修剪的位数（哈希值） final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { TreeNode<K,V> b = this; // Relink into lo and hi lists, preserving order // 修剪后的两个链表，下面用lo树和hi树来替代 TreeNode<K,V> loHead = null, loTail = null; TreeNode<K,V> hiHead = null, hiTail = null; int lc = 0, hc = 0; for (TreeNode<K,V> e = b, next; e != null; e = next) { next = (TreeNode<K,V>)e.next; e.next = null; //如果当前节点哈希值的最后一位等于要修剪的 bit 值，用于区分位于哪个桶 if ((e.hash & bit) == 0) { //把节点放到lo树的结尾 if ((e.prev = loTail) == null) loHead = e; else loTail.next = e; loTail = e; ++lc; } //把当前节点放到hi树 else { if ((e.prev = hiTail) == null) hiHead = e; else hiTail.next = e; hiTail = e; ++hc; } } if (loHead != null) { // 如果 loHead 不为空，且链表长度小于等于 6，则将红黑树转成链表 if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map); else { tab[index] = loHead; /* * hiHead ！= null 时，表明扩容后， * 有些节点不在原位置上了，需要重新树化 */ if (hiHead != null) // (else is already treeified) loHead.treeify(tab); } } //与上面类似 if (hiHead != null) { if (hc <= UNTREEIFY_THRESHOLD) tab[index + bit] = hiHead.untreeify(map); else { tab[index + bit] = hiHead; if (loHead != null) hiHead.treeify(tab); } } }
源码的逻辑大概是这样：拆分后，将红黑树拆分成两条由 TreeNode 组成的链表（hi树和lo树）。如果链表长度小于 UNTREEIFY_THRESHOLD，则将链表转换成普通链表。否则根据条件重新将 TreeNode 链表树化。这里用两张图来展示一下拆分前后的变化
红黑树拆分前：
拆分后：
至此，有关红黑树的一些转换操作就介绍完毕了，除此之外，hashMap还提供了很多操作红黑树的方法，原理都差不多，读者们可以自己去研究。
总结
HashMap的源码解析就告一段落了，最后，总结一下HashMap的一些特性：
1、HashMap 允许 key, value 为 null；
2、HashMap源码里没有做同步操作，多个线程操作可能会出现线程安全的问题，建议用Collections.synchronizedMap 来包装，变成线程安全的Map，例如：
Map map = Collections.synchronizedMap(new HashMap<String,String>());
3、Jdk1.7以前，当HashMap中某个桶的结构为链表时，遍历的时间复杂度为O(n)，1.8之后，桶中过多元素的话会转换成了红黑树，这时候的遍历时间复杂度就是O(logn)。
最后，感谢这几位大神的技术文章
https://blog.csdn.net/u011240877/article/details/53351188