Java Map

———— JDK 1.8
words: 7.9k    views:    time: 36min
Java SE
Map

java容器中一般最常用的就是List、Set、Map，List的实现前面已经介绍过，本文主要讨论下Map的几个实现，至于Set则比较简单，它们仅仅是依赖Map做了层封装而已。

在讨论之前，还是先看下Map的继承结构


1. HashMap

HashMap的本质是一个散列表，简单地说就是通过散列函数，每个给定的key都可以计算出一个在表中的确定位置，并且散列函数会尽量将不同的key分散在不同的位置上，这样一旦知道了key，几乎就可以通过计算直接从表中获取到对应位置的元素。

但是散列函数并不能保证一定会将每个不同的key都散列到不同的位置，即便散列函数真能做到，那么当元素个数超过表的长度时，还是会发生冲突，即多个key计算出同一个位置。对于这个问题，HashMap使用链表或者红黑树将这些落在同一个位置的元素链接在一起（网上有很多关于HashMap中链表红黑树实现细节之类的面试题，个人感觉这些并不是HashMap的重点，它只在发生碰撞时尽量降低寻找次数的一个手段，本意应该仅仅是作为一个散列表，最好永远不要出现转化为红黑树的情况。

对于红黑树，可以参考相关笔记：数据结构. 红黑树

1.1. 属性

java.util.HashMap
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
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable 

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 散列表默认长度: 16

    static final int MAXIMUM_CAPACITY = 1 << 30; // 散列表最大长度: 2的30次幂（忽略符号位，共31位）

    static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认负载系数: 0.75

    static final int TREEIFY_THRESHOLD = 8; // 链表转化为红黑树的条件1：链表长度>=7

    static final int MIN_TREEIFY_CAPACITY = 64; // 链表转化为红黑树的条件2：散列表长度>=64

    static final int UNTREEIFY_THRESHOLD = 6; // 红黑树转化为链表的条件：树节点数<=6

    transient Node<K,V>[] table; // 散列表

    transient Set<Map.Entry<K,V>> entrySet; // 实现了Iterator接口的内部类实例，首次使用时才初始化

    transient int size; // 元素总数

    transient int modCount; // 修改次数，阻止并发修改

    int threshold; // table.length * loadFactor，扩容阈值，当size的值达到threshold时会触发resize()

    final float loadFactor; // 负载系数，即元素最大数与表长度的比值
	
    ...
	
}
1.1.1. table

HashMap中的散列表其实就是一个数组table（这里称为表），对于表中的元素，则是封装后的链表节点或者红黑树节点，根据情况相互转换，不过在TreeNode与Node之间还有一个LinkedHashMap.Entry，具体如下

java.util.HashMap.Node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
	
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
	
    ...
}
java.util.LinkedHashMap.Entry
1
2
3
4
5
6
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}
java.util.HashMap.TreeNode
1
2
3
4
5
6
7
8
9
10
11
12
13
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
	
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
	
    ...
}

上面Node为单向链表，Entry为双向链表，TreeNode为红黑树，三者相互独立，设计这样的继承关系主要是为了LinkedHashMap对HashMap的复用，LinkedHashMap就是在HashMap的基础上又维护了一个双向链表关系，这样不管HashMap中的节点如何变换，都不会破坏LinkedHashMap中的双向链表。

另外，这里TreeNode除了维护红黑树的必要属性外，还维护了一个prev，那么结合Node中的next,它本身也是一个双向链表，目的是为了在链表转换为红黑树之后迭代顺序不受影响，不过它维护的是散列表中具体某个位置下元素的前后关系，而Entry维护的是所有元素插入时的前后关系。

其实上面让LinkedHashMap.Entry继承TreeNode也同样能实现，这样做也许是因为作者考虑到毕竟TreeNode的小概率事件，让LinkedHashMap中所有的节点都拥有红黑树那些不必要的属性会显得浪费空间，而反过来只会让少数的TreeNode多两个双向链表的链接。当存放元素体积越小，这种差距将越明显，甚至封装节点的空间成本会超过存放元素所需的空间本身。

1.1.2. loadFactor

在碰撞概率与空间使用率之间存在一个矛盾，如果表的长度远大于元素个数，那么碰撞概率自然会很比较低，但是空间浪费了，反之要是缩短表的长度，那么可以节约空间，但是碰撞率又上升了。

