Java基础
HashMap, JDK8

HashMap源码分析JDK8

数据存储结构

JDK7中数据结构的存储由数组+链表的方式，因为数组是一组连续的内存空间，易查询，不易增删，而链表是不连续的内存空间，通过节点相互连接，易删除，不易查询。

JDK8中为了解决hash碰撞过于频繁和链表过长查询效率过低，采用数组+链表+红黑树的存储方式，当链表长度超过阈值8且数组长度超过64时，将链表转换为红黑树。极大的提高了查询效率。

JDK8中HashMap存储结构

在JDK8中默认容量，最大容量以及装载因子等默认值未发生变化。但是多了一些树相关的属性。

1
2
3
4
5
6
7
8
9
10
11
12
13
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 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;

JDK8中hash方法有略微的简化了，可能是因为引用了红黑树，没有必要再对hashCode过于离散化。

1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

构造方法略微变化，最大的变化是将获取table的容量的方法tableSizeFor进行了优化，功能还是一样获取大于等于cap的最接近的2的幂的数作为数组的容量，且移位方式由带符号右移变成了无符号右移，在构造方法中就计算好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
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(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
// 获取大于等于cap的最接近的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;
}

添加方法

在JDK8中table的扩容是在添加元素后再进行的。当table为空时通过resize()方法对table进行初始化，以及++size > threshold时通过resize()方法对table的扩容。

如果新插入的元素的key不存在与链表中，则将新元素插入到对应链表的尾部，相对于JDK7的头插法，采用高低位拆分转移方式，避免了链表环的产生 ，解决了并发情况下的死循环问题。当插入新元素后链表的长度大于等于8且数组长度超过64时，会通过treeifyBin方法将链表转换成红黑树。

如果新插入的元素的key存在于链表中，退出for (int binCount = 0; ; ++binCount)循环，将旧值替换为新的值。其中13、14行干的是同样的事。

如果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
50
51
52
53
54
55
56
57
58
59
60
61
62
public V put(K key, V value) {
    return putVal(hash(key), key, value, 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; // 若table没有被初始化，进行初始化
    if ((p = tab[i = (n - 1) & hash]) == null) // 若插入的元素的hash对应的数组的槽为空
        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; // 相同的Key
        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) // 若链表的长度大于等于8了
                        treeifyBin(tab, hash); // 转换为红黑树
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break; // 相同的Key，则退出循环，去替换旧值
                p = e; // 下移指针
            }
        }
        if (e != null) { // 若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;
}
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize(); // 若数组长度小于64，则进行扩容，而不是转红黑树
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do { // 将Node转换成TreeNode
            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); // 将简单树转换成共黑树
    }
}

threshold的值在构造方法中被赋值为table的capacity，但是在resize()方法中被重新设置为capacity * loadFactor。这里对table的扩容以及threshold调整都是通过向左移位来完成的。

43行的if判断，主要是为了将老的table中的一个链表按照高位和低位拆分成两个链表。这个跟JDK是类是的，只不过JDK7是使用的头插法，这里是使用的尾插法，实现方式不一样。高位链表的数据下标按照JDK7的实现方式就为hiHead.hash & (newCap - 1)其实就等于这里的j + oldCap。

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
final Node<K,V>[] resize() { // 初始化table或扩容table
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length; // 未被初始化为0，否则为数组长度
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) { // 若已经是最大容量了，则无需在扩容了
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 若旧容量的两倍小于最大容量，且旧容量大于等于默认容量时，将新的threshold扩展为原来的两倍
        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;
    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 { // 采用高低位的方式将旧链表中的数据拆分成两个高低位链表
                    Node<K,V> loHead = null, loTail = null; // 低位
                    Node<K,V> hiHead = null, hiTail = null;	// 高位
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 通过判断最高位是否为0，来确定其在新数组中的高低位
                        if ((e.hash & oldCap) == 0) { // 若为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;
}

resize()方法中当table存储的元素是红黑树时，将通过split方法按照hash值得高低位将一颗树拆分成两棵树。如果拆分后树得节点个数小于等于UNTREEIFY_THRESHOLD = 6时，将树转换回链表。否正将loHead和hiHead转换成红黑树。

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
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) { // 通过判断最高位是否为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) // 若个数小于6，则将红黑树转回链表
            tab[index] = loHead.untreeify(map); 
        else {
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab); // 将普通的树转换成红黑树
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD) // 若个数小于6，则将红黑树转回链表
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab); // 将普通的树转换成红黑树
        }
    }
}
final Node<K,V> untreeify(HashMap<K,V> map) {
    Node<K,V> hd = null, tl = null;
    for (Node<K,V> q = this; q != null; q = q.next) {
        Node<K,V> p = map.replacementNode(q, null); // 将红黑树转换成链表
        if (tl == null)
            hd = p;
        else
            tl.next = p;
        tl = p;
    }
    return hd;
}