浅析JDK1.8 HashMap源码。

写在开篇

HashMap是最常用的数据结构之一，是JDK中util包下的一个集合类，基于Map接口实现、允许null键/值、非同步、不保证有序(比如插入的顺序)、也不保证顺序不随时间变化。

类的继承关系

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

继承于抽象的AbstractMap，实现了Map，Cloneable，Serializable这三个接口。

HashMap构造函数

我们看下不带参数的构造方法：

1
2
3
4
5
6
7
/**
 * Constructs an empty {@code HashMap} with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
	this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

我们可以看到HashMap的构造函数中只是简单地为负载因子（loadFactor）赋了一个默认的值0.75，其他的什么都没做。

HashMap的put函数

向HashMap中插入一个键值对主要涉及到下面的三个函数：

1
2
3
public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}

在进一步了解putVal之前，我们还需要知道后面我们会讲到的table究竟是何方神圣。

1
2
3
4
5
6
7
/**
 * The table, initialized on first use, and resized as
 * necessary. When allocated, length is always a power of two.
 * (We also tolerate length zero in some operations to allow
 * bootstrapping mechanics that are currently not needed.)
 */
transient Node<K,V>[] table;	//实际上table就是HashMap中的数组。

putVal函数才是真正的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
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
/**
 * Implements Map.put and related methods.
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
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;
    		/* 	//调用resize()初始化数组

            	final Node<K,V>[] resize() {
                    Node<K,V>[] oldTab = table;
                    int oldCap = (oldTab == null) ? 0 : oldTab.length;	//0
                    int oldThr = threshold;	//0
                    int newCap, newThr = 0; 
                    if (oldCap > 0) {
                        //...
                    }
                    else if (oldThr > 0) 
                        //...
                    else {   //初始化数组容量和阈值
                        newCap = DEFAULT_INITIAL_CAPACITY;	//16
                        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);	// 0.75 * 16 = 12（也就是map的size达到12时，就会扩容）
                    }
                    if (newThr == 0) {
                        //...
                    }
                    threshold = newThr;	//将新阈值赋给threshold
                    @SuppressWarnings({"rawtypes","unchecked"})
                    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
                    table = newTab;
                    if (oldTab != null) {
                        //...
                    }
                    return newTab;	//返回初始化的新数组
            	}
            */
    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))))	//key值相等
            e = p;
        else if (p instanceof TreeNode)	//p为树结点
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {	//p为链表结点
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {	// 尾插法插入新结点
                    p.next = newNode(hash, key, value, null);
                    //static final int TREEIFY_THRESHOLD = 8;
                    if (binCount >= TREEIFY_THRESHOLD - 1) // 超过TREEIFY_THRESHOLD将把链表转化为红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // 存在key冲突（key值相同）
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //modCount是此HashMap经过结构修改的次数
    ++modCount;
    if (++size > threshold)
        resize();	//这里的resize()是扩容的含义了
    afterNodeInsertion(evict);
    return null;
}

接下来我们讲讲resize扩容操作（当map的size达到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
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
86
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) {	
        //超过HashMap的容量上限就不再继续扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //新容量为原容量的2倍，新的上线为原上线的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    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]不为空
                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 { //按照原顺序插入链表节点（不同于jdk1.7）
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        /*
                         *(e.hash & oldCap) == 0
                         * 如果这个判断为true则说明e这个节点在resize之后不需要挪位置，反之则需要换个位置。
                         * 虽然这个代码难理解，但是自己举几个例子也能判断出来
                         * 比如有1，17两个数，在HashMap大小是16的时候，他们的hash值都是1，
                         * 如果此时扩容为32，可以看出1的hash是不变的，
                         * 但是17是会变，也就是说 1 & 16 = 0， 17 & 16 != 0
                         */
                        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如何降低冲突

主要从两个地方来说明：

为什么HashMap要采用2的n次方的数量级作为数组的长度

答案是因为HashMap需要用length-1的数量级和hash值做一个与操作

1
p = tab[i = (n - 1) & hash]

如果长度是17,那么length-1就是16那么与下来的值要么是0要么是16,也就是说16个槽子只用了两个槽,效率是很低的,而如果采用16(2的四次方),就是15(01111)做与操作,均匀分不到0-15的槽子上
我们可以从下面的例子中说明问题：

1
2
3
4
5
n = 17 -> 0001 0001
n - 1  -> 0001 0000

假设hash值为 0000 0001 那么和(n-1)执行&运算后结果为 0000 0000
假设hash值为 0000 0011 那么和(n-1)执行&运算后结果为 0000 0000

如果长度是17,那么length-1就是16，那么与下来的值要么是0要么是16,也就是说16个槽子只用了两个槽,效率是很低的。

1
2
3
4
5
n = 16 -> 0001 0000
n - 1  -> 0000 1111

假设hash值为 0000 0001 那么和(n-1)执行&运算后结果为 0000 0001
假设hash值为 0000 0011 那么和(n-1)执行&运算后结果为 0000 0011

而如果长度是16,那么length-1就是15，做与操作可以均匀分配到0-15的槽子上。

hash函数

如果是自己实现hash算法的话，最简单的话就是直接用hasCode对(n-1)取余：

1
index = key.hasCode() & (n-1)

这种方法是有缺陷的，就是取余的计算结果对高位是无效的，只是对低位有效，当计算出来的hasCode()只有高位有变化时，取余的结果还是一样的。

当key计算出来的hashCode()只有高位变化时，最终算出来的index索引就会引起hash冲突，如果冲突太多的话，HashMap的效率就会非常低下了。

我们看看JDK1.8中hash算法的实现。

1
2
3
4
5
6
static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }
   
   index = (n - 1) & hash(key) //n表示长度

首先，对hashCode进行16位的无符号右移，然后对自身进行异或运算，最后取余。通过上面的操作，hash能够把高位的变化影响到低位的变化。

至于为什么是使用异或（^）,因为&和|都会使得结果偏向0或者1 ,并不是均匀的概念。

HashMap的get函数

get()比较简单，直接贴源码。

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;
}