对于这个问题，HashMap提供了一个系数loadFactor用于维持元素个数与表长度之间的比例，并规定实际存放的元素总数不能超过table.length * loadFactor，记为threshold，当元素总数达到threshold时就对table.length进行翻倍。默认会给一个比较折中的值：0.75，试图在空间使用率与碰撞率直接找到一个平衡，原注释如下

As a general rule, the default load factor (0.75) offers a good tradeoff between time and space costs. Higher values decrease the space
overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected
number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the
number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

1.2. 静态工具

1.2.1. tableSizeFor
java.util.HashMap
1
2
3
4
5
6
7
8
9
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;
}

tableSizeFor(int cap)确保对于任意给定的int，都会返回一个刚好大于这个int的2的幂。它通过5次无符号右移以及位或运算，将任意一个以二进制表示的数的最高位往右至多32位全部置为1，然后再加1，这样所有位都进1，刚好得到一个比给定数高1位的2的幂。

并且运算之前首先将给定数减1，以确保结果不会超过给定数。这样如果给定数刚好为2^x，那么减1之后最高位将为2^(x-1)，那么运算后进位的结果依然为2^x。而如果给定数为2^(x-1) + m, 1 <= m < 2^(x-1), 则结果自然也是2^x。

考虑到int有效值区间，设置了返回值的上下界：2^0 ~ 2^30，另外，如果通过画图，可以将上面的步骤描述得更直白一些

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

hash(Object key)在返回key的hash值之前，先将hash值的高低位进行异或，以便中和一下低位上的散列程度。虽然hash函数的散列特性很好，但由于它的散列区间（int取值范围）很大，无法保证hash值在低位上的散列程度，试想如果给定n个key，计算得出的hash值在高位不同而低位完全相同，那么对于散列函数来说，它的任务也算完成了。

这样做是考虑到表的长度通常都是远小于hash，而计算hash在表中的位置则是采用取余计算(table.length - 1) & hash，其实就是直接取的hash低位值，此时如果hash在低位都相同，那么它们将全部撞在一起。因此先将hash的高低位进行异或可以尽量避免这种情况，而且这样做也不会增加多少开销。

tableSizeFor(int cap)和hash(Object key)的用意其实都是为了最后给key计算在表中的位置进行服务，首先确保了table.length一定为2的幂，然后才有(table.length - 1) & hash等价于hash % table.length。

另外，对于null，固定返回0，因此最终只能存在一个null值key，它将与其它hash取余为0的key一起放在散列表的第0位。

1.3. 接口实现

讨论下主要的接口，比如put、remove、以及遍历

1.3.1. put

put思路很清晰：先根据hash计算key在table中的位置，如果对应位置为空，则直接插入一个链表节点；否则尝试从位置下面的节点中寻找一个与key重复的节点，并记为e，如果找到了就直接替换值，如果找不到则直接插入，并且如果是插入的链表节点，那么插入后再检查是否有必要转换为红黑树。最终在插入之后，检查size是否超过了threshold，是否需要扩容。

java.util.HashMap
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
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i; // 记散列表为tab，表的长度为n，key对应表中的位置上的节点为p
	
    if ((tab = table) == null || (n = tab.length) == 0) 
        n = (tab = resize()).length; // tab为空则先初始化

    if ((p = tab[i = (n - 1) & hash]) == null) 
        tab[i] = newNode(hash, key, value, null); // p为空则直接新建并插入一个Node<K,V>
    else {
        Node<K,V> e; K k; // 记节点的key为k，尝试寻找与key完全相同的k，并记对应的节点为e 
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // 如果第一个节点p的k就与key一样，则直接将p记为e
        else if (p instanceof TreeNode) 
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 1.3.1.1
        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); // 1.3.1.4 
                    break;
                }

                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break; // 如果找到了与key重复的节点，则记为e，并结束遍历
                p = e; // 继续向下遍历
            }
        }

        if (e != null) { // 如果存在于key重发的节点e，则直接替换，并返回旧值
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)  // 若onlyIfAbsent为true，则不替换，除非原来为null
                e.value = value;

            afterNodeAccess(e);  // 留给LinkedHashMap实现
            return oldValue;
        }
    }

    ++modCount; //否则必然发生了新增，修改次数加1
    if (++size > threshold)
        resize(); // 1.3.1.6 如果新增后元素总数超过了threshold，则对table长度进行翻倍

    afterNodeInsertion(evict); // 留给LinkedHashMap实现
    return null;
}
1.3.1.1. putTreeVal

