Java 集合高频面试题汇总

短命女 2023-10-01 16:17 28阅读 0赞

更多：[Java 集合面试题汇总][Java]

Java 中的集合类存放于 `java.util` 包中，主要有 3 种：set(集）、list(列表包含 Queue）和 map(映射)。

*  **Iterator**：迭代器，可以通过迭代器遍历集合中的数据，主要方法为`hasNext()` 和 `next()`；
 *  **Collection**：Collection 是集合 List、Set、Queue 的最基本的接口；
 *  **Map**：是映射表的基础接口。

![image-20220117142757454][]

### 1. 常用的集合类有哪些，有什么区别 ###

Java 中常用的集合有 List，Set，Map，区别如下：

<table> 
 <thead> 
  <tr> 
   <th align="center"></th> 
   <th align="center">是否有序</th> 
   <th align="center">是否可重复</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">List</td> 
   <td align="center">是</td> 
   <td align="center">是</td> 
  </tr> 
  <tr> 
   <td align="center">Set</td> 
   <td align="center">否</td> 
   <td align="center">否</td> 
  </tr> 
  <tr> 
   <td align="center">Map</td> 
   <td align="center">否</td> 
   <td align="center">是</td> 
  </tr> 
 </tbody> 
</table>

### 2. Array 和 ArrayList 的区别 ###

数组 Array 是一种最简单的数据结构，在使用时必须要给它**创建大小**，在日常开发中，往往我们是不知道给数组分配多大空间的，如果数组空间分配多了，内存浪费，分配少了，装不下。而 ArrayList 在使用时可以添加多个元素且不需要指定大小，因为 ArrayList 是**动态扩容**的。

### 3. ArrayList 的扩容机制 ###

ArrayList 的内部实现，其实是用一个**对象数组进行存放具体的值**，然后用一种扩容的机制，进行数组的动态增长。

其扩容机制可以理解为，如果元素的个数，大于其容量，则把其容量扩展为原来容量的 1.5 倍，在其源码中的方法为 `grow()`，如下：

/**
     * 扩容
     *
     * @param minCapacity
     */
    private void grow(int minCapacity) {
        
        //原来的容量
        int oldCapacity = elementData.length;
        //新的容量  通过位运算右移一位  如，默认为10 10>>1=5  右移过程：10的二进制为  1010   右移1位->0101 转十进制->5
        //可以理解为oldCapacity >> 1 == oldCapacity/2 再加上原来的长度就扩容1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果大于ArrayList 可以容许的最大容量，则设置为最大容量
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //copy
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

ArrayList 默认的初始容量为 10，默认扩容为原来的 1.5 倍，假如当有第 11 个元素新增，则会将数组容量扩为 `10*1.5=15`，扩容之后在对原数组进行复制之后在把最新的元素添加到 ArrayList 中去。

了解更多：[ArrayList源码分析及扩容机制][ArrayList]

### 4. ArrayList 和 Vector 的区别 ###

这两个类都实现了 List 接口，他们都是有序集合，且都基于数组：

*  **线程安全**：Vector 是线程安全的，而 ArrayList 不是；
 *  **性能**：Vector 使用了 Synchronized 来实现线程安全，因此 ArrayList 在性能方面要优于 Vector；
 *  **扩容**：ArrayList 和 Vector 都会根据实际需要动态的调整容量，ArrayList 为原来容量的 1.5 倍，Vector 为原来的 2倍。

**那么为什么我们现在很少用到 Vector ？**

目前大多数的程序都是运行在单线程的环境下，无需考虑线程安全问题，而 Vector 是需要一定开销来维护线程安全，即 Synchronized，并且从扩容的角度来看，Vector 是扩容为原来的 2 倍，所以从节省内存空间角度来看，使用 ArrayList 更好。

### 5. 说说 CopyOnWriteArrayList ###

我们知道 ArrayList 是非线程安全的，而 Vector 虽说是线程安全的，但使用粗暴的锁同步机制 Synchronized，性能较差，因为**读写操作都会加锁**。（实际上在 1.8 之后对 Synchronized 做了优化）

在大多数情况下，我们的系统都是**读多写少**的情况，而 CopyOnWriteArrayList 容器允许并发读（读不加锁），性能较高。

而对于写操作，则是通过加锁的方式来保证其线程安全，其`add()`如下：

public boolean add(E e) {
        
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
        
            Object[] elements = getArray();
            int len = elements.length;
            //对原数组进行复制
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            //指向新数组
            setArray(newElements);
            return true;
        } finally {
        
            lock.unlock();
        }
    }

其工作原理是：

当新增一个元素时，会先将原数组进行**复制**形成新的副本，然后在副本上执行写操作，写操作执行完成之后再讲原容器的引用指向这个副本。

如果在新增过程中存在并发读，则依旧读的是原来容器中的数据。

![image-20220118104920869][]

**优点：**

读操作性能很高，因为无需任何同步措施，比较适用于**读多写少**的并发场景。List 在遍历时，若中途有别的线程对List 容器进行修改，则会抛出**ConcurrentModificationException**异常。而 CopyOnWriteArrayList 由于其 “读写分离” 的思想，遍历和修改操作分别作用在不同的 List 容器，所以在使用迭代器进行遍历时候，也就不会抛出ConcurrentModificationException异常了

**缺点：**

**一是内存占用问题**，毕竟每次执行写操作都要将原容器拷贝一份，数据量大时，对内存压力较大，可能会引起频繁GC；

**二是无法保证实时性**，Vector 对于读写操作均加锁同步，可以保证读和写的强一致性。而 CopyOnWriteArrayList 由于其实现策略的原因，写和读分别作用在新老不同容器上，在写操作执行过程中，读不会阻塞但读取到的却是旧容器的数据。也就是说 CopyOnWriteArrayList **只能保证数据的最终一致性，不能保证数据的实时一致性**。

### 6. HashSet 是如何判断重复的 ###

Set 集合有**自动去重**的特性，对基本数据类型如 String，Integer 等，其子类如 HashSet 是利用 `Comparable` 接口来实现重复元素的判断。

而对于自定义的类，HashSet 判断元素重复是利用 Object 类中的 `hashCode()`和`equals()`来判断的。

在进行重复元素判断的时候首先利用`hashCode()`进行编码匹配，如果该编码不存在表示数据不存在，证明没有重复，如果该编码存在了，则进一步进行对象的比较处理，如果发现重复了，则此数据是不能保存的。

实际上 HashSet 的`add()`方法底层调用了 HashMap 的`put()`方法来处理的，即底层结构实际上是 HashMap。

所以 HashSet 的不重复是 HashMap 保证了不重复，HashMap 的 put() 方法新增一个原来不存在的值会返回 null，如果原来存在的话会返回原来存在的值。（[HashMap 深入浅出][HashMap]）

### 7. 简单说一下 TreeSet ###

TreeSet 是使用二叉树的原理对新 `add()`的对象按照指定的顺序排序（升序、降序），每增加一个对象都会进行排序，将对象插入的二叉树指定的位置。

Integer 和 String 对象都可以进行默认的 TreeSet 排序，而自定义类的对象是不可以的，自己定义的类**必须实现 Comparable 接口**，并且覆写相应的 compareTo() 函数，才可以正常使用。

在覆写 `compare()`函数时，要返回相应的值才能使 TreeSet 按照一定的规则来排序。

比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。

了解更多：[二叉树][Link 1]、[二叉查找树][Link 2]

### 8. ArrayList 与 LinkedList 区别 ###

<table> 
 <thead> 
  <tr> 
   <th align="center"></th> 
   <th align="center">ArrayList</th> 
   <th align="center">LinkedList</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">数据结构</td> 
   <td align="center">数组</td> 
   <td align="center">链表</td> 
  </tr> 
  <tr> 
   <td align="center">访问效率</td> 
   <td align="center">高，通过索引直接映射</td> 
   <td align="center">慢，循环遍历</td> 
  </tr> 
  <tr> 
   <td align="center">插入删除效率</td> 
   <td align="center">慢，需要移动数组，扩容需要复制</td> 
   <td align="center">快，只需改变指针的指向</td> 
  </tr> 
  <tr> 
   <td align="center">开销</td> 
   <td align="center">小</td> 
   <td align="center">大，除了存储数据，还要存储引用</td> 
  </tr> 
 </tbody> 
</table>

总结如下：

1.  数据结构不同，ArrayList 底层是基于数组实现的，LinkedList 底层是基于链表实现的。
2.  由于底层数据结构不同，他们所适⽤的场景也不同，ArrayList 更适合随机查找，LinkedList 更适合删除和添加，查询、添加、删除的时间复杂度不同。
3.  另外 ArrayList 和 LinkedList 都实现了 List 接⼝，但是 LinkedList 还额外实现了 Deque 接⼝，所以 LinkedList 还可以当做队列来使⽤。

**注**：对于 ArrayList 的插入效率来说，在大多数情况下都是通过**尾插法**的方式来新增元素，所以此时效率并不会低于 LinkedList。

了解更多：[手写链表之LinkedList源码分析][LinkedList]

### 9. Java 中的 Stack 有什么问题 ###

**栈是一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构**，同[顺序表][Link 3]和[链表][Link 4]一样，也是用来存储逻辑关系为 “一对一” 数据。栈的应用有很多，比如浏览器的跳转和回退机制等。

![image-20220117172538968][]

从上图可以看出：

1.  栈只能从一端存取数据，而另外一端是封闭的；
2.  无论是存还是取，都需要遵循**先进后出**的原则。如需要取元素1，需要提前将元素4,3,2取出。

而反观 Java 中的 Stack ，它继承自 Vector 类，而 Vector 是由数组实现的集合类，他包含了大量集合处理的方法。而 Stack 之所以继承 Vector，是为了**复用** Vector 中的方法，来实现进栈（push）、出栈（pop）等操作。

这里就是质疑 Stack 的地方，既然只是为了实现栈，为什么不用链表来单独实现，只是为了复用简单的方法而迫使它继承 Vector（Stack 和 Vector本来是毫无关系的）。这使得 Stack 在基于数组实现上效率受影响，另外因为继承Vector 类，Stack 可以复用 Vector 大量方法，这使得 Stack 在设计上不严谨，当我们看到 Vector 中的：

public void add(int index, E element) {
        
        insertElementAt(element, index);
    }

**可以在指定位置添加元素**，这与 Stack 的设计理念相冲突（栈只能在栈顶添加或删除元素）。

另外，对于栈的应用来说，通常有一个面试题就是**如何反转字符串**？

*  使用栈的先进后出；
 *  递归。
    
        public static String reverse(String str) {
              
            if (str == null || str.length() <= 1) {
              
                return str;
            }
            return reverse(str.substring(1)) + str.charAt(0);
        }

了解更多：[栈和队列][Link 5]

### 10. Queue 中 poll() 方法和 remove()方法的区别 ###

在 Queue 队列中，poll() 和 remove() 都是从队列中取出一个元素，在**队列元素为空**的情况下，remove() 方法会抛出异常，poll() 方法只会返回 null 。

### 11. BlockingQueue 中 poll() 方法和 take()方法的区别 ###

**poll(long timeout,TimeUnit unit)**

从 BlockingQueue 取出一个队首的对象，如果在指定时间内，队列一旦有数据可取，则立即返回队列中的数据。否则直到时间超时还没有数据可取，返回失败。

**take()**

取走 BlockingQueue 里排在首位的对象，若 BlockingQueue 为空，阻断进入等待状态直到 BlockingQueue 有新的数据被加入。

这两个方法在线程池的获取任务中所用到，即`getTask()`方法，该方法是将任务队列中的任务调度给空闲线程。

### 12. 说说对 HashMap 的理解 ###

在 jdk1.8 之前的版本中，HashMap 存储结构是数组＋链表。计算保存对象的hash值除数组长度求余，根据余数将该对象保存到哪个链表。这种方式就要有很好的 hash 函数，尽量将数据平均保存到不同链表上。但是再好的 hash 函数的选择也很难将数据均匀分布，而且当 HashMap 中有大量元素都保存在同一个链表上时，此时的查询效率将是 O(n)，当然这是最极端的情况。

jdk1.8 之前版本的HashMap中，当调用 put 方法添加元素时，如果新元素的 hash 值或保存的 key 在原 HashMap 中不存在，则会检查要保存到的链表的 size 是否大于负载因子 threshold，如果达到扩容要求，则将原数组进行扩容，扩容后的数组容量是原数组的二倍，并将原Map中的元素重新计算 hash 值然后保存到新的数组中，如下图所示，假设一个HashMap的数组长度是4，负载因子是 0.75，有新的元素要保存到下标为 2 的数组上，这时就会触发 HashMap 的扩容。

![image-20220118135835673][]

在 jdk1.8 及之后的版本中，当链表的长度等于 8 时，HashMap 就会将链表的结构转换为红黑树，也就是 HashMap 的存储结构变为了数组＋链表＋红黑树。删除元素和扩容时，如果树中的元素个数较少时会对树进行修剪调整或还原为链表结构，以提高后续操作性能。

了解更多：[HashMap 深入浅出][HashMap]

### 13. HashMap 中String、Integer为什么适合作为 key ###

String、Integer 等包装类的特性能够保证 Hash 值的不可更改性和计算准确性，能够有效的减少Hash碰撞的几率，原因如下：

*  都是 final 修饰的类，不可变性，保证 key 的不可更改性，不会存在获取 hash 值不同的情况；
 *  内部已重写了 equals()、hashCode() 等方法，遵守了 HashMap 内部的规范。

### 14. HashMap put函数执行流程 ###

![3ff5a426e42abb3c372d31c97ab2b42d][]

### 15. HashMap 的扩容机制 ###

HashMap 的默认数组容量大小为 16，也就是说它是有限的，那么随着数据的增加，达到一定量之后就会自动扩容，即resize()。

那么触发resize()的具体条件是什么呢？主要包括两个方面：

*  **capacity**：HashMap 当前长度，默认为 16。
 *  **load factor**：加载因子，默认值 0.75f。

其中负载因子的大小决定着哈希表的扩容和哈希冲突，一旦达到阈值就会扩容，阈值在HashMap中定义如下：

/**
     * The next size value at which to resize (capacity * load factor).
     *
     * @serial
     */
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
    int threshold;

那么什么时候扩容呢？就是`capacity * load factor`，即`16*0.75=12`，也就是说数组最多只能放 12 个元素，一旦超过 12 个，哈希表就需要扩容。

而在扩容的过程中包含了 2 步：

*  **扩容**，创建一个新的 Entry 空数组，长度是原数组的 2 倍（2次幂），即 16 扩容后为 32；
 *  **Rehash**，遍历原 Node 数组，从新计算索引的值并添加到新数组。

那么为什么需要Rehash呢？

因为在 HashMap 中 hash 值是通过 `(n-1)&hash`来计算的，其中 n 为数组的长度，数组长度发生变化，如果不重新计算，很可能后续添加元素的时候会生冲突。

扩容过程：

**1.7 版本**

1.  先⽣成新数组；
2.  遍历⽼数组中的每个位置上的链表上的每个元素；
3.  取每个元素的 key，并基于新数组⻓度，计算出每个元素在新数组中的下标；
4.  将元素添加到新数组中去；
5.  所有元素转移完了之后，将新数组赋值给 HashMap 对象的 table 属性。

**1.8 版本**

1.  先⽣成新数组；
2.  遍历⽼数组中的每个位置上的链表或红⿊树；
3.  如果是链表，则直接将链表中的每个元素重新计算下标，并添加到新数组中去；
4.  如果是红⿊树，则先遍历红⿊树，先计算出红⿊树中每个元素对应在新数组中的下标位置；
    
    1.  统计每个下标位置的元素个数；
    2.  如果该位置下的元素个数超过了8，则⽣成⼀个新的红⿊树，并将根节点的添加到新数组的对应位置；
    3.  如果该位置下的元素个数没有超过8，那么则⽣成⼀个链表，并将链表的头节点添加到新数组的对应位置；
5.  所有元素转移完了之后，将新数组赋值给 HashMap 对象的 table 属性。

### 16. HashMap 的长度为什么是 2 的 n 次方 ###

当我们`new HashMap()`在未指定大小的时候，其默认为 16，如下：

/**
     * The default initial capacity - MUST be a power of two.
     *
     * 默认数组的初始容量，且必须为2的次幂
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
    // 存放所有Node节点的数组
    transient Node<K,V>[] table;

**那么为什么说 table 数组的长度必须是 2 的 n 次方呢？**

`put()`方法源码如下：

public V put(K key, V value) {
        
        return putVal(hash(key), key, value, false, true);
    }

可以看到在存入数据时会先计算 key 的 hash 值，即`hash(key)`：

static final int hash(Object key) {
        
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

然后通过`(n-1) & hash` 的取值来判断将该数据放入 table 的哪个**下标**，如下：

![image-20220104145843344][]

注：n 为 table 数组的长度。

其中 `&` 为二进制中的`位与`运算，两个位都为 1 时，结果才为 1 `(1&1=1，0&0=0，1&0=0)`，如下：

4 & 6 = 4

首先把两个十进制的数转换成二进制

4  0 1 0 0
    6  0 1 1 0
    ----------
    4  0 1 0 0

因为 HashMap 的 table 数组的长度是 2 的次幂 ，那么对于这个数再减去 1（即 n-1），转换成二进制的话，就肯定是最高位为 0，其他位全是1 的数。为什么？

因为一个数（大于0）为 2 的次幂，那么根据奇偶判断这个数必定为偶数，那么减 1 之后就为奇数，那么一个数转为二进制数的末位就为 1。

以 HashMap 默认初始数组长度 16 为例，`16-1`的二进制为`1111`，然后随意指定几个 hash 值与其计算，并与其进行位与运算：

十进制
    hash1	1 0 1 1 0 1 1 1
    15      0 0 0 0 1 1 1 1
    -----------------------
    7       0 0 0 0 0 1 1 1
    
    hash2	1 0 1 1 0 1 0 1
    15      0 0 0 0 1 1 1 1
    -----------------------
    5       0 0 0 0 0 1 0 1
    
    hash3	1 0 1 1 0 1 0 0
    15      0 0 0 0 1 1 1 1
    -----------------------
    4       0 0 0 0 0 1 0 0

若不为 2 次幂，假如为 15，则减 1 后 14 的二进制为 `1110`，再次进行运算：

十进制
    hash1	1 0 1 1 0 1 1 1
    14      0 0 0 0 1 1 1 0
    -----------------------
    6       0 0 0 0 0 1 1 0
    
    hash2	1 0 1 1 0 1 0 1
    14      0 0 0 0 1 1 1 0
    -----------------------
    4       0 0 0 0 0 1 0 0
    
    hash3	1 0 1 1 0 1 0 0
    14      0 0 0 0 1 1 1 0
    -----------------------
    4       0 0 0 0 0 1 0 0

很明显，在不为 2 次幂的时候，最后两个通过位运算，求出的值都为 4，也就是说数据都分布在 table 数组下标为 4 的节点上（数据桶），带来的问题就是由于出现 Hash 碰撞导致 HashMap 上的数组元素分布不均匀，而数组上的某些位置，永远也用不到，进而影响其性能。

此时，就有人说了，我不是可以指定 HashMap 的大小吗？我就不给他 2 次幂的数，会怎样呢？比如`new HashMap(7)`。假设你传一个 7 进去，实际上最终 HashMap 的大小是 8，其具体的实现其构造器的 `tableSizeFor()`。

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

`tableSizeFor()`源码如下：

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

**其中还是通过位运算去解析的，即如果你传一个 7 进去，实际上最终 HashMap 的大小是 8，传一个 10，那么 HashMap 的大小是 16，传 20，HashMap 的大小是 32。**

对于`(n-1) & hash`，还存在另外一种说法，**(n - 1) & hash等于 hash % n**，举个例子：

当 n = 16 时，二进制形式为 00010000，（n-1）的二进制形式为 00001111 ，假设 hash = 33，其二进制形式为 00100001，则：

0 0 0 0 1 1 1 1
    0 0 1 0 0 0 0 1
    ---------------
    0 0 0 0 0 0 0 1

其结果为 1，即`(16-1) & 33 = 1`，而 `33 % 16 = 1`，两者相等，但前提是**当 n 为 2 的任意次幂时，（n-1）& hash 等价于 hash % n**。从而也保证了当添加一个数时的下标 index 在数组范围内。

### 17. HashMap 加载因子为什么是 0.75 ###

我们知道，若没有指定 HashMap 的容量，其大小默认为 16，当容器达到阈值时会进行扩容，而影响扩容的两个因素就是加载因子和容量，在不考虑容量的情况下，那么影响其扩容的就是加载因子，而扩容需要遍历原数组并需要重新计算 Hash，那如果把**加载因子**调大是不是就可以减少扩容次数呢？

**1、加载因子是1.0**

比如设置为 1，那么就是等元素到 16 之后才扩容。

![image-20220105195041298][]

一开始数据保存在数组中，当发生 Hash 碰撞后，就在这个数据节点上，生出一个链表，当链表长度达到一定长度的时候，就会把链表转化为红黑树。

**当加载因子是 1.0 的时候，也就意味着，只有当数组的 8 个值（这个图表示了 8 个）全部填充了才会发生扩容。这就带来了很大的问题，因为 Hash 冲突时避免不了的。当负载因子是 1.0 的时候，意味着会出现大量的 Hash 的冲突，底层的红黑树变得异常复杂。对于查询效率极其不利。这种情况就是牺牲了时间来保证空间的利用率。**

**2、加载因子是 0.5**

加载因子是 0.5 的时候，这也就意味着，当数组中的元素达到了一半就开始扩容，既然填充的元素少了，**Hash冲突也会减少**，那么底层的链表长度或者是红黑树的高度就会降低。查询效率就会增加。但是触发扩容，会浪费一定的内存空间，这时空间利用率就会大大的降低，原本存储 1M 的数据，现在就意味着需要 2M 的空间。

总结起来就是：

1.  加载因子调高了，意味着 Hash 碰撞概率增加，查找速度变慢；
2.  加载因子调低了，Hash 碰撞概率降低，查找速度变高，但空间利用率降低。

而为什么是 0.75？在源码中也有体现，如下：

![image-20220105202014726][]

其大致意思就是说负载因子是 0.75 的时候，权衡之后空间利用率相对较高，并且降低了Hash碰撞的概率。

### 18. HashMap 的死循环 ###

这个问题实际上是针对 jdk7 的，因为 jdk7 的链表是头插法，在并发情况下可能会造成死循环，而 jdk8 采用的是尾插法，不会产生死循环。

那么什么是头插法和尾插法呢？可以看看下面这张图：

![image-20220106152324204][]

在 jdk7的 put 方法中，主要流程如下：

put()  --> addEntry()  --> resize() -->  transfer()

主要问题就出现在`transfer()`，也就是扩容过程中出现了问题，该方法的作用是**将原来的所有数据全部重新插入（rehash）到新的数组中**，如下：

void transfer(Entry[] newTable, boolean rehash) {
        
        // 获取新table的长度
        int newCapacity = newTable.length;
        // 遍历老table中的元素
        for (Entry<K,V> e : table) {
        
            // 遍历每一个链表的元素
            while(null != e) {
        
                // 获取当前元素的 next
                Entry<K,V> next = e.next; 
                // 判断是否需要重新hash
                if (rehash) {
        
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                // 获取元素对应的新table位置
                int i = indexFor(e.hash, newCapacity);
                // 进行转移，头插法
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

实际上，非并发情况下是不会出现死循环的，这里演示在并发的情况下。

假设 HashMap 初始容量为 4，则 `4*0.75=3`，若在之前已经插入了 3 个元素 A，B，C（为了方便直接用以表示节点的key-value），并且它们都 hash 到一个位置上，则形成如下的链表结构：

![image-20220107161745890][]

此时插入第 4 个元素时，HashMap 需要扩容（为原来的 2 倍），若此时有**两个线程同时**插入，则两个线程都会建立新的数组，如下：

![image-20220107163640649][]

当线程 1 执行到`transfer()`中的`Entry<K,V> next = e.next` ，且 CPU 时间片刚好到了，那么此时对于线程 1 来说：

e = A;
    e.next = B;

然后线程 2 开始正常执行，在 rehash 之后，A、B、C 又在同一位置，则按照头插法的方式循环完成之后的结构如下所示：

![image-20220107175932194][]

在执行完上面的步骤之后，此时线程 2 的 CPU 时间片到了，又轮到线程 1，对于线程 1 来说`e = A;`  
`e.next = B`，那么此时的引用关系因为：

![image-20220107180130441][]

而我们知道在 JVM 中我们的对象都存在于堆中，因为对于线程 1 来说，`e = A;e.next = B`即`A.next =B`，而对于线程 2 来说则是`B.next=A`，所以此时 2 个数组对于 A、B、C 的引用关系如下：

![image-20220108131439917][]

可以看到 A，B之间相互引用，若此时存在另外的线程来调用 `get()` 方法，如下：

final Entry<K,V> getEntry(Object key) {
        
        //如果hashmap的大小为0返回null    
        if (size == 0) {
        
            return null;
        }
        // 判断key如果为null则返回0,否则将key进行hash    
        int hash = (key == null) ? 0 : hash(key);
        //indexFor方法通过hash值和table的长度获取对应的下标    
        // 遍历该下标下的(如果有)链表    
        for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        
            Object k;
            //判断当前entry的key的hash如果和和参入的key相同返回当前entry节点        
            if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) 
                return e;
        }
        return null;
    }

可以看到在 for 循环查找元素时，只要 `e.next != null`，则会一直循环查找，所以在并发的情况，发生扩容时，可能会产生循环链表，在执行 get 的时候，会触发死循环。

那么问题来了，既然有死循环产生的可能为**什么还要使用头插法**呢？

这可能得问实现者了，有种说法，我觉得挺有道理：**缓存的时间局部性原**则，最近访问过的数据下次大概率会再次访问，把刚访问过的元素放在链表最前面可以直接被查询到，减少查找次数。

这实际上并不能算是一个问题，因为 HashMap 本就不是线程安全的，所以你如果用它来处理并发，本就是不符合逻辑的，所以在并发情况下可以使用线程安全的如 ConcurrentHashMap。

### 19. HashMap 什么时候用到红黑树 ###

红黑树是一棵二叉查找树，其具备以下性质：

1.  节点是红色或黑色（非黑即红）
2.  根节点是黑色
3.  所有的null节点称为叶子节点，且都是黑色
4.  所有红色节点的子节点都是黑色（即没有连续的红色节点）
5.  任意一个节点到其叶子节点的所有路劲都包含相同数目的黑色节点

![image-20220108133603691][]

如果想了解更多关于红黑树的可以参看我的这篇文章：[图解红黑树][Link 6]

而在 HashMap 中运用红黑树的主要目的是为了查询效率，我们知道，在 jdk7 是通过链表来解决了 Hash 冲突，但是如果某一条链表上存在很多数据，当我们需要查找的时候，则需要一直遍历，知道找到对应的值，时间复杂度为O(n)。而 jdk8 就引入了红黑树，红黑树是一棵二叉查找树，其查询是插入时间复杂度为 O(logn)，效率高于链表。

那么就有人说了，既然有红黑树，为什么还需要链表？

因为红黑树的查询很快，但是增加删除操作却比较复杂，需要进行相应的**左旋、右旋、变色**操作，相比链表是比较耗时的，所以在 jdk8 中也不是一上来就使用红黑树，遵循以下规则：

1.  数组容量大小大于 64 **且**链表大小大于 8，链表转为红黑树；
2.  当红黑树的大小小于 6，红黑树退化为链表。

### 20. HashMap 链表大于 8 一定会转为红黑树吗 ###

不是的，数组容量大小大于 64 **且**链表大小大于 8，链表才会转为红黑树。

如果说仅仅是链表长度大于 8，而数组容量小于 64，此时还是会扩容但不会转为红黑树。

因为此时数组容量较小，应该尽量避开使用红黑树，因为红黑树需要进行**左旋，右旋，变色**操作来保持平衡，所以当数组长度小于 64，使用数组加链表比使用红黑树查询速度要更快、效率要更高。

注：对于红黑树的大小小于 6，红黑树退化为链表，实际上只有 resize 的时候才会进行转换，同样也不是到 8 的时候就变成红黑树。

**为什么是链表长度大于 8 的时候转为红黑树？能不能是其他数值？**

通常情况下，**链表长度很难达到 8**，在源码中有这样一段注释：

Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution 
    with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although 
    with a large variance because of resizing granularity. Ignoring variance, the expected 
    occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). 
    The first values are:
          0:    0.60653066
          1:    0.30326533
          2:    0.07581633
          3:    0.01263606
          4:    0.00157952
          5:    0.00015795
          6:    0.00001316
          7:    0.00000094
          8:    0.00000006
          more: less than 1 in ten million

在理想情况且在随机哈希码下，哈希表中节点的频率遵循[泊松分布][Link 7]，而根据统计，忽略方差，列表长度为 K 的期望出现的次数是以上的结果，可以看到其实在为 8 的时候概率就已经很小了，可以看到**当长度为 8 的时候，概率仅为 0.00000006**。这是一个小于千万分之一的概率，一般来说我们的 Map 里面是不会存储这么多的数据的，所以通常情况下，并不会发生从链表向红黑树的转换，因此再往后调整并没有很大意义。

如果真的碰撞发生了8次，那么这个时候说明由于元素本身和 hash 函数的原因，此时的链表性能已经已经很差了，操作的 hash 碰撞的可能性非常大了，后序可能还会继续发生 hash 碰撞，因此特殊情况下链表长度为 8，哈希表容量又很大，造成链表性能很差的时候，只能采用红黑树提高性能，这是一种应对策略。

**为什么链表的长度为 8 是变成红黑树？为什么红黑树大小为 6 时又变成链表？**

首先我们先了解一下什么是平均查询长度，ASL(Average Search Length)。

另外，从结果上来看[平均查找长度去掉系数之后就是时间复杂度][Link 8]。

链表属于顺序查找，红黑树可以看作二叉树，属于二分查找。

对于顺序查找来说，假设存在 n 个数，每个数字查找概率相等，那么有：

(1+2+3+4+...+n)/n = (n+1)/2

对于二分查找来说，其平均查询长度为：log2n。

这里就不推导了，感兴趣的看看这篇文章（https://www.jianshu.com/p/6d7b9c7fef3a）

因此，当链表长度为 **6** 时：

*  链表查询的平均长度为：**(n+1)/2 = (6+1)/2 = 3.5**
 *  红黑树查询的平均长度为：**log2n = log26 = 2.6**

因此，当链表长度为 **7** 时：

*  链表查询的平均长度为：**(n+1)/2 = (7+1)/2 = 4**
 *  红黑树查询的平均长度为：**log2n = log27 = 2.8**

当链表长度为 **8** 时：

*  链表查询的平均长度为：**(n+1)/2 = (8+1)/2 = 4.5**
 *  红黑树查询的平均长度为：**log2n = log28 = 3**

为什么链表的长度为 8 是变成红黑树？

我们对比一下，长度为 8 时红黑树的查询长度要低，而本来出现长度为 8 的概率就很低，若这么小的概率都出现了，那说明很有必要进行树化。那么为什么不选择 6 呢？虽然 6 的速度也很快，但是概率比 8 的概率高，因此树化的可能性就越大，**转化和生成树本身就耗费时间**。

为什么红黑树大小为 6 时又变成链表？

主要是因为，如果也将该阈值设置于 8，那么当 hash 碰撞在 8 时，会反生链表和红黑树的不停相互转换，白白浪费资源。中间有个差值 7 可以防止链表和树之间的频繁转换，假设一下：

如果设计成链表个数超过 8 则链表转换成树结构，链表个数小于 8 则树结构转换成链表，如果 HashMap 不停的插入，删除元素，链表个数在 8 左右徘徊，就会频繁的发生红黑树转链表，链表转红黑树，效率会很低下。

如果设计成链表个数超过 7 则链表转换成树结构，跳出技术角度来说，千万分之一的概率都能碰到，说明是真的牛逼，那假设红黑树大小为 7 时变成链表，那万一又达到 8 了呢？（因为前面 8 这么低的概率还达到了 8），所以此时又要变成红黑树，还是会频繁的发生红黑树转链表，链表转红黑树，同样效率低下。

所以干脆中间给一个过渡值 7，差值 7 可以防止链表和树之间的频繁转换。

### 21. HashMap 和 Hashtable 的区别 ###

**1、继承的父类不同**

HashMap 继承自 AbstractMap 类。但二者都实现了Map接口。

Hashtable 继承自 Dictionary 类，Dictionary 类是一个已经被废弃的类（见其源码中的注释）。父类都被废弃，自然而然也没人用它的子类 Hashtable 了。

**2、线程安全**

HashMap 是线程不安全的类。

Hashtable 是线程安全的类。其中大部分方法基于 Synchronized。

**3、是否允许 null 值**

Hashmap 是允许 key 和 value 为 null 值。

HashTable键值对都不能为空，否则包空指针异常。

**4、扩容方式不同**

HashMap 哈希扩容必须要求为原容量的2倍，而且一定是2的幂次倍扩容结果，而且每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入，即扩容+ReHash。

Hashtable 扩容为原容量 2 倍加 1。

### 22. HashMap 和 LinkedHashMap 的区别 ###

我们知道 HashMap 其中之一的特点就是在获取元素时是无序的，而 LinkedHashMap 恰好解决了这个问题。

实际上 LinkedHashMap 继承自 HashMap，所以它的底层仍然是由数组和链表+红黑树构成，只是在此基础上LinkedHashMap 增加了一条双向链表，保持遍历顺序和插入顺序一致的问题。

HashMap 中存储数据的叫 Node，而 LinkedHashMap 中叫 Entry，但它继承自 HashMap.Node，如下：

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

Entry 中新增了两个引用，分别是 before 和 after，并且维护了两个头尾属性，因此从这里也可以看出它是一个双向链表：

/**
     * The head (eldest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> head;
    /**
     * The tail (youngest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> tail;

在实现上，LinkedHashMap 很多方法直接继承自 HashMap（比如put、remove方法就是直接用的父类的），仅为维护双向链表覆写了部分方法（get()方法是重写的）。

我们可以把 LinkedHashMap 理解为就是 HashMap 和 LinkedList 的一个结合。

参考：[LinkedHashMap 源码详细分析（JDK1.8）][LinkedHashMap _JDK1.8]

### 23. 说说 ConcurrentHashMap ###

对于 ConcurrentHashMap 来说实现相对比较复杂，这里大致说一下其实现机制。

jdk7 采用的是**分段锁**的概念，每一个分段都有一把锁（ReentrantLock），锁内存储的着数据，锁的个数在初始化之后不能扩容。

![image-20220121173439611][]

jdk8 的 ConcurrentHashMap 数据结构同 HashMap，通过 **Synchronized+CAS** 来保证其线程安全。

![image-20220121173502122][]

参考：[简单了解 ConcurrentHashMap 在 JDK7 和 JDK8 中的区别][ConcurrentHashMap _ JDK7 _ JDK8]

### 24. ConcurrentHashMap 的扩容机制 ###

**1.7 版本**

1.  1.7版本的 ConcurrentHashMa p是基于 Segment 分段实现的，每个Segment相对于⼀个⼩型的HashMap；
2.  每个 Segment 内部会进⾏扩容，和 HashMap 的扩容逻辑类似；
3.  先⽣成新的数组，然后转移元素到新数组中；
4.  扩容的判断也是每个 Segment 内部单独判断的，判断是否超过阈值。

**1.8 版本**

1.  1.8版本的 ConcurrentHashMap 不再基于 Segment 实现；
2.  当某个线程进⾏ put 时，如果发现 ConcurrentHashMap 正在进⾏扩容那么该线程⼀起进⾏扩容；
3.  如果某个线程 put 时，发现没有正在进⾏扩容，则将 key-value 添加到 ConcurrentHashMap 中，然后判断是否超过阈值，超过了则进⾏扩容；
4.  ConcurrentHashMap 是⽀持多个线程同时扩容的；
5.  扩容之前也先⽣成⼀个新的数组；
6.  在转移元素时，先将原数组分组，将每组分给不同的线程来进⾏元素的转移，每个线程负责⼀组或多组的元素转移⼯作。

### 25. 说说 TreeMap ###

TreeMap 是一个能比较元素大小的Map集合，会对传入的 key 进行了大小排序。可以使用元素的自然顺序，也可以使用集合中自定义的比较器来进行排序。

public class TreeMap<K,V>
        extends AbstractMap<K,V>
        implements NavigableMap<K,V>, Cloneable, java.io.Serializable
    {
        
    	......
    }

**TreeMap的特点：**

1.  TreeMap 是有序的 key-value 集合，通过**红黑树**实现。根据键的自然顺序进行排序或根据提供的 Comparator 进行排序。
2.  TreeMap 继承了 AbstractMap，实现了 NavigableMap 接口，支持一系列的导航方法，给定具体搜索目标，可以返回最接近的匹配项。如 floorEntry()、ceilingEntry() 分别返回小于等于、大于等于给定键关联的Map.Entry() 对象，不存在则返回 null。lowerKey()、floorKey、ceilingKey、higherKey()只返回关联的key。

### 26. Iterator 和 ListIterator ###

Iterator （迭代器）模式用同一种逻辑来遍历集合。它可以把访问逻辑从不同类型的集合类中抽象出来，不需要了解集合内部实现便可以遍历集合元素，统一使用 Iterator 提供的接口去遍历。它的特点是更加安全，因为它可以保证，在当前遍历的集合元素被更改的时候，就会抛出 `ConcurrentModificationException` 异常。

public interface Collection<E> extends Iterable<E> {
        
    	Iterator<E> iterator();
    }

主要有三个方法：`hasNext()`、`next()`和`remove()`。

ListIterator 是 Iterator的增强版。

*  ListIterator 遍历可以是逆向的，因为有 previous() 和 hasPrevious() 方法，而 Iterator 不可以。
 *  ListIterator 有 add() 方法，可以向 List 添加对象，而 Iterator 却不能。
 *  ListIterator 可以定位当前的索引位置，因为有 nextIndex() 和 previousIndex() 方法，而 Iterator 不可以。
 *  ListIterator 可以实现对象的修改，set() 方法可以实现。Iterator 仅能遍历，不能修改。
 *  ListIterator 只能用于遍历 List 及其子类，Iterator 可用来遍历所有集合。

### 27. 阻塞队列 ###

阻塞队列是`java.util.concurrent`包下重要的数据结构。

BlockingQueue 提供了线程安全的队列访问方式：

1.  当阻塞队列进行插入数据时，如果队列已满，线程将会阻塞等待直到队列非满；
2.  从阻塞队列取数据时，如果队列已空，线程将会阻塞等待直到队列非空。

并发包下很多高级同步类的实现都是基于 BlockingQueue 实现的，BlockingQueue 适合用于作为数据共享的通道。我们常用的线程池就是用的 BlockingQueue 来实现的。

使用阻塞算法的队列可以用一个锁（入队和出队用同一把锁）或两个锁（入队和出队用不同的锁）等方式来实现。

阻塞队列和一般的队列的区别就在于：

1.  **多线程支持**，多个线程可以安全的访问队列；
2.  **阻塞操作**，当队列为空的时候，消费线程会阻塞等待队列不为空；当队列满了的时候，生产线程就会阻塞直到队列不满。

其中的常用方法：

<table> 
 <thead> 
  <tr> 
   <th align="center">方法\处理方式</th> 
   <th align="center">抛出异常</th> 
   <th align="center">返回特殊值</th> 
   <th align="center">一直阻塞</th> 
   <th align="center">超时退出</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">插入方法</td> 
   <td align="center">add(e)</td> 
   <td align="center">offer(e)</td> 
   <td align="center">put(e)</td> 
   <td align="center">offer(e,time,unit)</td> 
  </tr> 
  <tr> 
   <td align="center">移除方法</td> 
   <td align="center">remove()</td> 
   <td align="center">poll()</td> 
   <td align="center">take()</td> 
   <td align="center">poll(time,unit)</td> 
  </tr> 
  <tr> 
   <td align="center">检查方法</td> 
   <td align="center">element()</td> 
   <td align="center">peek()</td> 
   <td align="center">-</td> 
   <td align="center">-</td> 
  </tr> 
 </tbody> 
</table>

BlockingQueue 的实现类有很多，这里列举以下几个常用的队列：

**1、ArrayBlockingQueue**

有界阻塞队列，底层采用数组实现。ArrayBlockingQueue 一旦创建，容量不能改变。其并发控制采用可重入锁来控制，不管是插入操作还是读取操作，都需要获取到锁才能进行操作。此队列按照先进先出（FIFO）的原则对元素进行排序。默认情况下不能保证线程访问队列的公平性，参数`fair`可用于设置线程是否公平访问队列。为了保证公平性，通常会降低吞吐量。

**2、LinkedBlockingQueue**

LinkedBlockingQueue是一个用单向链表实现的有界阻塞队列，可以当做无界队列也可以当做有界队列来使用。通常在创建 LinkedBlockingQueue 对象时，会指定队列最大的容量。此队列的默认和最大长度为`Integer.MAX_VALUE`。此队列按照先进先出的原则对元素进行排序。与 ArrayBlockingQueue 相比起来具有更高的吞吐量。

**3、PriorityBlockingQueue**

支持优先级的**无界**阻塞队列。默认情况下元素采取自然顺序升序排列。也可以自定义类实现`compareTo()`方法来指定元素排序规则，或者初始化PriorityBlockingQueue时，指定构造参数`Comparator`来进行排序。

PriorityBlockingQueue 只能指定初始的队列大小，后面插入元素的时候，如果空间不够的话会**自动扩容**。

PriorityQueue 的线程安全版本。不可以插入 null 值，同时，插入队列的对象必须是可比较大小的（comparable），否则报 ClassCastException 异常。它的插入操作 put 方法不会 block，因为它是无界队列（take 方法在队列为空的时候会阻塞）。

**4、DelayQueue**

支持延时获取元素的无界阻塞队列。队列使用 PriorityBlockingQueue 来实现。队列中的元素必须实现Delayed接口，在创建元素时可以指定多久才能从队列中获取当前元素。只有在延迟期满时才能从队列中提取元素。

**5、SynchronousQueue**

不存储元素的阻塞队列，每一个 put 必须等待一个 take 操作，否则不能继续添加元素。支持公平访问队列。

SynchronousQueue 可以看成是一个传球手，负责把生产者线程处理的数据直接传递给消费者线程。队列本身不存储任何元素，非常适合传递性场景。SynchronousQueue 的吞吐量高于 LinkedBlockingQueue 和 ArrayBlockingQueue。

**6、LinkedTransferQueue**

由链表结构组成的无界阻塞 TransferQueue 队列。相对于其他阻塞队列，多了 tryTransfer 和 transfer 方法。

transfer 方法：如果当前有消费者正在等待接收元素（take或者待时间限制的poll方法），transfer 可以把生产者传入的元素立刻传给消费者。如果没有消费者等待接收元素，则将元素放在队列的tail节点，并等到该元素被消费者消费了才返回。

tryTransfer 方法：用来试探生产者传入的元素能否直接传给消费者。如果没有消费者在等待，则返回 false。和上述方法的区别是该方法无论消费者是否接收，方法立即返回。而 transfer 方法是必须等到消费者消费了才返回。

### 28. 哪些集合类是线程安全的？哪些不安全 ###

线性安全的集合类：

*  Vector
 *  Stack
 *  Hashtable
 *  CopyOnWriteArrayList
 *  ConcurrentHashMap

线性不安全的集合类：

*  ArrayList
 *  LinkedList
 *  HashSet
 *  TreeSet
 *  HashMap
 *  TreeMap
 *  LinkedHashMap

### 29. 什么是 fail fast ###

fast-fail 是 Java 集合的一种错误机制。当多个线程对同一个集合进行操作时，就有可能会产生 fail-fast 事件。

例如：当线程 a 正通过iterator遍历集合时，另一个线程 b 修改了集合的内容，此时 modCount（记录集合操作过程的修改次数）会加1，不等于 expectedModCount，那么线程 a 访问集合的时候，就会抛出`ConcurrentModificationException`，产生 fast-fail 事件。边遍历边修改集合也会产生 fast-fail 事件。

常见的线程不安全的集合都会出现这种错误，如 ArrayList ：

final void checkForComodification() {
        
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }

如下：

public static void main(String[] args) {
        
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
        
            System.out.println(iterator.next());
            list.add(3);
            System.out.println(list.size());
        }
    }

运行结果：

1
    4
    Exception in thread "main" java.util.ConcurrentModificationException
    	at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1042)
    	at java.base/java.util.ArrayList$Itr.next(ArrayList.java:996)
    	at com.fanryes.vanadium.cloud.Tealksk.main(Tealksk.java:43)

解决方法：

*  使用 `Colletions.synchronizedList` 方法或在修改集合内容的地方加上 synchronized。这样的话，增删集合内容的同步锁会阻塞遍历操作，影响性能。
 *  使用 `CopyOnWriteArrayList` 来替换 ArrayList。在对 CopyOnWriteArrayList 进行修改操作的时候，会拷贝一个新的数组，对新的数组进行操作，操作完成后再把引用移到新的数组。

### 30. 什么是fail safe ###

采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

`java.util.concurrent`包下的容器都是安全失败，可以在多线程下并发使用，并发修改。

**原理**：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发 `ConcurrentModificationException`。

**缺点**：基于拷贝内容的优点是避免了`ConcurrentModificationException`，但同样地，迭代器并不能访问到修改后的内容，即：

迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。

[Java]: https://javatv.net/pages/be9f91/
[image-20220117142757454]: https://img-blog.csdnimg.cn/img_convert/8a4373623865557ecf721dd32db22a7d.png
[ArrayList]: https://javatv.blog.csdn.net/article/details/117265931
[image-20220118104920869]: https://img-blog.csdnimg.cn/img_convert/3b39b0ed3b2e59db61feabc31db60577.png
[HashMap]: https://javatv.blog.csdn.net/article/details/122403739
[Link 1]: https://javatv.blog.csdn.net/article/details/118741724
[Link 2]: https://javatv.blog.csdn.net/article/details/118941644
[LinkedList]: https://javatv.blog.csdn.net/article/details/117308367
[Link 3]: https://juejin.cn/post/6981275430049284110
[Link 4]: https://juejin.cn/post/6982740666849853454
[image-20220117172538968]: https://img-blog.csdnimg.cn/img_convert/6573e0582bdd16c09cb081421c76c54d.png
[Link 5]: https://javatv.blog.csdn.net/article/details/118678606
[image-20220118135835673]: https://img-blog.csdnimg.cn/img_convert/62698251d18501fbbde849d7f05e41bc.png
[3ff5a426e42abb3c372d31c97ab2b42d]: https://img-blog.csdnimg.cn/img_convert/0a209748dba793d5f7c4c2631163457a.png
[image-20220104145843344]: https://img-blog.csdnimg.cn/img_convert/f0cae7576d837530dc377a1faf5284df.png
[image-20220105195041298]: https://img-blog.csdnimg.cn/img_convert/5912110c46318634cde9d766ca820a11.png
[image-20220105202014726]: https://img-blog.csdnimg.cn/img_convert/a2c2d214924013719fb807c1c728c5ce.png
[image-20220106152324204]: https://img-blog.csdnimg.cn/img_convert/aba6f299d6dedc55f729e374824c9462.png
[image-20220107161745890]: https://img-blog.csdnimg.cn/img_convert/97580c3bb46233ce12f72285eca28349.png
[image-20220107163640649]: https://img-blog.csdnimg.cn/img_convert/d9fda9b1f03d017347c2beb9e8255a2d.png
[image-20220107175932194]: https://img-blog.csdnimg.cn/img_convert/12d3b692811846ac3e35acd404504d3c.png
[image-20220107180130441]: https://img-blog.csdnimg.cn/img_convert/ac5c9651cc7e15c2e7494ad95ccc6927.png
[image-20220108131439917]: https://img-blog.csdnimg.cn/img_convert/5ed460a7e2540c4360ede8d8c76ff0f8.png
[image-20220108133603691]: https://img-blog.csdnimg.cn/img_convert/f39a81a973ba83af4c4d18991f27ef0b.png
[Link 6]: https://javatv.blog.csdn.net/article/details/119120401
[Link 7]: https://baike.baidu.com/item/%E6%B3%8A%E6%9D%BE%E5%88%86%E5%B8%83/1442110
[Link 8]: https://www.zhihu.com/question/21680896/answer/466229561
[LinkedHashMap _JDK1.8]: https://segmentfault.com/a/1190000012964859
[image-20220121173439611]: https://img-blog.csdnimg.cn/img_convert/8d591104bf88f730e5135474cc3555f4.png
[image-20220121173502122]: https://img-blog.csdnimg.cn/img_convert/d5014653d472e06cc6aaaae25b2eefde.png
[ConcurrentHashMap _ JDK7 _ JDK8]: https://blog.csdn.net/weixin_43477531/article/details/122609065