TreeMap源码阅读笔记
2021-09-04 / highPhone啊

JDK源码版本: Oracle JDK1.8.0_271

常量

1
2
3
4
5
6
7
8
9
10
11
12
//默认的初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16   
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//由链表转化为红黑树的节点数量的阈值。
static final int TREEIFY_THRESHOLD = 8;
//哈希桶数组某一下标下的Node链表节点数量大于此值，由红黑树转化为链表。此值要比TREEIFY_THRESHOLD小
static final int UNTREEIFY_THRESHOLD = 6;
//当哈希桶数组容量大于等于此值，才会进行红黑树转化，否则对哈希桶数组进行resize()扩容操作
static final int MIN_TREEIFY_CAPACITY = 64;

成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 /* ---------------- Fields -------------- */
 //哈希桶数组，其长度必须是2的次方，在第一次使用时才会初始化，可以通过resize()方法扩容。
transient Node<K,V>[] table;

//用来缓存entrySet()方法的结果，当entrySet()被调用时优先从这个成员变量获取值，如果它为null，在去调用EntrySet内部类的构造函数，获取所有Entry的set集合，返回EntrySet实例的同时也将实例的引用赋给entrySet。以便下次entrySet()被调用时可以快速获取结果。
transient Set<Map.Entry<K,V>> entrySet;

 //Hashmap所包含键值对的总数
transient int size;

//HashMap实例的内部结构被修改的次数。用于快速失败
transient int modCount;

//下一次将进行扩容的容量。当某次插入操作之后，size大于threshold的时候，将进行扩容，threshold将变成下一次进行扩容的容量。
int threshold;
//加载因子。它的作用,用来计算threshold：threshold = loadFactor * table.size。该值默认为0.75。
final float loadFactor;

静态方法hash()和tableSizeFor()

  • hash()

    1
    2
    3
    4
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//高16位右移后与原值做异或计算
    }

    这个函数也叫扰动函数，在理解扰动函数前，我们要先知道在HashMap中，根据元素hashcode计算数组下标的方法是(n-1) & hash,若果没有扰动函数重新计算key的hash值，那么，对于初始容量16来说，n-1的值为15，基于(n-1) & hash 算出来的下标，只与hash值的最后4位有关，前28无论是何值，都不影响计算出来的下标，这样，发生hash碰撞的机率会比较高。扰动函数的作用就是让hash高16位与低16位的值做一个异或，让所有数值的特征结合到一起，尽量使hash值中每一位数值对下标的计算都有意义，降低hash碰撞

  • tableSizeFor()

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

    这个方法是为了保证hash数组的长度一定是2的n次方，且返回的值是大于输入参数且最小的2的整数次幂的数, 我们用输入值9来做一个计算，就能很清楚的看到计算规则了：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    cap                 0000 0000 0000 0000 0000 0000 0000 1001
    n = cap - 1         0000 0000 0000 0000 0000 0000 0000 1000
    n >>> 1             0000 0000 0000 0000 0000 0000 0000 0100
    -----------------------------------------------------------------
    n |= n >>>1         0000 0000 0000 0000 0000 0000 0000 1100
    n >>> 2             0000 0000 0000 0000 0000 0000 0000 0011
    -----------------------------------------------------------------
    n |= n >>>2         0000 0000 0000 0000 0000 0000 0000 1111

    .......

    n >>> 16            0000 0000 0000 0000 0000 0000 0000 0000
    -----------------------------------------------------------------
    n |= n >>>16        0000 0000 0000 0000 0000 0000 0000 1111

    上述计算中，有一步n = cap - 1操作，这一步是为了防止输入的cap刚好是2的整数次幂，如果不减1，计算结果最终会是预期值的2倍，同时，由于int只有32位，做到n |= n >>> 16这一步时，已经可以确保32位全是1，这时计算结果为MAXIMUM_CAPACITY

添加元素putVal()

此方法是往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
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //如果table数组为null或者table数组长度为0，说明是第一次进入，对table数组进行resize()初始化扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //如果通过(n - 1) & hash计算到的tab[index]中的节点为null，还没有hash碰撞，直接新建一个节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    //有hash碰撞产生
    else {
        Node<K,V> e; K k;
        //首先检查hash碰撞发生的那个数据下标所在元素，与此次添加进来的元素是否相等(hash相等且key相等)，如相等，替换此数组下标的节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果发生hash碰撞的数组下标所在元素是TreeNode，证明此下标下的数据已经转化成红黑树存储了，调用putTreeVal()添加元素
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //发生hash碰撞的数组下标所在元素仍然以链表存储
        else {
            //遍历链表添加元素
            for (int binCount = 0; ; ++binCount) {
                //在链表尾部添加新元素
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //添加元素后检查链表长度，如果>=7,转换成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //如果key已存在，直接break出for循环，在后面代码中会覆盖旧值
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //key已存在mapping中，覆盖旧值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;//结构变化次数，有更新或删除操作时记录
    //如果size大于扩容阈值，size+1，resize()扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

扩容机制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
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) {
        //如果扩容前的容量已经是最大容量，直接返会旧的数组，只能让新元素在旧数组上添加，如果有hash碰撞，也无法扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //新容量为旧容量的两倍，位运算左移1位
        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;
    //第一次初始化，threshold为0，使用默认容量和默认threshold
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //计算新的resize阈值newThreshold
    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) {
        //把旧的table数组中元素遍历复制到新的数组
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                //把已经取出的元素置null，方便gc回收
                oldTab[j] = null;
                //该元素既不是链表也不是红黑树，直接求出index放到新数组
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                //红黑树节点，调用TreeNode的split方法处理
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //该元素下有链表
                else { // preserve order
                    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;
}
本文链接：https://highphone.xyz/2a457b11.html