Map(一)之HashMap（java8）

92 阅读 0 评论 61 点赞

我是靠谱客的博主安详小懒猪，这篇文章主要介绍Map(一)之HashMap（java8），现在分享给大家，希望可以做个参考。

概述【本文基于jdk1.8.0_60】

　　在我们日常开发中，HashMap被使用到的概率非常高。它是一种非常典型的数据结构。我们应该都知道Map是存储key-value键值对的集合类，也就是说元素是成对出现的。并且key可以为null但必须是唯一的。
　　

定义

复制代码

1
2
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

　　HashMap实现了Map接口，继承了AbstractMap。

基本属性

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

/**
* 默认初始容量(桶的数量)，16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/**
* 最大容量1*2^30
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认装载因子，此值表示当前容量的HashMap装entry满的程度，当entry数量大于当前容量与装载因子的
* 乘积时，HashMap就会进行rehash操作。也就是HashMap会扩充容量，扩充容量之后整个HashMap就会
* 重建
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
*当“桶”中的元素大于此阀值时使用树代替单向链表，这里的树实际上是红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 当“桶”中的元素小于此阀值时，树转成单向链表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
*HashMap中所有元素总数小于此值时，即使“桶”中元素超过TREEIFY_THRESHOLD也不转成树
*/
static final int MIN_TREEIFY_CAPACITY = 64;

构造

复制代码

1
2
3
4
5

//默认构造方法，装载因子设置为默认值0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13

//指定初始容量和加载因子
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);
}

复制代码

1
2
3
4
5

//指定初始容量
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

复制代码

1
2
3
4
5
6

//使用一个Map来初始化一个HashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}

底层存储

复制代码

1
2
3
4
5

/**
*HashMap底层实际上是一个Node<K,V>类型的数组
*/
transient Node<K,V>[] table;

简单画一下HashMap底层存储结构图：
这里写图片描述
上图描述的是一个容量为16(即16个桶)的的HashMap结构图。可以理解为是一个长度为16的Node类型的数组，每个数组元素都是一个链表的head结点。于是乎就构成了上面的结构。我们用默认构造方法创建的HashMap在没有resize之前容量就是16。

resize与树化

　　随着结点的增多，单个桶中的元素越来越大，即链表的长度越来越长。这样会导致get，remove（大家可以想一下链表的相关操作）等的性能越来越差，怎么办呢？HashMap中有对应的解决方案。

resize

　　HashMap中有一个叫做threshold的参数：

复制代码

1
2
3
4
5

/**
* The next size value at which to resize (capacity * load factor).
*/
int threshold;

这个参数表示当HashMap的size达到此值时就要进行resize操作。它是怎么计算来的呢？计算公式如下：

复制代码

1
threshold = capacity * load factor

拿上图举个例子，假如上图的HashMap是通过默认构造方法创建的。其中HashMap的容量为16，load_factor为默认值0.75 。所以threshold = 16 * 0.75 = 12 。也就是说当元素个数达到12时，就会发生resize操作。结构就会发生改变。看一下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;
//扩充容量会进入这个if语句块
if (oldCap > 0) {
//容量不能超过MAXIMUM_CAPACITY上限
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
//新容量为旧容量的2倍，新阀值为旧阀值的两倍。（<<1表示2进制左移一位，也就是乘以2）
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
//这个分支是应对使用不能构造方法创建HashMap的情况
} else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else {
// zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float) newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
(int) ft : Integer.MAX_VALUE);
}
//阀值赋值为新的值
threshold = newThr;
//创建一个更大容量的Node数组
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
//把新创建的数组赋值给table属性
table = newTab;
if (oldTab != null) {
//遍历旧数组中每个桶
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;
/**
*下面的是把旧HashMap中的元素放到新HashMap。映射算法后面再详细讲解
*/
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

final Node<K, V>[] resize() {
Node<K, V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//扩充容量会进入这个if语句块
if (oldCap > 0) {
//容量不能超过MAXIMUM_CAPACITY上限
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
//新容量为旧容量的2倍，新阀值为旧阀值的两倍。（<<1表示2进制左移一位，也就是乘以2）
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
//这个分支是应对使用不能构造方法创建HashMap的情况
} else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else {
// zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float) newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
(int) ft : Integer.MAX_VALUE);
}
//阀值赋值为新的值
threshold = newThr;
//创建一个更大容量的Node数组
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
//把新创建的数组赋值给table属性
table = newTab;
if (oldTab != null) {
//遍历旧数组中每个桶
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;
/**
*下面的是把旧HashMap中的元素放到新HashMap。映射算法后面再详细讲解
*/
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;
}

树化

　　我们观察会发现HashMap有两个属性：

复制代码

1
2
3

static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;

当HashMap的容量大于MIN_TREEIFY_CAPACITY 并且桶中元素数量大于等于TREEIFY_THRESHOLD 时，该桶中的元素结构就会由链表结构转成树结构以提高性能。看下源码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//这里是保证桶中元素和HashMap容量同时满足条件才对相应桶进行树化。否则只进行resize操作
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;
/**
*这里可以理解为把链表中每个结点都替换成树结点，世界上是创建一个新链表，结点类型
*由Node变为TreeNode
*/
do {
//创建树结点
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
//具体树化算法
hd.treeify(tab);
}
}