putTreeVal与上面putVal中链表的处理思路类似：尝试找到一个重复key的节点，如果找到则返回重复节点，否则直接插入新节点

java.util.HashMap.TreeNode
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
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) {
    Class<?> kc = null; // 记k的Class类型为kc
    boolean searched = false;
    TreeNode<K,V> root = (parent != null) ? root() : this; // 记根节点为root，待插入节点的key为k，其hash值为h
    
    for (TreeNode<K,V> p = root;;) { 
        int dir, ph; K pk; // 记遍历节点的key的pk，其hash值为ph，其hash值与h的比较结果记为dir
        if ((ph = p.hash) > h)
            dir = -1;
        else if (ph < h)
            dir = 1;
        else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
            return p; // ph = h且k与pk相同，那么找到了重复节点p，直接返回
        else if ((kc == null && (kc = comparableClassFor(k)) == null) // ph = h但k与pk不相同
                || (dir = compareComparables(kc, k, pk)) == 0) { // 1.3.1.2 尝试通过comparable比较
            
            // 通过hash和comparable都无法比较出key的大小关系
            if (!searched) { // 那么尝试从p的左右节点冲寻找与k有重复key的节点，searched确保只寻找一次
                TreeNode<K,V> q, ch; 
                searched = true; 
                if (((ch = p.left) != null && (q = ch.find(h, k, kc)) != null) 
                    || ((ch = p.right) != null && (q = ch.find(h, k, kc)) != null))
                    return q;
            }
            dir = tieBreakOrder(k, pk); // 1.3.1.3 上面的尝试都失败，只好强行比较出一个大小
        }

        TreeNode<K,V> xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) { // 没找到重复节点则插入
            Node<K,V> xpn = xp.next;
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x; // 插入红黑树叶子节点
				
            xp.next = x;
            x.parent = x.prev = xp; 
            if (xpn != null) // 就近维护下节点间的双向链表关系 xp - x - xpn 
                ((TreeNode<K,V>)xpn).prev = x;

            // 调整平衡并将root作为链表的头节点，并放到tab对应的位置上
            moveRootToFront(tab, balanceInsertion(root, x)); 
            return null;
        }
    }
}
1.3.1.2. comparableClassFor

如果通过key.hash无法比较出大小，那么尝试从key自身比较出大小，方法则是检查它是否实现了Comparable接口

java.util.HashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static Class<?> comparableClassFor(Object x) {
    if (x instanceof Comparable) {
        Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        if ((c = x.getClass()) == String.class) // 如果是String直接返回，它实现了Comparable
            return c;

        // 如果c的接口列表中存在Comparable，并且其泛型参数为c自身
        if ((ts = c.getGenericInterfaces()) != null) {  
            for (int i = 0; i < ts.length; ++i) {
                if (((t = ts[i]) instanceof ParameterizedType) 
                        && ((p = (ParameterizedType)t).getRawType() == Comparable.class) 
                        && (as = p.getActualTypeArguments()) != null 
                        && as.length == 1 
                        && as[0] == c) // type arg is c
                    return c; 
            }
        }
    }
    return null; 
}

static int compareComparables(Class<?> kc, Object k, Object x) {
    return (x == null || x.getClass() != kc ? 0 : ((Comparable)k).compareTo(x));
}
1.3.1.3. tieBreakOrder

如果前面的尝试全部失败，即通过通过hash和comparable都无法比较出key的大小关系，并且树中也没有相同key的节点，那么再做进行最后的努力：首先比较类名，如果还不行，继续调用本地方法System.identityHashCode，这里就算相等也视为小于，总之强行比较出一个大小关系，这样做是因为红黑树中的节点必须要有大小关系。

java.util.HashMap
1
2
3
4
5
6
7
8
static int tieBreakOrder(Object a, Object b) {
	int d;
	if (a == null 
	 || b == null 
	 || (d = a.getClass().getName().compareTo(b.getClass().getName())) == 0)
		d = (System.identityHashCode(a) <= System.identityHashCode(b) ? -1 : 1);
	return d;
}
1.3.1.4. treeifyBin

新增过程中有一个链表转化为红黑树的情形：如果链表新增后长度>=7，并且table长度>=64，那么会将对应的链表转化为红黑树

