前言
Map接口实现类包括：HashMap、TreeMap、Hashtable、LinkedHashMap、ConcurrentHashMap。根据key的hashcode值来存储数据，可以根据key获取value。
实现类之间的区别：
HashMap
- 不保存每个元素的插入顺序，无序存放（存放顺序与key的hash值有关）
- 具有很快的访问速度
- 最多只允许一条记录的key值为null(多条会覆盖)
- 允许多条记录的value为null
- 非同步；非线程安全
TreeMap
- 是通过红黑树实现的
- 默认key升序排序存放，可以写Comparator接口改变排序方式
- 不允许key的值为null
- 非同步
HashTable
- 不允许key、value的值为null
- 同步；线程安全（很多方法加了synchronized锁）
- 由于引入了线程安全，处理效率没有HashMap高
LinkedHashMap
- 基于HashMap和双向链表，有序存放
- 具有很快的访问速度
- 最多只允许一条记录的key值为null(多条会覆盖)
- 允许多条记录的value为null
- 非同步；非线程安全
ConcurrentHashMap
- 线程安全，读写快，底层实现是一种以空间换时间的结构，创建的时候直接分了16个segment，每个segment实际上存储的还是HashTable，写入的时候先找到对应的segment，然后对segment加锁，写完，解锁。锁segment的时候其他segment还可以继续工作。
- 使用场景：当项目中的全局变量有多线程操作时需要用ConcurrentHashMap
下面重点介绍HashMap原理。
数据结构
JDK1.8之前，HashMap是数组+链表存储。JDK1.8及其之后，先用数组+链表，当链表长度>=8时，就是数组+红黑树（原链表元素组成）。
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
| public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
static final int DEFAULT_INITIAL_CAPACITY = 16;
static final int MAXIMUM_CAPACITY = 1073741824;
static final float DEFAULT_LOAD_FACTOR = 0.75F;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
transient Node<K, V>[] table;
transient Set<Map.Entry<K, V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
static class Node<K, V> implements Map.Entry<K, V> {
final int hash;
final K key;
V value;
Node<K, V> next;
}
static final class TreeNode<K, V> extends LinkedHashMap.Entry<K, V> {
TreeNode<K, V> parent;
TreeNode<K, V> left;
TreeNode<K, V> right;
TreeNode<K, V> prev;
boolean red;
}
}
|
Node与TreeNode之间的继承关系： Map.Entry<K, V> –> HashMap.Node<K, V> –> LinkedHashMap.Entry<K, V> –> HashMap.TreeNode<K, V> 。所以Node是TreeNode的间接父类。
红黑树和MySQL索引结构B+树，都属于平衡二叉树。区别在于，红黑树一个节点只含一条数据，而B+树是B树的变种，B树一个节点含多条数据，用于查找的key和数据都在节点上，B+树的非叶子节点不再保存数据，而只保存key，叶子节点保存数据，并且所有的叶子节点按顺序使用链表进行连接。
相关博客：
红黑树的规则和原理，包括左旋右旋：https://www.cnblogs.com/LiaHon/p/11203229.html
负载因子0.75的作用：http://baijiahao.baidu.com/s?id=1656137152537394906&wfr=spider&for=pc
HashMap部分源码：https://itimetraveler.github.io/2017/11/25/%E3%80%90Java%E3%80%91HashMap%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90%EF%BC%88JDK1.8%EF%BC%89/#get-%E6%96%B9%E6%B3%95
PUT
put(key,value)时，HashMap先用key的hashcode计算出一个新的hash值，再用hash值和数组长度计算出一个数组下标。如果该数组位上为空，则直接添加key-value并返回NULL。如果该数组位上已经有元素，那么就遍历该数组位上的所有元素，比较要添加的key和现有元素是否相等，若相等就覆盖旧元素，并返回旧元素的value。若没有相等的，就直接添加进去。
向链表中添加元素时，用的是“尾插法”（JDK1.7中用的是“头插法”）。
比较key是否相同时，用的是equals方法，因为equals方法默认比较的是内存地址，所以如果用自定义类的对象做key，这个类需要重写equals方法。
关于hash值和数组下标的计算可以看这篇博客：https://www.cnblogs.com/eycuii/p/12015283.html 。理解了hash值和数组下标的原理，我们可以回答一个常见的面试题：
HashMap数组长度为什么都是2的k次方？
首先，对于计算机来说，使用像左移、右移、与或非这样的位运算，效率比人类习惯的加减乘除以及取模更高，所以源码里计算数组下标都是用位运算。用位运算，就要把数组长度值转为二进制，任何数都能转为二进制，为什么偏偏指定2的k次方？因为计算数组下标时，公式是i = hash & (length - 1)，当length=2^k时，length - 1就是在低k位连续分布的1，这样在做“与”运算时，能够完全利用hash的低k位的所有值，使得多个hash的“与”结果不同，达到了分散数组位的目的。
(2^k) - 1 = 2^(k-1) + 2^(k-2) + … + 1，这是由等比数列求和公式得到的。
put方法源码：
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
| public V put(K paramK, V paramV) {
return (V) putVal(hash(paramK), paramK, paramV, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
|
RESIZE
resize()方法为私有，调用点都在HashMap内部。具体在：
- put(key,value)，具体见上一节源码
- new HashMap(map2)或putAll(map2)，批量添加map元素
- put(key,value)中链表转红黑树时treeifyBin()方法
- computeIfAbsent()方法内
- compute()方法内
- merge()方法内
resize()方法是JDK1.8和1.7的区别比较大的地方。区别在于：
- JDK1.8引入了红黑树的处理
- 重新安排链表元素时，计算新下标的方式。虽然方式不同，但结果不变
- 元素插入链表的方式。1.7用头插法，1.8用尾插法
下面借助两个版本的resize()源码讲讲这些区别。
JDK1.7的resize方法：
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
| void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int) (newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K, V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K, V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
static int indexFor(int h, int length) {
return h & (length - 1);
}
|
JDK1.8的resize方法：
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
| 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 (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
else if (oldThr > 0)
newCap = oldThr;
else {
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;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
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 {
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;
}
|
区别一
区别1：JDK1.8引入了红黑树的处理。
在TreeNode.split()方法中，会把当前树拆分成两个子链表，然后判断两个子链表的节点数，节点数<=6，就按照链表存储，否则转为红黑树，即“树化”。树化时，遍历树的所有节点的时间复杂度是O(n)，插入树节点的时间复杂度是O(logn)，所以创建红黑树的总时间是O(nlogn)。
顺便一提，resize处理链表时，是一边遍历一边插入，遍历链表的时间复杂度为O(n)，插入的时间复杂度是O(1)，所以创建链表的总时间是O(n)。
附上TreeNode.split()方法源码：
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
| final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
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;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null)
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);
}
}
}
|
参考：
HashMap内部类TreeNode主要方法源码和解释：https://www.cnblogs.com/freeorange/p/10804332.html
红黑树的时间复杂度O(logn)的证明：https://blog.csdn.net/l_o_s/article/details/105703296 （红黑树查找、插入和删除操作的时间复杂度都是O(logn)）
区别二
区别2：重新安排链表元素时，计算新下标的方式。虽然方式不同，但结果不变。
在1.7中，无论什么情况，新数组位 = e.hash & (newCap - 1)。在1.8中，当只有一个元素时，新数组位的计算和1.7一致；当是链表元素时，新数组位只有“原下标”和“原下标+oldCap”两种位置，而具体是哪个位置，就看(e.hash & oldCap)的值是否等于0。
乍一看，在1.8中重新安排链表元素时，因为只有两种选择，似乎会加大冲突概率。但实际上，这个做法和1.7的重新计算下标的结果，是完全一致的！！
我们举例看看在1.7中计算出的新下标的规律：
设：oldCap = 16, newCap = 32, key1.hash = 107 = (0110 1011), key2.hash = 123 = (0111 1011)
则，key1的原下标 = (key.hash) & (oldCap - 1) = (0110 1011) & (0000 1111) = (0000 1011) = 11
扩容后，key1的新下标 = (key.hash) & (newCap - 1) = (0110 1011) & (0001 1111) = (0000 1011) = 11
则，key2的原下标 = (key.hash) & (oldCap - 1) = (0111 1011) & (0000 1111) = (0000 1011) = 11
扩容后，key2的新下标 = (key.hash) & (newCap - 1) = (0111 1011) & (0001 1111) = (0001 1011) = 27 = 16 + 11
在1.7中，即使是重新计算下标，新下标依然只有两种结果：“原下标”和“原下标+oldCap”，这是因为(newCap - 1)只是比(oldCap - 1)多了一位高位1，这个高位1的值就等于oldCap（证明如下）。而这个高位1的值是否对“与”结果起作用，就是看与此高位1对应的key.hash的位上是0还是1，是1才起作用。这就和1.8的逻辑对应上了！
(newCap - 1) - (oldCap - 1)
= (2^(k+1) - 1) - (2^k - 1)
= (1 + … + 2^(k-1) + 2^k) - (1 + … + 2^(k-1))
= 2^k
= oldCap
所以，1.8并没有改变新下标的结果，只是代码写得更直接了。
区别三
区别3：元素插入链表的方式。1.7用头插法，1.8用尾插法。
1.7的头插法是HashMap线程不安全的一个原因，简单来说就是多线程会造成环形链表导致死循环。
假设原HashMap：
table[0]=null
table[1]=(3,a)->(7,b)
当在多线程进行扩容时，
线程A遍历到元素(3,a)->(7,b)->null停止，
线程B开始执行到扩容后：table[3]=(7,b)->(3,a)->null（先遍历到的是(3,a)键值对，先插入到新位置的也是(3,a)，随后遍历到(7,b)，(7,b)的新位置也在table[3]，因为使用的是头插法，所以在(3,a)前面）
然后线程A继续执行，计算到(3,a)新位置在table[3]，把(3,a)插入table[3]的链表，而此时table[3]=(7,b)->(3,a)->null，导致table[3]=(3,a)<=>(7,b)，这两个元素互相指向，在遍历table[3]位置的链表时就会进入死循环。
这篇博客：https://www.cnblogs.com/developer_chan/p/10450908.html 中的1.1 扩容造成死循环分析过程用图片讲解，可参考。
因为改用了尾插法，所以1.8避免了1.7的环形链表的问题。但是，1.8的红黑树还是会出现死循环的情况，只是没人像1.7一样给出具体的过程，仅仅做了实验，实验博客：https://blog.csdn.net/gs_albb/article/details/88091808 。
1.8的优化
从源码来看，JDK1.8优化的主要是查询性能，因为1.8不会出现过长的链表（都转为红黑树了~），时间复杂度由链表的O(n)降低为红黑树的O(logn)。扩容方法resize优化了环形链表的问题，但性能看不出优化。先说简单的，计算新下标时，1.7直接用位运算得出新下标，1.8除了位运算还有加法运算，不会比1.7更快。然后，正如在区别一中所述，创建红黑树的时间复杂度比创建链表要大，所以1.8的resize性能肯定不会比1.7好。
线程安全问题
JDK1.7和1.8都是线程不安全的，其中一个原因是扩容时会导致死循环，另一个原因是put方法：
1
2
3
4
5
6
7
8
9
10
| final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
}
|
HashTable的线程安全
