HashMap 源码分析

发表于 | 分类于 | 阅读次数:

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
class HashMap {
     /**
     * 下一次扩容阈值（容量 * 负载因子）
     */
    int threshold;

    /**
     * 负载因子
     */
    final float loadFactor;
    
    public HashMap() {
        // DEFAULT_LOAD_FACTOR = 0.75
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }
    
    public HashMap(int initialCapacity) {
        // DEFAULT_LOAD_FACTOR = 0.75
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    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);
    }
    
    /*
    * 大于输入参数且最近的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;
    }
}

tableSizeFor 详解：

先来分析有关n位操作部分：

先来假设n的二进制为01xxx…xxx。接着

对n右移1位：001xx…xxx，再位或：011xx…xxx

对n右移2为：00011…xxx，再位或：01111…xxx

此时前面已经有四个1了，再右移4位且位或可得8个1

同理，有8个1，右移8位肯定会让后八位也为1。

综上可得，该算法让最高位的1后面的位全变为1。

最后再让结果n+1，即得到了2的整数次幂的值了。

现在回来看看第一条语句：

1
int n = cap - 1;

　　让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。例如二进制1000，十进制数值为8。如果不对它减1而直接操作，将得到答案10000，即16。显然不是结果。减1后二进制为111，再进行操作则会得到原来的数值1000，即8。

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
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
class HashMap {
    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)
            // Node数组初始化
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            // p = 原数据 == 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)
                // key不同，处理树结构
                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 ，链长度超过8时转换为树结构
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    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 Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        // 1. 计算新容量 新阈值
        
        // 旧容量
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 旧阈值
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            // 旧容量 > 0：
            if (oldCap >= MAXIMUM_CAPACITY) {
                // 扩容前的数组大小如果已经达到最大(2^30)了：阈值为int的最大值(2^31-1)，这样以后就不会扩容了  
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 新容量翻倍后 < 最大容量 && 旧容量 >= 默认初始容量：新阈值翻倍
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) 
            // 旧容量 == 0 && 旧阈值 > 0：新容量 = 旧阈值
            newCap = oldThr;
        else {               
            // 旧容量 == 0 && 旧阈值 == 0：采用默认值
            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;
        
        // 2. 数据转移到新结构中
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    // 原数组j数据非空
                    oldTab[j] = null;
                    if (e.next == null)
                        // 原数组j无冲突值，重新计算下标，数组下标 = hash & ( 新容量 - 1 ) 
                        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;
                            // 新容量和就容量只在高位有1个区别，因此只通过高位即可判断索引是否变化
                            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;
    }
}

关于 modCount：

modCount用于记录HashMap的修改次数, 在HashMap的put(),get(),remove(),Interator()等方法中,都使用了该属性

由于HashMap不是线程安全的,所以在迭代的时候,会将modCount赋值到迭代器的expectedModCount属性中,然后进行迭代, 如果在迭代的过程中HashMap被其他线程修改了,modCount的数值就会发生变化, 这个时候expectedModCount和ModCount不相等, 迭代器就会抛出ConcurrentModificationException()异常

在java8之前，map 的扩容在多线程下会死循环（由于新链表和旧链表的顺序相反，多线程下会出现环）,1.8解决了这个问题，但依然是非线程安全的，要使用线程安全的 map 建议使用 ConcurrentHashMap

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
25
26
27
28
29
30
31
class HashMap {
    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 &&
                ((k = first.key) == key || (key != null && key.equals(k))))
                // 直接数据下标命中
                return first;
            if ((e = first.next) != null) {
                // 下标相同，且存在"冲突"Node
                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;
    }

}

LinkedHashMap

继承 HashMap

put

未覆盖，但是重写了 newNode、afterNodeAccess 和 afterNodeInsertion

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
class LinkHashMap {
    
    /**
     * 链头部（最老）
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * 链尾部（最年轻）
     */
    transient LinkedHashMap.Entry<K,V> tail;

    static class Entry<K,V> extends HashMap.Node<K,V> {
        // after：较年轻 befor：较老
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
    
    /**
    * 插入新Entry调用
    */
    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

    /**
    * Entry被访问时调用
    */
    void afterNodeAccess(Node<K,V> e) {
        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)
                // 访问的e是head节点
                head = a;
            else
                // 访问的e不是head节点
                b.after = a;
            if (a != null)
                // 访问的e不是tail节点
                a.before = b;
            else
                // 访问的e是tail节点
                last = b;
            if (last == null)
                // 当前链为空
                head = p;
            else {
                // 非空
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }
    
    /**
    * put中被调用
    */
    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;
    }
    
    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;
        }
    }
    
    // 暂未实现，可被重写
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }
}

本文标题:HashMap 源码分析

文章作者:Sun

发布时间:2020年07月10日 - 18:07

最后更新:2020年08月08日 - 17:08

原始链接:https://sunyi720.github.io/2020/07/10/Java/HashMap源码解析/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。