java.util.HashMap
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
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 { 
            TreeNode<K,V> p = replacementTreeNode(e, null); // 先将所有Node转成TreeNode
            if (tl == null)
                hd = p; // 将链表头节点记为hd
            else {
                p.prev = tl; // 记住转换为红黑树之前节点再链表中的顺序，以便在转换后迭代顺序不受影响
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);

        if ((tab[index] = hd) != null)
            hd.treeify(tab); // 1.3.1.5 从hd开始插入红黑树
    }
}
	
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}
1.3.1.5. treeify

treeify就是将链表中的节点按顺序插入红黑树

java.util.HashMap.TreeNode
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
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null; 
        if (root == null) { //第一个节点为根节点
            x.parent = null;
            x.red = false;
            root = x;
        }else {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            for (TreeNode<K,V> p = root;;) { 
                int dir, ph; // 尝试比较出大小，并记为dir
                K pk = p.key;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((kc == null && (kc = comparableClassFor(k)) == null) 
                      ||(dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);

                TreeNode<K,V> xp = p; // 找到值为null的树叶位置进行插入，然后平衡
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    moveRootToFront(tab, root); // 将root作为链表的头节点，并放到tab对应的位置上
}
1.3.1.6. resize

在首次插入或者插入之后size超过threshold时，将会触发resize，即将散列表长度翻倍，并将oldTab中的节点放入newTab中，不过这里有个技巧，由于oldCap和newCap都为2的幂，并且newCap刚好比oldCap高一位，那么hash对它们取余时的区别就看hash在oldCap最高位是0还是1，如果是0，则取余结果不变，如果是1则取余结果相差一个oldCap，至于判断方法只在于hash & oldCap的结果。

java.util.HashMap
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
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold; // 记原散列表为oldTab，原散列表长度为oldCap，原扩容阈值为oldThr
    int newCap, newThr = 0; // 记新散列表长度为newCap，新扩容阈值为newThr
   
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) { 
            threshold = Integer.MAX_VALUE;
            return oldTab; // 如果oldCap已经超过2^30，只能将threshold放到int最大值，table无法再扩
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 如果oldCap>=16，且翻倍后<MAXIMUM_CAPACITY，那么将threshold也翻倍
    }
    else if (oldThr > 0) // 初始化时如果指定了长度，则将其值记在了oldThr中，主要是为与上面if情形区分开，将table的初始化时机延迟到实际put操作
        newCap = oldThr; // 如果table没有初始化，但oldThr有值，则将newCap置为oldThr
    else {              
        newCap = DEFAULT_INITIAL_CAPACITY; // 否则将newCap和newThr都设为默认值
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
	
    if (newThr == 0) { // 确保newThr赋值
        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) {      
        for (int j = 0; j < oldCap; ++j) { // 遍历oldTab，将节点放入newTab中
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null; // 尽快垃圾回收

                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e; // 如果位置上只有一个节点，则直接放入newTab中
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 1.3.1.7
                else { 
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null; // 刚好拆成两个链表放到newTab中
                    Node<K,V> next;
                    do {                               
                        next = e.next;
                        if ((e.hash & oldCap) == 0) { // 节点在newTab中位置不变
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else { // 节点在newTab中位置刚好相差一个oldCap                        
                            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.3.1.7. split

与上面resize中链表的处理类似，将oldTab中的红黑树拆为两部分，由于TreeNode本身也是双向链表，所以拆分过程可以与链表一样遍历，只是在拆分后纪录了链表的长度，如果长度<=6，就将节点退化成链表节点，否则重新将节点插入为一个新的红黑树。

java.util.HashMap.TreeNode
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
final void split(T1<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) { // //与loHead处理一样，只是在tab中的位置不一样
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}
1.3.2. remove

remove的思路相对简单：就是从map中寻找相同key的节点，如果找到就删除并返回，否则返回空。

java.util.HashMap
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
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; //尝试找到key相同的节点，并记为node
        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);
            }
        }
		
        //如果找到了key相同的节点，（并且不需要比较value或者value也相同），那么进行删除
        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); // 1.3.2.1
            else if (node == p)
                tab[index] = node.next; // 如果node刚好为链表头节点，那么删除头节点
            else
                p.next = node.next; // 删除链表节点
				
            ++modCount;
            --size;
            
            afterNodeRemoval(node); // 留给LinkedHashMap实现
            return node;
        }
    }
    return null; // 没有找到，返回null
}
1.3.2.1. removeTreeNode

删除红黑树节点思路也比较明确，即先将删除节点替换成对树叶节点的删除（这里是找的后继节点），然后再做平衡操作，由于篇幅较长，而且之前对于红黑树的操作已经做过非常详细的讨论：数据结构. 红黑树，这里就不再赘述

java.util.HashMap.TreeNode
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) {
    int n;
    if (tab == null || (n = tab.length) == 0)
        return; 
		
    int index = (n - 1) & hash; // index为当前要删除节点所在tab中的位置
    TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl; // 记tab[index]为root和first
    TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev; // 记当前节点的前后节点分别为pred和succ
            
    if (pred == null)
        tab[index] = first = succ; // 若当前节点为头节点，直接将succ记为tab[index]和first
    else
        pred.next = succ; // 否则pred跳过当前节点，向后指向succ
				
    if (succ != null)
        succ.prev = pred; // succ跳过当前节点，向前指向pred
				
    if (first == null)
        return; // 删除之后tab[index]为空，直接结束
            
    if (root.parent != null)
        root = root.root(); // 修正root
		
    if (root == null || (movable && (root.right == null || (rl = root.left) == null || rl.left == null))) {
        tab[index] = first.untreeify(map);  // 如果判断成立，那么节点数不超过6，直接退化成链表
        return;
    }

    // 记当前节点为p，左右子节点为pl和pr，然后找一个树叶节点replacement用来替换p，并删除
    TreeNode<K,V> p = this, pl = left, pr = right, replacement; 
    if (pl != null && pr != null) {
        // 1.找到p的后继节点，并记为s
        TreeNode<K,V> s = pr, sl;
        while ((sl = s.left) != null) 
            s = sl;
			
        // 2.交换p与后继节点s的颜色	
        boolean c = s.red; s.red = p.red; p.red = c; 
		
        // 3.交换p与后继节点s的位置，交换之前先记下p的父节点pp，以及s的右子节点sr	
        TreeNode<K,V> sr = s.right;
        TreeNode<K,V> pp = p.parent;
        if (s == pr) { // 如果s = pr，那么s一定为树叶，直接交换
            p.parent = s;
            s.right = p;
        }
        else { // 交换p与s位置
            TreeNode<K,V> sp = s.parent; 
            if ((p.parent = sp) != null) {
                if (s == sp.left)
                    sp.left = p;
                else
                    sp.right = p;
            }
            if ((s.right = pr) != null)
                pr.parent = s;
        }
                
        // 4.修正交换之后的节点关系		
        p.left = null; // 原后继节点s不存在left，换完之后直接置p.left为null
		
        if ((p.right = sr) != null) // 修正sr，原先后继节点s的right
            sr.parent = p; 
			
        if ((s.left = pl) != null) // 修正pl，原删除节点p的left
            pl.parent = s; 
			
        if ((s.parent = pp) == null) // 修正pp，原删除节点p的parent
            root = s;
        else if (p == pp.left)
            pp.left = s;
        else
            pp.right = s;
			
        if (sr != null) // 如果sr不为空，则sr是树叶，否则p（原先为s）自身为树叶
            replacement = sr;
        else
            replacement = p;
    }
    else if (pl != null)
        replacement = pl; // pr为空，则pl为树叶
    else if (pr != null)
        replacement = pr; // pl为空，则pr为树叶
    else
        replacement = p; // 都为空，则p自身为树叶
    
    if (replacement != p) { // 如果p自身不是要删除的树叶，再将p与replacement对换，并删除p
        TreeNode<K,V> pp = replacement.parent = p.parent;
        if (pp == null)
            root = replacement;
        else if (p == pp.left)
            pp.left = replacement;
        else
            pp.right = replacement;
        p.left = p.right = p.parent = null;
    }

    // 如果最后删除的树叶不是红色，则需要重新平衡
    TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);

    if (replacement == p) {  // p自身是树叶，直接删除，上面的平衡已经将p变成一个可忽略的节点了
        TreeNode<K,V> pp = p.parent;
        p.parent = null;
        if (pp != null) {
            if (p == pp.left)
                pp.left = null;
            else if (p == pp.right)
                pp.right = null;
        }
    }
		
    if (movable)
        moveRootToFront(tab, r); // 将root作为链表的头节点，并放到tab对应的位置上
}
1.3.3. entrySet

