基于HashMapJDK1.8中的源码
参考前辈们的成果，简单的分析HashMap的源码，了解一下HashMap的存储结构，主要方法工作原理和线程安全这几个方面。
简介
Java为数据结构中的映射定义了一个接口java.util.Map，此接口主要有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap，类继承关系如下图所示：
下面对各个实现类的特点做一些说明：
-
HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
-
Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。
-
LinkedHashMap：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。
-
TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。
对于上述四种Map类型的类，要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。
通过上面的比较，我们知道了HashMap是Java的Map家族中一个普通成员，鉴于它可以满足大多数场景的使用条件，所以是使用频度最高的一个。
以上都不是我写的，摘自美团的技术博客：Java 8系列之重新认识HashMap，233333
存储结构
HashMap内部究竟是怎样的结构呢？看一下源码就明白了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //用来定位数组索引位置
final K key;
V value;
Node<K,V> next; //链表的下一个node
Node(int hash, K key, V value, Node<K,V> next) { ... }
public final K getKey(){ ... }
public final V getValue() { ... }
public final String toString() { ... }
public final int hashCode() { ... }
public final V setValue(V newValue) { ... }
public final boolean equals(Object o) { ... }
}
|
- 从源码可知，HashMap的键值对存储在
Node中。HashMap的字段中有又有一个Node的数组：table。也就是说我们的数据存储在这个哈希表中。
- 哈希表会发生哈希冲突，HashMap为了解决哈希冲突使用了哪种方法呢？一般的，我们有 linear probing（线性探测，也有叫开放地址法的） 和 separate chaining（链地址法）两种方式。显而易见，HashMap使用了链地址法。
讲到这里，你可以停下来去实现一个使用 linear probing 或者 separate chaining 实现的简单的哈希表，如果你学过数据结构的话应该很简单，这里我简单的实现了一下：
有参考《算法 第四版》中symbol table的内容
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
|
public class SeparateChainingHashST<Key, Value> {
private int M = 97;
// 没有扩容机制，哈希表的长度固定为97
private Node[] st = new Node[M];
private static class Node {
private Object key; //no generic, because array creation
private Object val;
private Node next;
Node(Object key, Object val, Node next) {
this.key = key;
this.val = val;
this.next = next;
}
}
private int hash(Key key) {
// 与上0x7fffffff，使得符号位变为0。如果是正数，值不变，如果是负数，则相当于值加上2^32-1
// M 是素数
// 取模消耗较大
return (key.hashCode() & 0x7fffffff) % M;
}
public void put(Key key, Value value) {
int i = hash(key);
Node x = st[i];
while (x != null) {
// 寻找重复的key，找到就覆盖原理的值
if (key == x.key || (key != null && key.equals(x.key))) {
x.val = value;
return;
}
//不相等把指针往下移动
x = x.next;
}
st[i] = new Node(key, value, st[i]); //插入到链表头部
}
public Value get(Key key) {
int i = hash(key);
for (Node first = st[i]; first != null; first = first.next) {
if (key.equals(first.key)) {
return (Value) first.val;
}
}
return null;
}
}
|
可以看到我这里实现的哈希表的哈希桶（源码中叫hash bin node,）数组的大小固定为97。那么在HashMap中是怎么确定数组的大小的呢？
如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组（Node[] table）占用空间又少呢？答案就是好的Hash算法和扩容机制。
在说明Hash算法和扩容机制之前，我们先要了解一下几个相关的字段。
1
2
3
4
|
int threshold; // 所能容纳的key-value对，如果超过会扩容
final float loadFactor; // 负载因子
int modCount;
int size;
|
table的初始化长度（capacity）(默认值是16)。HashMap中table的长度一定是2的幂。为什么这样设计呢？其实是为了根据key的hashCode快速确定其下标。
-
load factor为负载因子(默认值是0.75)。
-
threshold是HashMap所能容纳的最大数据量的Node(键值对)个数，threshold = capacity * load factor。*当哈希桶数组没有被初始化时，threshold为capacity的值或者为0。*键值对数量超过threshold就会进行扩容，扩容之后，capacity为原来的两倍。
-
size是HashMap中键值对的个数，而不是table的长度（capacity）。
-
modCount字段主要用来记录HashMap内部结构发生变化的次数，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。
JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能。
主要方法
Hash算法
一个好的Hash算法可以减少哈希碰撞，使得元素的分布尽量均匀。HashMap的Hash算法主要分为三步：
- key的hashCode
- 高位XOR低位
- 巧妙的取模运算
1
2
3
4
5
6
|
static final int hash(Object key) {
int h;
// 第一步：key.hashCode()
// 第二步： h ^ (h >>> 16)
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
|
通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的长度比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。
在putVal中有如下的语句，可知最终的下标为(capacity - 1) & hash。
1
2
3
4
5
6
7
8
9
|
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// ....
// 第三步：取模，(n - 1) & hash, 其中n为哈希桶数组的长度。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//...
}
|
为什么取模运算变成了按位与运算呢？或者说为什么可以这样做？
因为HashMap的哈希桶数组的长度总是2的n次方，当长度总是2的n次方时，h& (capacity-1)运算等价于对长度取模，也就是h%capacity，而&比%具有更高的效率。
我们都知道h / (2^n)相当于h >> n，即逻辑右移n位。而被移掉的n位就是余数。而h & (2^n - 1)就是取h的后n位二进制，也就是在除法运算中被移掉的n位，所以h & (2^n - 1)相当于h % 2^n。
下面为美团博客中的例子：
put方法
HashMap的put方法执行过程可以通过下图来理解：
-
判断键值对数组table[i]是否为空或为null，执行resize()进行扩容。注意：table的初始化是在第一次put中执行的。
-
根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向6，如果table[i]不为空，转向3；
-
判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向4，这里的相同指的是hashCode以及equals的返回值相等；
-
判断table[i] 是否为TreeNode，即table[i]是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
-
遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
-
插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
JDK1.8的putval源码如下：
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
|
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//步骤1：如果为null，则利用resize进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//步骤2：如果该数组项为null，直接新建节点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//步骤3：如果key值重复，直接覆盖
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//步骤4：如果该节点为TreeNode，在红黑树中插入节点
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);
// TREEIFY_THRESHOLD = 8
//步骤5：判断链表长度是否大于8，大于8 把链表转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果链表项key重复，直接覆盖
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//步骤6：插入成功后，检查size是否大于threshold，大于就进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
|
扩容机制
我们在putval方法中有提过过扩容，HashMap会在两种情况下进行扩容：
- 在哈希桶数组没有初始化时，调用
put方法时会调用resize进行初始化
- 当size大于threshold时
- 当某条链表的长度大于8，但是哈希桶数组大大小小于64时，进行扩容，而不是树型化链表
resize的实现过程可以参考下面的流程图，省略了一些不必要的细节
PS：这次的图终于是我自己画的啦n(≧▽≦)n，用的processon。
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
80
81
82
83
84
85
|
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;
}
// 原来capacity的两倍也没有超过最大值，进行扩容
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
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);
}
// 重新计算threshold
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;
//链表中只有一个节点，直接根据下标插入table
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和下标需要改变的node。
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 扩容是把capacity乘以2，这样新的hash值相当于高位多出一位。
// 判断hash多出来的一位是否为0，为0的话，那么它的下标不变
// 为1的话，它的下标变为原下标+oldCap
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;
}
|
在复制数据的时候，不需要重新计算下标。只需要看看原来的hash值新增的那个bit是1还是0，是0的话下标没变，是1的话下标变成原下标+oldCap。
美团博客中的例子如下：
线程安全
HashMap不是线程安全的，在多线程的环境下使用可能会发生死循环。可以使用线程安全的ConcurrentHashMap，HashTable也是线程安全的，但是效率低。关于这部分的内容，大概会在review到线程的时候，再详细的写一写吧。
参考
JDK1.8 HashMap 源码
《Algorithms 4th》
Java 8系列之重新认识HashMap
HashMap源码分析（JDK 1.8）
酷壳：JAVA HASHMAP的死循环