看一下树化之后的HashMap结构长什么样：
这里写图片描述

上图编号为1023的桶由于数量超过了阀值，所以有链表转成了树形结构。关于链表转成树的具体算法这里就不详细讲解了。
有树化过程当然就有“非树化”过程，我这里树的非树化就是树转链表。当然如果我们频繁做remove操作，链表里面的元素越来越少就会进行逆向操作。相应的“非树化”阀值参数定义如下：

复制代码

1
2
3
4
5
6
7

/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;

意思是当桶中元素个数小于UNTREEIFY_THRESHOLD 时，就会由树转成链表，当然，前提是你之前已经进行了树化操作。

其他创建流程

　　HashMap提供了4个构造方法，这使我们可以在创建HashMap的时候指定初始容量和加载因子。当我们使用这两个构造方法时有一点可能和你想的有点不一样，下面我们探讨一下：
　

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
　　//指定初始容量和加载因子
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);
}

复制代码

1
2
3
4
5

//指定初始容量
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

假如我们想创建一个初始容量为30的HashMap，也许你会这样写：

复制代码

1
Map<String, Object> map = new HashMap<>(30);

我们这样写实际上调用的是 public HashMap(int initialCapacity, float loadFactor) ，这里loadFactor是默认值，我们不管它，看最后一句。

复制代码

1
this.threshold = tableSizeFor(initialCapacity);

啊？initialCapacity和threshold什么关系？是不是感觉有点混乱？我们刚刚不是想创建容量为30的HashMap吗？为何这里把initialCapacity通过计算赋值给了threshold？别急！我们一步步来，先来看下这个tableSizeFor方法时干嘛的，上源码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13

/**
* Returns a power of two size for the given target capacity.
*/
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;
}

它的作用是根据传入的容量，返回2的幂次方大小的容量。你刚刚传的是30，这里会返回2^5=32。但是这个值也没有赋值给initialCapacity参数呀？继续看：
　　我们知道我们虽然new HashMap(30)，但此时HashMap里面的真正用来存储数组的Node数组table还是null呢：
　　

复制代码

1
2

transient Node<K,V>[] table;

　　此时当我们往HashMap中put元素时，如果table==null，就需要进行第一次resize操作：
　　这里写图片描述
　　
我们继续看resize方法：
　　
这里会把threshold 的值赋给newCap，然后根据这个newCap创建一个Node数组赋给table。然后根据newCap计算一个threshold赋值给threshold。此时的newCap的值为32，threshold的值为24 。所以我们刚开始使用Map<String, Object> map = new HashMap<>(30); 创建的map的容量不是30，而是32。

HashMap中映射算法介绍

1 key映射到桶

　　我们拿get(object key)方法来分析，key是如何映射到桶的，也就是HashMap如何知道key对应的元素存在哪个链表的？我们看下源码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