HashMap的remove函数

remove()和get()差不多，通过node将查找的结点记录下，再进行删除相关的操作。

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
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

为什么HashMap是线程不安全的

JDK1.7 HashMap中出现的死循环、数据丢失已经得到了解决，可是它仍然存在数据覆盖的问题。

在putVal()如果不存在hash冲突：

1
2
if ((p = tab[i = (n - 1) & hash]) == null) // 如果没有hash碰撞则直接插入元素
    tab[i] = newNode(hash, key, value, null);

假设两个线程A、B都在进行put操作，并且hash函数计算出的插入下标是相同的，当线程A执行完if ((p = tab[i = (n - 1) & hash]) == null)后由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，从而线程不安全。

putval()最后size+1的时候：

1
2
if (++size > threshold)
    resize();

++size，一个最常见的线程不安全问题，还是由于数据覆盖又导致了线程不安全。

被transient所修饰table变量

最后还想提一个容易被大家忽略的点，如果大家细心阅读HashMap的源码，会发现桶数组table被申明为transient。transient表示易变的意思，在Java中，被该关键字修饰的变量不会被默认的序列化机制序列化。我们再回到源码中，考虑一个问题：桶数组table是HashMap底层重要的数据结构，不序列化的话，别人还怎么还原呢？

这里简单说明一下吧，HashMap并没有使用默认的序列化机制，而是通过实现readObject/writeObject两个方法自定义了序列化的内容。这样做是有原因的，试问一句，HashMap中存储的内容是什么？不用说，大家也知道是键值对。所以只要我们把键值对序列化了，我们就可以根据键值对数据重建HashMap。有的朋友可能会想，序列化table不是可以一步到位，后面直接还原不就行了吗？这样一想，倒也是合理。但序列化talbe存在着两个问题：

  1. table 多数情况下是无法被存满的，序列化未使用的部分，浪费空间
  2. 同一个键值对在不同 JVM 下，所处的桶位置可能是不同的，在不同的 JVM 下反序列化 table 可能会发生错误。

以上两个问题中，第一个问题比较好理解，第二个问题解释一下。HashMap的get/put/remove等方法第一步就是根据hash找到键所在的桶位置，但如果键没有覆写hashCode方法，计算hash时最终调用Object中的hashCode方法。但Object中的hashCode方法是native型的，不同的JVM下，可能会有不同的实现，产生的hash可能也是不一样的。也就是说同一个键在不同平台下可能会产生不同的 hash，此时再对在同一个table继续操作，就会出现问题。

参考：
transient所修饰table变量 https://segmentfault.com/a/1190000012926722?utm_source=tag-newest#item-3-6