Java集合类源码解析：HashMap (基于JDK1.8)
目录
前言
今天我们来学习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)。
心得
最后，说下心得，老实说，在写这篇文章之前，我对hashmap只是的了解仅仅停留在用过的层面，没有对源码做深入的了解，直到心血来潮想学习下java的集合类才去看hashmap的源码，看完源码后，我被深深的震撼了，说实话，我没想过平时最常见的工具类的源码是这么复杂，一个hashmap就涉及到了如此众多的技术知识，比如红黑树，链表转换，hash运算等，通过简单的代码就整合了这些知识点，而且还保证了hashmap的高效性能。说实话，我对设计者是非常佩服的，估计此生我都写不出如此牛逼的代码。我也终于能理解为什么那么多公司面试时很喜欢问集合类的底层实现了，因为集合中涉及的技术知识是非常高深的，若能吃透集合类的源码，那人能不nb吗？
最后，感谢这几位大神的技术文章
上一篇： 05替换空格
下一篇： pymongo的简单使用