entrySet的类型EntrySet并没有任何属性状态，但是它作为内部类可以访问到HashMap的所有属性和方法。HashMap本身并没有直接实现迭代接口，不过它可以返回一个实现迭代接口的实例，这样达到与自己本身实现一样的效果，而且代码结构更加清晰，这种将外部接口实现为私有内部类的技巧在api中随处可见，也是内部类的经典使用方式。

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
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {

    public final int size()                 { return size; }
	
    public final void clear()               { HashMap.this.clear(); }
	
    public final Iterator<Map.Entry<K,V>> iterator() {
        return new EntryIterator();
    }
	
    public final boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>) o;
        Object key = e.getKey();
        Node<K,V> candidate = getNode(hash(key), key);
        return candidate != null && candidate.equals(e);
    }
	
    public final boolean remove(Object o) {
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Object value = e.getValue();
            return removeNode(hash(key), key, value, true, true) != null;
        }
        return false;
    }
	
    public final Spliterator<Map.Entry<K,V>> spliterator() {
        return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
    }
	
    public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (int i = 0; i < tab.length; ++i) { // 不管是Node还是TreeNode，都可以直接通过next访问下一个
                for (Node<K,V> e = tab[i]; e != null; e = e.next)
                    action.accept(e);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}

EntrySet实现了Iterator接口，返回一个迭代器，本身也是一个内部实现，迭代器中主要是这里维护了一个next的状态

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
final class EntryIterator extends HashIterator implements Iterator<Map.Entry<K,V>> {
    public final Map.Entry<K,V> next() { return nextNode(); }
}