仔细观察有这么一行代码：tab[(n - 1) & hash] 其中hash的值就是key的哈希值，从中我们可以大致知道hash值是怎么映射到桶的。接下来我们通过例子来更深层次的探讨下：
　　假如我们通过构造方法创建了一个HashMap，那么它的初始容量是16。现在我们往HashMap中添加4个元素。假如这4个元素key的hash值分别是6、22、38、54（具体key的值是多少我们这里就不列出了）。现在我们看下这4个元素会映射到哪个桶？由于容量是16，所以n=16，那么n - 1) & hash 代入n就变成了15 & hash。我们把6、22、38、54 分别于 15 进行按位与操作，换算成二进制：
　　这里写图片描述
计算之后的结果全是6，于是这四个元素全部放到了table[6]中，即第6个桶。另外由于15二进制001111，除了低四位为1，其他高位全是0 。所以与15进行按位与结果永远不会大于15，所以不会超出table大小范围。这四个元素放到HashMap中的结构如图：

这里写图片描述

2 resize时key的重新映射
　　接着上面的例子讲，随着HashMap中元素的增多，我们建立的HashMap容量是16，加载因子loader_factor为0.75 。所以threshold = 16*0.75 = 12 所以当元素数量超过12时，HashMap就会resize。假如现在上例中元素刚好达到12，第6个桶中的元素还是上述那四个元素。我们看下这四个元素分别会重新映射到新table中的哪个桶。在开始讨论之前，先看下重新映射的代码：
　　
　　
我们知道原来HashMap的容量是16，resize之后容量是32 。旧数组中的元素映射到新数组中的算法就如上图所示。是不是有点晕？为什么要这样算呢？我们先看一下resize之前和之后往HashMap中添加元素是如何映射的，以key的hash值是6、22为例，映射算法分别是6 & 15与6 & 31 和22 & 15与22 & 31，换算成二进制计算如下图：

这里写图片描述

　　如上图所示，我们只观察从右往左第5位(前面4位都是一样的)，6的第5位为0，所以不论是与15还是31进行按位与操作结果都是一样的。然而22的第5位为1，所以与15和31的按位与结果不同。与31的按位与结果比15大了010000，也就是16(未resize前的容量大小)。可以理解为resize之后，元素在新HashMap中桶的位置是否改变，取决于原第5(在这个例子中是第五位)位是0还是1。那么代码中的算法就是按照第5位是0，还是1进行了分组。代码中的hash&oldCap，刚好可以区分第5位是0还是1 。看例子：
　　
这里写图片描述
结果为0的第5位是0，否则第5位不为0 。
说明一下：上述算法只有当resize之后是之前的2倍的基础上才成立。换算成2进制就是左移了一位：newCap = oldCap <<1 ，这个是必要条件。否则上述算法就不对了。不知道我有没有讲清楚。
下面看下resize前后结构图：
这里写图片描述

HashMap的bug

　　我们知道，旧版本jdk中HashMap在多线程条件下rehash操作有可能会产生无限循环的问题。不了解此问题的麻烦搜索下相关问题，这里不做描述。在jdk1.8中(我研究的这个版本)，此问题已经得到解决。(我看其他人写的博客中还提到说java8中hashMap死循环的问题，他们应该是搞错了)。产生无限循环的本质就是链表中产生了环，而java8中不具有产生环的条件，所以不会产生无限循环。但是产生了其他bug。

1. 为何不会产生环

　　java8中resize时对每个桶进行的操作都是先将链表拆分成两个链表，然后分别将两个链表放到新table中对应的桶当中去。这个过程在多线程条件下不会产生环。

2. 其他bug（多线程条件下）

1 HashMap中有值，但是get出来为null。
　　来看下resize时有这么一行代码：
　　
　　如上图所示，在进行真正的元素移动前，先将newTab赋值给了table，这时table是空的，什么都没有，假如这个时候进行get操作，什么都取不到。
2 resize时元素丢失问题。
　　假设同时又两个线程thread1、thread2同时进行resize操作，初始状态图如下：
　　
　　
　　图中红色代表thread1，银灰色代表thread2，此时thread2被挂起，thread1执行到如下图：
　　
　　
　　
　　此时仔细观察会发现thread2指向的链表少了一个节点c。倘若此时thread1被挂起，thread2执行，直到遍历完整个链表：