WLQ's Blog

文章 https://mp.weixin.qq.com/s/1yWSfdz0j-PprGkDgOomhQ 的学习笔记

为什么要ConcurrentHashMap?

即使JDK1.8的HashMap已经不会出现环形链表，但仍然线程不安全

.

例如，若多个线程同时执行put方法，可能会同时进入第627行的判断条件，发生更新覆盖的情况

【实质】可以进行二分查找的有序链表，JUC包下有ConcurrentSkipListMap

跳表在原有的有序链表上增加了多级索引，实现了快速查找、插入、删除

可以得出，查找时每层最多遍历3个结点，而总层数为$log2n$，则CRUD复杂度均为$O(logn)$

插入

本文总结了三种平衡树：B+树、红黑树、AVL树

B+树

• B树应用：磁盘上的文件

.

.

默认初始长度为16，每次扩容一倍

HashMap在并发插入元素的扩容时，会出现线程安全问题，可能会出现环形链表，让下一次读操作出现死循环

扩容源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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);
            //jdk1.7的头插法，这会导致resize的时候链表顺序颠倒
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

.

Step1: 生成基本框架

先照着程序🐏的视频做https://www.bilibili.com/video/BV1Yb411a7ty

【踩坑1】注意仓库创建时就要设为public，设置成private会失败

域名强制小写，所以Github名字中的大写字母会转为小写

最后得到一个域名为<Github名字>.github.io的博客，但是无法插入图片并且无法渲染数学公式