abstract class HashIterator {
    Node<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot

    HashIterator() {
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // 迭代初始位置，index为tab中第一个不为空的位置，next则为first节点 
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        if (modCount != expectedModCount) // 迭代期间预料之外的发生变化，及时失败
            throw new ConcurrentModificationException();

        if (e == null) // （并发场景下）modCount在实际删除之后修改，可能modCount没变但实际已经删除
            throw new NoSuchElementException();
			
        // 若next后面还有节点，则返回next，并将next记为下一个节点，若没有，再取下一个不为空的位置的头节点
        if ((next = (current = e).next) == null && (t = table) != null) {
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }

    public final void remove() {
        Node<K,V> p = current;
        if (p == null) // 预料之外的情况
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null;
        K key = p.key;
        removeNode(hash(key), key, null, false, false);
		
        //通过迭代器删除会将expectedModCount重置，因此不会出现ConcurrentModificationException
        expectedModCount = modCount;
    }
}

2. LinkedHashMap

前面已经提过，LinkedHashMap只是在HashMap的基础上加一层双向链表关系，维护了节点插入的先后顺序，其基本直接复用了HashMap的实现，相当于HashMap提供一个模板方法，在流程中独立出一些步骤交给LinkedHashMap来实现自己的操作。

2.1. 属性

java.util.LinkedHashMap
1
2
3
4
5
6
7
8
9
10
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

    transient LinkedHashMap.Entry<K,V> head; //链表头节点

    transient LinkedHashMap.Entry<K,V> tail; //链表尾节点

    final boolean accessOrder; //true：基于访问顺序，false：基于插入顺序，默认false
	
    ...
}

2.3 实现

由于其实现基本都是复用，所以就不过多赘述，就简单总结下

  • 对于插入很简单，仅仅覆盖下节点的创建方法，并在其中进行自己的链表链接操作
java.util.LinkedHashMap
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
@Override
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

@Override
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
    TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
    linkNodeLast(p);
    return p;
}

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}
  • 删除同样简单，只要HashMap节点删除后，实现下afterNodeRemoval操作
java.util.LinkedHashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
@Override
void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}
  • 如果accessOrder为true，即按照访问顺序进行遍历，那么在每次访问之后，则将访问节点放到最后
java.util.LinkedHashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
@Override
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}
  • 对于迭代则更加简单，可以直接遍历自己维护的链表，即按照插入的先后顺序来返回节点

3. TreeMap

HashMap中只是用红黑树来作为散列表中发生冲突时降低节点遍历深度的一个手段，而TreeMap则完全是对红黑树的一个应用，它维护着节点key之间的大小关系。由于对红黑树已经有过非常详细的讨论：数据结构. 红黑树，并且还尝试实现了一个可以处理重复key的MultiTreeMap，有兴趣可以看下，这里不再赘述。

4. Set

其实Set的实现就是Map的实现，虽然它实现的接口是Collection，但它就全部接口的实现都委托给了对应的Map， 具体的在 HashSet、LinkedHashSet、TreeSet中都是同样的套路。