海风影像馆
zhixinglvren
2022-07-28
目录

HashMap详解

# 1 HashMap（jdk1.7）

重要方法

public V put(K key, V value)

put(K key, V value) 表示添加元素

public V get(Object key)

get(Object key) 表示取出元素

# 1.1 put(K key, V value)

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        //初始化HashMap的底层数据结构 
        //调整hashmap的容量，取大于等于最接近指定容量的2的冪数
        inflateTable(threshold);
    }
    if (key == null)
        //key为空时存储到指定位置
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    //hashmap中若key已经存在，更新
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    //添加元素到hashmap
    addEntry(hash, key, value, i);
    return null;
}
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
void addEntry(int hash, K key, V value, int bucketIndex) {
    //hashmap元素数量达到负载容量，并且要添加元素的地方已经存在元素，则开始扩容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        //按当前hashmap两倍的长度扩容
        resize(2 * table.length);
        //计算hash，key为空则hash=0
        hash = (null != key) ? hash(key) : 0;
        //找到新数组要添加元素的地方
        bucketIndex = indexFor(hash, table.length);
    }
    //创建一个新Entry节点，头插法插入到数组中
    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    //按双倍长度创建新的Entry数组
    Entry[] newTable = new Entry[newCapacity];
    //旧数组元素转换到新数组
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    //table指向新数组
    table = newTable;
    //计算新的负载容量
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 1.1.1 transfer 转移

提示

旧数组元素转换到新数组，该过程jdk1.7的实现在多线程的情况下会存在死循环。

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

单线程

hashmap_st 注意：图中 next 指向的是节点实例。

多线程

hashmap_mthread 注意：图中 next 指向的是节点实例。

# 1.2 get(Object key)

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}

private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    //key为null时，默认去数组下标为0的地方取，
    // 如果该下标有多个元素（链表），则返回key为null的value
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
    //计算key的hash
    int hash = (key == null) ? 0 : hash(key);
    //通过hash找到数组下标，若该下标上是一个链表，则通过key的对比找到最终正确的元素
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}
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

# 2 HashMap（jdk1.8）

# 2.1 put(K key, V value)

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;
    //数组对应下标的元素为空时，直接添加node到该下标
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        //p：hash对应的数组元素
        Node<K,V> e; K k;
        //如果hash对应的数组元素，key值赋值给k，比较key也相等时，将p赋值给变量e
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果p是树节点类型，在该树后面添加节点
        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);
                    //binCount >= 8 - 1，
                    //从0开始累加，则如果当前节点时第9个节点（算上数组上的节点），转成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //长度未达到，拼接链表
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //e不等于空，代表对应的key已经存在，更新value
        if (e != null) {
            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;
    //数组为空 或者 数组的长度小于64，数组初始化或扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    //hash对应的数组元素不为空，开始转换成红黑树
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        //先拼成链表
        TreeNode<K,V> hd = null, tl = null;
        do {
            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);
    }
}

TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, 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
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

# 2.1.1 resize 扩容

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) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //旧数组长度 * 2 小于 最大长度限制，并且旧数组长度 大于等于 16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            //新阈值 = 旧阈值 * 2
            newThr = oldThr << 1; // double threshold
    }
    //如果旧的阈值大于0，则新数组长度 = 旧数组阈值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    //否则
    //新数组长度 = 16
    //新数组阈值 = 负载因子0.75 * 新数组长度16 
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        //ft = 新数组长度 * 负载因子
        float ft = (float)newCap * loadFactor;
        //新数组阈值 = 新数组长度及ft没有超过最大长度限制，则取ft，否则取Integer.MAX_VALUE
        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] = 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 {
                    //低位链表：存放的元素：（新数组下标 等于 旧数组下标）
                    //loHead：头结点，loTail：尾节点
                    Node<K,V> loHead = null, loTail = null;
                    //高位链表：存放的元素：（新数组下标 等于 （旧数组下标 + 旧数组长度））
                    //loHead：头结点，loTail：尾节点
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        //元素的hash【逻辑与】旧数组长度，等于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;
}
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

hashmap_hl

同样道理，如果是红黑树，也通过高低位的方式拉出两条链。

如果链表长度小于等于阈值6，则退化成链表插入到扩容后的数组，否则构造成红黑树插入到扩容后数组。

低位链插入数组的下标跟旧数组下标一样，高位链插入的新数组下标 = 旧下标 + 旧数组容量

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    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) // (else is already treeified)
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}
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

# 2.2 get(Object key)

public V get(Object key) {
    Node<K,V> e;
    //找到对应节点，为空则返回null，否则返回节点的value
    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;
    //key对应的元素不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //hash与数组上该hash下标的数组元素相等，且key也相等，则返回数组上的该元素
        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;
}
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
上次更新: 2022/11/24, 17:59:25
阻塞队列LinkedBlockingQueue
ThreadPoolExecutor线程池

← ThreadPoolExecutor线程池→

最近更新
01
Linux常用指令
11-24
02
GitHub高级搜索技巧
11-24
03
散列表
11-09
更多文章>
Theme by Vdoing | Copyright © 2020-2023 知行旅人 | MIT License | 粤ICP备20036515号-1