内容来源于网络，如有侵权请联系删除

Java 中有哪些集合类？请简单介绍 ？

Java 中的集合类主要分为两大类：Collection 接口和 Map 接口。前者是存储对象的集合类，后者存储的是键值对（key-value）。

Collection 接口下又分为 List、Set 和 Queue 接口。每个接口有其具体实现类。以下是主要的集合类：

List 接口：

• ArrayList：基于动态数组，查询速度快，插入、删除慢。
• LinkedList：基于双向链表，插入、删除快，查询速度慢。
• Vector：线程安全的动态数组，类似于 ArrayList，但开销较大。

Set 接口：

• HashSet：基于哈希表，元素无序，不允许重复。
• LinkedHashSet：基于链表和哈希表，维护插入顺序，不允许重复。
• TreeSet：基于红黑树，元素有序，不允许重复。

所以网上有些说 Set 是无序集合非常不准确，因为需要看具体的实现类。

Queue 接口：

• PriorityQueue：基于优先级堆，元素按照自然顺序或指定比较器排序。
• LinkedList：可以作为队列使用，支持 FIFO（先进先出）操作。

Map 接口：

存储的是键值对，也就是给对象（value）设置了一个 key，这样通过 key 可以找到那个 value。

• HashMap：基于哈希表，键值对无序，不允许键重复。
• LinkedHashMap：基于链表和哈希表，维护插入顺序，不允许键重复。
• TreeMap：基于红黑树，键值对有序，不允许键重复。
• Hashtable：线程安全的哈希表，不允许键或值为 null。
• ConcurrentHashMap：线程安全的哈希表，适合高并发环境，不允许键或值为 null。

这题一般会在面试刚开始的时候被问，主要用于暖场热身，不需要说的那么详细，大致讲下，面试官会根据你回答的点继续挖的。

PS：可尝试结合类图，对常见的实现类关系重点记忆，面试时可对自己擅长的实现类详细介绍或引导，也可做一定的取舍。

注意类图中“接口–>抽象类 –>实现类”的整体框架，可以体现一点 Java 的设计理念，可根据此记忆也可根据此在面试的时候详细说明，可延展出 Java 的接口和抽象类的区别。

扩展：LinkedHashMap

什么是 Java 的 LinkedHashMap？

扩展：TreeMap

什么是 Java 的 TreeMap？

Java 中的 List 接口有哪些实现类？

List 接口主要包含 ArrayList、LinkedList、Vector、Stack、CopyOnWriteArrayList 几个实现类。

最常见的就是 ArrayList 和 LinkedList，注意这两者都不是并发容器，所以线程不安全。

ArrayList 是基于动态数组实现的，因此它的特性与数组一致，随机访问很快，删除和插入相对比较慢。

• 随机访问时间复杂度为 O(1)。
• 插入和删除（除了在列表末尾）时间复杂度为 O(n)。

LinkedList 是基于双向链表实现的，因此两端都能操作，特性就是正常的链表特性，两端插入删除很快，但是随机访问需要遍历链表所以比较慢。

• 随机访问时间复杂度为 O(n)，需要遍历链表
• 插入和删除时间复杂度为 O(1)。

扩展 Vector

它也是基于动态数组实现，与 ArrayList 类似，但它是线程安全，所有方法都是同步的。

可以看到，都加了 synchronized 这把锁。

也因为同步开销较大，所以它性能相对较低。

扩展 CopyOnWriteArrayList

它也是基于动态数组实现，但所有可变操作（如 add()、set() 等）都会创建一个新的数组。

它其实运用了一个叫写时复制的技术，即当写的时候，再去复制。

它是线程安全的，适合在多线程环境中频繁读取、很少修改的场景。

扩展 AbstractList

它一个抽象类，实现了 List 接口的大部分方法，提供了基本的 List 功能。

如果我们想要扩展实现自己的列表，那么可以用它作为自定义列表实现的基础类，大大减少我们的自定义成本。

Java 中 ArrayList 和 LinkedList 有什么区别？

底层数据结构不同：

• ArrayList：基于动态数组实现，元素在内存中连续存储。
• LinkedList：基于双向链表实现，元素通过节点链接，内存中不需要连续存储。

性能区别：

1）ArrayList：

• 随机访问速度快，查找元素的时间复杂度为 O(1)。
• 插入和删除操作慢，尤其是在中间插入或删除时，时间复杂度为 O(n)，因为需要移动后续元素。

2）LinkedList：

• 随机访问速度慢，查找元素的时间复杂度为 O(n)。
• 插入和删除操作快，尤其是在头尾插入或删除时，时间复杂度为 O(1)。

LinkedList 常见接口介绍

LinkedList 分别实现了 List 和 Deque 接口。

List 接口相关方法

• **add(E e)**：将指定元素添加到列表的末尾。
• **add(int index, E element)**：在指定位置插入元素。
• **get(int index)**：返回指定位置的元素。
• **set(int index, E element)**：用指定元素替换指定位置的元素。
• **remove(int index)**：移除指定位置的元素。
• **indexOf(Object o)**：返回指定元素在列表中的首次出现位置，如果列表中不包含该元素，返回 -1。
• **lastIndexOf(Object o)**：返回指定元素在列表中最后一次出现的位置，如果列表中不包含该元素，返回 -1。
• **size()**：返回列表中的元素数量。

Deque 接口相关方法

• **addFirst(E e)**：在列表的开头插入指定元素。
• **addLast(E e)**：在列表的末尾插入指定元素。
• **removeFirst()**：移除并返回列表的第一个元素。
• **removeLast()**：移除并返回列表的最后一个元素。
• **peekFirst()**：返回列表的第一个元素，但不移除它，如果列表为空，返回 null。
• **peekLast()**：返回列表的最后一个元素，但不移除它，如果列表为空，返回 null。
• **push(E e)**：将元素推入列表的开头。
• **pop()**：移除并返回列表的第一个元素。

其他常用方法

• **clear()**：移除列表中的所有元素。
• **toArray()**：返回包含列表所有元素的数组。
• **iterator()**：返回列表的迭代器，用于遍历元素。

使用示例：

1
2
3
4
5
6
7
8
9

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.addFirst("C"); // C A B
linkedList.addLast("D");  // C A B D

System.out.println(linkedList.get(2)); // 输出: B
linkedList.removeFirst(); // A B D
System.out.println(linkedList.peekLast()); // 输出: D

Java ArrayList 的扩容机制是什么？

当 ArrayList 中的元素数量超过其当前容量时，会触发扩容机制。默认情况下，ArrayList 的初始容量为 10。

当发生扩容时，ArrayList 会创建一个新的数组，其容量为原数组的 1.5 倍（即 oldCapacity + (oldCapacity >> 1)），然后将原数组中的元素复制到新数组中。

复制过程是通过 Arrays.copyOf() 方法实现的。

性能问题：

扩容是一个相对耗时的操作，因为需要分配新的内存并复制元素。频繁的扩容会影响性能，因此建议在创建 ArrayList 时根据预期的元素数量设置合适的初始容量。

ArrayList 提供多个构造函数，可以指定初始容量。例如：

1

List<Integer> list = new ArrayList<>(50); // 设置初始容量为 50

负载因子

• ArrayList 的扩容机制与负载因子（即当前元素数量与数组容量的比值）无关，不同于哈希表等数据结构。ArrayList 采用固定比例的扩容策略。

扩容源码解析

往 ArrayList 中添加元素时会有 ensureCapacityInternal 的判断， size + 1 则为添加次元素后，ArrayList 中的元素数：

1
2
3
4
5

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

ensureCapacityInternal 内部会调用 ensureExplicitCapacity 方法，若 minCapacity - elementData.length > 0 即容量不够了，则会调用 grow 方法：

minCapacity 是所需的最小容量，用于确保扩容后数组至少能容纳这个数量的元素（一般为传入的 size + 1 数）

1
2
3
4
5
6
7

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

grow 就是实际的扩容逻辑：

1
2
3
4
5
6
7
8
9
10
11

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

oldCapacity 就是数组的容量。

oldCapacity + (oldCapacity >> 1) 等价于 oldCapacity + (oldCapacity / 2)，即设置新容量设为当前容量的 1.5。

下面这段代码就是一个容错处理，MAX_ARRAY_SIZE 值为 Integer.MAX_VALUE - 8，防止新容量的值超过数组的最大限制。

1
2

if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);

1
2
3
4
5
6
7

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? //若超过，则控制下大小
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

Java 中的 HashMap 和 Hashtable 有什么区别？

1）线程安全性：

• HashMap：非线程安全，多线程环境下可能会产生数据不一致问题。
• Hashtable：线程安全，内部大部分方法都使用了 synchronized 关键字进行同步，保证了多线程的并发安全性。

2）性能差异：

• HashMap：由于没有线程同步开销，因此在单线程环境下性能优于 Hashtable。
• Hashtable：由于方法的同步锁机制，性能低于 HashMap。由于使用全局锁的方式，使得即使是不同的操作也会被串行化。

3）允许空值：

• HashMap：允许一个 null 键和多个 null 值。
• Hashtable：不允许 null 键和 null 值，插入 null 键或 null 值时会抛出 NullPointerException。

4）继承结构：

• HashMap：继承自 AbstractMap，是 Map 接口的实现类。
• Hashtable：继承自 Dictionary（已废弃），后来也实现了 Map 接口。它是一种较为古老的类，在 Java 2 之后逐渐被 HashMap 所取代（不推荐使用）。

5）迭代器类型：

• HashMap：使用的是快速失败的 Iterator，在迭代过程中如果对 Map 进行结构性修改，会抛出 ConcurrentModificationException。
• Hashtable：使用的是弱一致性的 Enumerator，虽然也不建议在迭代过程中修改 Map，但不会抛出 ConcurrentModificationException。

ConcurrentHashMap vs Hashtable：

• ConcurrentHashMap 是 Hashtable 的替代方案。它在实现线程安全的同时，通过分段锁机制提高了并发性能，避免了全局锁导致的性能瓶颈。适用于高并发环境。
• ConcurrentHashMap 的读操作无锁化，写操作则使用了局部锁分段，使得在高并发下性能大大优于 Hashtable。

ConcurrentHashMap 相关面试题

• 461. Java 中 ConcurrentHashMap 1.7 和 1.8 之间有哪些区别？
• 462. Java 中 ConcurrentHashMap 的 get 方法是否需要加锁？
• 463. 为什么 Java 的 ConcurrentHashMap 不支持 key 或 value 为 null？

ConcurrentHashMap 和 Hashtable 的区别是什么？

它们都是 Java 中常用的线程安全的哈希表实现，它们主要在性能有显著的差异。

因为在线程安全性上的实现方式不同，导致了它们性能上的差别：

• **Hashtable**：Hashtable 使用的是单一的锁机制（全表锁），即对整个哈希表进行同步，所有的操作（如插入、删除、查找等）都必须通过一个锁（synchronized）来保证线程安全。这种方式使得 Hashtable 在多线程环境下效率较低，因为无论是读取还是写入操作都需要获得锁，无法做到并发访问。
• **ConcurrentHashMap**：在 Java 8 中，ConcurrentHashMap 采用了 CAS + synchronized 的方式进行线程安全控制。CAS 用于无锁的写入操作。如果某个 Node 节点为空，则通过 CAS 将数据插入节点。如果不为空，则会退化到 synchronized。使用 synchronized 锁定冲突节点的头结点。这种锁的粒度更细，仅锁住特定的冲突节点，而非整个表，因此在并发访问时性能较好。高的并发性能。

Hashtable 的历史背景

Hashtable 是早期 Java 提供的线程安全的哈希表实现，它的设计使用了全表锁来保证线程安全。然而，随着多核 CPU 和高并发场景的普及，Hashtable 的性能问题显现出来。因此，Java 在 Java 5 引入了 ConcurrentHashMap，解决了 Hashtable 性能瓶颈和其他限制。

Hashtable 和 ConcurrentHashMap 的适用场景

• **Hashtable**：由于性能较差，Hashtable 适用于线程数较少、对性能要求不高的场景，但在现代 Java 开发中，已很少使用 Hashtable。
• **ConcurrentHashMap**：适用于高并发的场景，尤其是在多线程读写操作频繁的情况下，ConcurrentHashMap 能够提供比 Hashtable 更高的性能和更低的延迟。因此，ConcurrentHashMap 更适用于大规模分布式缓存、Web 应用程序中的缓存、以及需要高并发读写的系统。

线程安全集合类

Java 中的线程安全集合类除了 Hashtable 和 ConcurrentHashMap，还有 Collections.synchronizedMap（它是对任何普通 Map 的封装，提供同步操作）和 CopyOnWriteArrayList 等。

• 464. Java 中的 CopyOnWriteArrayList 是什么？

ConcurrentHashMap 1.7 和 1.8 之间有哪些区别

• 461. Java 中 ConcurrentHashMap 1.7 和 1.8 之间有哪些区别？

Java 中的 HashSet 和 HashMap 有什么区别？

HashSet：是基于 HashMap 实现的集合类，不允许重复元素，用于存储一组无序的唯一元素。

HashMap：基于哈希表的数据结构，存储的是键值对（key-value），键必须唯一，值可以重复。

实际上HashSet 内部使用 HashMap 来实现，HashSet 中的元素实际上存储在 HashMap 的键中，而所有的值都是一个常量对象 PRESENT。因此，HashSet 仅操作 HashMap 的键部分。

HashSet 内部依赖 HashMap

来看下源码：

从上图我们可以发现，构造一个 HashSet 内部就是 new 了一个 HashMap。

并且 HashSet#add 方法实际上调用的就是 HashMap 的 put

这里默认填了个 PRESNET, 实际上就是定义的一个 Object 没有任何意义，仅为了适配 map 需要一个 value 罢了。

因此 HashSet 就是封装了一下 HashMap！，因此许多 HashSet 的操作（如 add()、remove() 等）实际上是调用 HashMap 的相应方法，内部的实现逻辑其实都由 HashMap 来代劳。

说说 Java 中 HashMap 的原理？

HashMap 是基于哈希表的数据结构，用于存储键值对（key-value）。其核心是将键的哈希值映射到数组索引位置，通过数组 + 链表（在 Java 8 及之后是数组 + 链表 + 红黑树）来处理哈希冲突。

HashMap 使用键的 hashCode() 方法计算哈希值，并通过 indexFor 方法（JDK 1.7 及之后版本移除了这个方法，直接使用 (n - 1) & hash]）确定元素在数组中的存储位置。哈希值是经过一定扰动处理的，防止哈希值分布不均匀，从而减少冲突。

HashMap 的默认初始容量为 16，负载因子为 0.75。也就是说，当存储的元素数量超过 16 × 0.75 = 12 个时，HashMap 会触发扩容操作，容量x2并重新分配元素位置。这种扩容是比较耗时的操作，频繁扩容会影响性能。

HashMap 的红黑树优化：

从 Java 8 开始，为了优化当多个元素映射到同一个哈希桶（即发生哈希冲突）时的查找性能，当链表长度超过 8 时，链表会转变为红黑树。红黑树是一种自平衡二叉搜索树，能够将最坏情况下的查找复杂度从 O(n) 降低到 O(log n)。

如果树中元素的数量低于 6，红黑树会转换回链表，以减少不必要的树操作开销。

hashCode() 和 equals() 的重要性：

HashMap 的键必须实现 hashCode() 和 equals() 方法。hashCode() 用于计算哈希值，以决定键的存储位置，而 equals() 用于比较两个键是否相同。在 put 操作时，如果两个键的 hashCode() 相同，但 equals() 返回 false，则这两个键会被视为不同的键，存储在同一个桶的不同位置。

误用 hashCode() 和 equals() 会导致 HashMap 中的元素无法正常查找或插入。

• 428. Java 中的 hashCode 和 equals 方法之间有什么关系？

默认容量与负载因子的选择：

默认容量是 16，负载因子为 0.75，这个组合是在性能和空间之间找到的平衡。较高的负载因子（如 1.0）会减少空间浪费，但增加了哈希冲突的概率；较低的负载因子则会增加空间开销，但减少哈希冲突。

如果已知 HashMap 的容量需求，建议提前设定合适的初始容量，以减少扩容带来的性能损耗。

哈希冲突链表法图解

当要塞入一个键值对的时候，会根据一个 hash 算法计算 key 的 hash 值，然后通过数组大小 n-1 & hash 值之后，得到一个数组的下标，然后往那个位置塞入这键值对。

hash 算法是可能产生冲突的，且数组的大小是有限的，所以很可能通过不同的 key 计算得到一样的下标，因此为了解决键值对冲突的问题，采用了链表法，如下图所示：

在 JDK1.7 及之前链表的插入采用的是头插法，即每当发生哈希冲突时，新的节点总是插入到链表的头部，老节点依次向后移动，形成新的链表结构。

在多线程环境下，头插法可能导致链表形成环，特别是在并发扩容时（rehashing）。当多个线程同时执行 put() 操作时，如果线程 A 正在进行头插，线程 B 也在同一时刻操作链表，可能导致链表结构出现环路，从而引发死循环，最终导致程序卡死或无限循环。

举个例子：

假如此时线程 1 和 2 同时在插入，同时触发了扩容：

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

void transfer(Entry[] newTable) {
  Entry[] src = table; 
  int newCapacity = newTable.length;
  for (int j = 0; j < src.length; j++) { 
      Entry<K,V> e = src[j];           
      if (e != null) {
          src[j] = null; 
          do { 
              Entry<K,V> next = e.next; 
             int i = indexFor(e.hash, newCapacity);//线程1执行到这没cpu时间片，线程2继续执行
             e.next = newTable[i]; 
             newTable[i] = e;  
             e = next;             
         } while (e != null);
     }
 }
}

假设此时，线程 1 中 e 是 A，next 为 B，刚要开始搬运，时间片到了，此时停止操作（停止在源码中注释那一行）。

而线程 2 开始扩容，且成功扩容完毕，此时：

待线程 2 扩容完毕后，线程 1 得到了时间片要开始执行了，它开始执行以下代码：

1
2
3

e.next = newTable[i];  // A.next = C
newTable[i] = e;   
e = next;  

此时 A.next = C， A 被放到数组上，e 变成 B，此时环已经产生。

在 JDK1.8 的时候，改成了尾插法，即新的节点插入到链表的尾部，保持插入的顺序。并且引入了红黑树。

当链表的长度大于 8 且数组大小大于等于 64 的时候，就把链表转化成红黑树，当红黑树节点小于 6 的时候，又会退化成链表。

HashMap流程：

Java 中 HashMap 的扩容机制是怎样的？

HashMap 中的扩容是基于负载因子（load factor） 来决定的。默认情况下，HashMap 的负载因子为 0.75，这意味着当 HashMap 的已存储元素数量超过当前容量的 75% 时，就会触发扩容操作。

例如，初始容量为 16，负载因子为 0.75，则扩容阈值为 16 × 0.75 = 12。当存入第 13 个元素时，HashMap 就会触发扩容。

当触发扩容时，HashMap 的容量会扩大为当前容量的两倍。例如，容量从 16 增加到 32，从 32 增加到 64 等。

扩容时，HashMap 需要重新计算所有元素的哈希值，并将它们重新分配到新的哈希桶中，这个过程称为rehashing。每个元素的存储位置会根据新容量的大小重新计算哈希值，并移动到新的数组中。

rehashing 细节

按照我们的思维，每一个元素应该是重新 hash 一个一个搬迁过去。

在 1.7 的时候就是这样实现的，然而 1.8 在这里做了优化，关键点就在于数组的长度是 2 的次方，且扩容为 2 倍。

因为数组的长度是 2 的 n 次方，所以假设以前的数组长度（16）二进制表示是 010000，那么新数组的长度（32）二进制表示是 100000，这个应该很好理解吧？

它们之间的差别就在于高位多了一个 1，而我们通过 key 的 hash 值定位其在数组位置所采用的方法是 (数组长度-1) & hash。我们还是拿 16 和 32 长度来举例：

1
2

16-1=15，二进制为 001111
32-1=31，二进制为 011111

所以重点就在 key 的 hash 值的从右往左数第五位是否是 1，如果是 1 说明需要搬迁到新位置，且新位置的下标就是原下标+16（原数组大小），如果是 0 说明吃不到新数组长度的高位，那就还是在原位置，不需要迁移。

所以，我们刚好拿老数组的长度（010000）来判断高位是否是 1，这里只有两种情况，要么是 1 要么是 0 。

从上面的源码可以看到，链表的数据是一次性计算完，然后一堆搬运的，因为扩容时候，节点的下标变化只会是原位置，或者原位置+老数组长度，不会有第三种选择。

上面的位操作，包括为什么是原下标+老数组长度等，如果你不理解的话，可以举几个数带进去算一算，就能理解了。

总结一下：

• 当扩容发生时，HashMap 并不是简单地将元素复制到新数组中。每个元素的哈希值会根据新的数组容量重新计算，因此元素的存储位置会发生变化
• Java 8 之后的扩容不需要每个节点重新 hash 算下标，因为元素的新位置只与高位有关，通过和老数组长度的 & 计算是否为 0 就能判断新下标的位置，因此链表中的元素可能只需要部分移动。这一优化减少了扩容时的计算开销。

扩容的考虑

每次扩容都需要遍历当前所有的元素，重新计算哈希值并移动它们到新的位置，因此扩容是一个比较耗时的操作。如果频繁扩容，整体性能会明显下降。

优化策略：如果能预估到 HashMap 中大概会存储多少数据，可以在创建 HashMap 时就指定一个较大的初始容量，以减少扩容次数。例如，对于存储 100 万个元素的 HashMap，可以直接设置一个 1024 × 1024 的初始容量，避免多次扩容。

场景题

• 752. 假设有一个 1G 大的 HashMap，此时用户请求过来刚好触发它的扩容，会怎样？怎么优化？

为什么 HashMap 在 Java 中扩容时采用 2 的 n 次方倍？

HashMap 采用 2 的 n 次方倍作为容量，主要是为了提高哈希值的分布均匀性和哈希计算的效率。

HashMap 通过 (n - 1) & hash 来计算元素存储的索引位置，这种位运算只有在数组容量是 2 的 n 次方时才能确保索引均匀分布。位运算的效率高于取模运算（hash % n），提高了哈希计算的速度。

且当 HashMap 扩容时，通过容量为 2 的 n 次方，扩容时只需通过简单的位运算判断是否需要迁移，这减少了重新计算哈希值的开销，提升了 rehash 的效率。

哈希分布均匀性

如果数组容量为 2 的 n 次方，那么 n - 1 后低位都是 1 ，此时进行 & （两个位都为 1 时，结果才为 1）运算可以确保哈希码的最低几位均匀分布。

比如 64 二进制表示为 0100 0000，64 - 1 = 0011 1111。

此时 0011 1111 与哈希码进行 & 运算，低位能均匀的反应出哈希码的随机性。

假设来个 0100 0000 与哈希码进行 & 运算，那么低位得到的值就都是 0 了，随机性很差，都是冲突。

位运算与取模

正常情况下，如果基于哈希码来计算数组下标，我们想到的都是 %（取余）计算。例如数组长度为 5 ，那么哈希码 % 5 得到的值就是对应的数组下标。

但相比于位运算而言，效率比较低，所以推荐用位运算，而要满足 i = (n - 1) & hash 这个公式，n 的大小就必须是 2 的 n 次幂。即：当 b 等于 2 的 n 次幂时，a % b 操作等于 a & ( b - 1 )

为什么 Java 中 HashMap 的默认负载因子是 0.75？

HashMap 的默认负载因子为 0.75 是为了在时间复杂度和空间复杂度之间取得一个合理的平衡。负载因子为 0.75 时，避免过多扩容的同时，也保证了不会出现过多的哈希冲突，确保查找和插入操作的效率，维持良好的性能表现。

什么是负载因子

负载因子是 HashMap 中的一个参数，用来衡量 HashMap 的满载程度，公式为： 负载因子 = 实际存储的元素数量 / 容量。

当 HashMap 中存储的元素数量超过 容量 × 负载因子 时，HashMap 会进行扩容操作，增加容量以维持性能。

为什么不选择 1.0 作为默认负载因子

尽管负载因子 1.0 可以减少扩容次数，提高内存利用率，但它增加了哈希冲突的可能性。冲突过多会导致桶内链表或红黑树变长，降低查找、插入和删除的效率。因此，负载因子 1.0 会使得时间复杂度劣化为 O(n)，不利于 HashMap 的高效运行。

HashMap 源码注释解读

其实在 HashMap 的源码中有这么一段注释：

简单理解下就是设置 0.75 是因为空间和时间上的平衡。

较低的负载因子（例如 0.5）会导致 HashMap 需要频繁扩容，空间利用率就低。不过因为冲突少，查找效率就高，但是因为扩容频繁会增加 rehashing 的开销。

较高的负载因子（例如 1.0）会减少扩容次数，空间利用率高了，但会增加哈希冲突的概率，从而降低查找效率。

经过大量实践，0.75 被认为是大多数场景下比较合适的值，能够在时间和空间之间取得良好的平衡。

所以设置了 0.75。

不同场景下的负载因子调整

在某些特定场景下，可以根据业务需求调整 HashMap 的负载因子。例如：

• 高并发读取场景：可以降低负载因子（如 0.5），以减少哈希冲突，提高读取性能。
• 内存受限场景：可以提高负载因子（如 0.85 或更高），以减少扩容次数和内存消耗，但可能会降低写入和查询的性能。

使用 HashMap 时，有哪些提升性能的技巧？

1）合理设置初始容量：

如果在使用时可以预估 HashMap 存储的数据量大小，那么需要在创建时设置一个合适的初始容量，以避免频繁的扩容操作。

Java 中 HashMap 默认初始容量是 16。

2）调整负载因子：

官方提供的默认负载因子是 0.75。

可以根据具体应用场景调整这个值。较低的负载因子会减少冲突，提高查找效率，但会占用更多内存。较高的负载因子则会减少内存消耗，但可能增加冲突的概率，降低查找效率。

3）确保 hashCode 均匀分布：

对应 key 的 hashCode() 方法生成的哈希值需均匀分布，减少哈希冲突。避免使用质量不高的哈希函数，防止大量键映射到相同的槽位上，造成性能瓶颈。

HashMap 扩容机制的性能影响

扩容触发条件：

当 HashMap 中的元素数量超过容量 × 负载因子时，会触发扩容。扩容会将容量扩展为当前容量的两倍，并将所有键值对重新分配到新的桶（bucket）中。

性能影响：

扩容是一个耗时的操作，因为它需要重新计算每个键的哈希值，并将键值对重新分配到新的桶中。因此，频繁的扩容会显著影响性能，特别是在存储大量数据时。

其他优化

例如需要保留元素的插入顺序，则可以使用 LinkedHashMap替换 HashMap。它基于 HashMap 但维护了一个链表，记录元素的插入顺序。

这样就不需要我们从 HashMap 中获取数据，然后再排序。

如果是需要保留有序的键值对，则可以使用 TreeMap。

如果是线程安全场景，则可以使用 ConcurrentHashMap。

什么是 Hash 碰撞/冲突？怎么解决哈希碰撞/冲突？

Hash 碰撞是指在使用哈希算法时，不同的输入数据通过哈希函数计算后，得到了相同的哈希值（即散列值）。因为哈希值相同，所以这些键会被映射到哈希表的同一个位置，从而引发“碰撞”。

常见有以下几种方式解决哈希碰撞问题：

1）拉链法（链地址法）：

将哈希表中每个槽的位置变成一个链表，当多个键的哈希值相同时，将它们存储在同一个链表中。

2）开放寻址法：

如果出现碰撞，寻找哈希表中的下一个可用位置。

3）再哈希法（双重哈希）：

在出现碰撞时，使用第二个哈希函数计算新的索引位置，减少碰撞的概率。

拉链法（链地址法）

使用链表来处理冲突，每个哈希表的槽（bucket）不仅存储单个元素，而是存储指向链表头部的指针。所有具有相同哈希值的元素都会被放入到同一个链表中。

优点：

• 简单易实现，扩展性好。
• 在处理大量数据时，性能更为稳定。

缺点：

• 如果碰撞频繁，链表会变长，导致查询性能下降。
• 需要额外的内存来存储链表的指针。

红黑树优化

当冲突产生的链表长度超过一定阈值时，可以将链表转换为红黑树。红黑树的查找时间复杂度为 O(log n)，相较于链表 O(n) 的查找复杂度，性能更高。

这个优化可以大幅提升在极端情况下的查找性能。

缺点就是实现复杂，且需要更多的内存空间。

在 Java 8 中的 HashMap 使用了链表转红黑树的解决方案。 详细可看为什么 JDK 1.8 对 HashMap 进行了红黑树的改动？

开放寻址法

在哈希表中寻找下一个空闲的槽位以存储发生碰撞的元素，常见寻找方式有线性探查、平方探查和双重散列。

优点：

• 不需要额外的内存来存储指针或链表结构。
• 如果负载因子低，查找和插入的效率较高。

缺点：

• 随着哈希表的填充度增加，探查的次数会增加，导致性能下降。
• 删除元素时候，不能真的删除，只能打标，否则会导致查找错误。只能在下一个元素插入时，发现标记后才能替换原来的元素。

寻找方式

在哈希表中查找下一个连续的空槽，将碰撞的键存入该槽中。

2）平方探查法：

类似于线性探查，但探查的步长是二次方，减少了聚集问题。

3）双散列法：

使用两个不同的哈希函数，第一次哈希决定初始位置，第二次哈希决定探查步长。

几种寻址方式本质原理都差不多，仅演示下线性探测过程：

再哈希法（双重哈希）

在出现碰撞时，使用第二个哈希函数计算新的索引位置，减少碰撞的概率

为什么 JDK 1.8 对 HashMap 进行了红黑树的改动？

在 JDK 1.8 之前，HashMap 使用链表来解决哈希冲突。当哈希冲突较多时，链表中的元素增多，查找、插入和删除的时间复杂度从 O(1) 退化为 O(n)。

因此在 JDK 1.8 引入红黑树，将链表长度超过一定阈值（默认 8）时的链表转换为红黑树，避免性能急剧下降。当链表长度降到 6 以下时，红黑树会重新退化为链表，保持简单高效。

红黑树是一种平衡二叉搜索树，插入、删除、查找操作的时间复杂度为 O(log n)，在元素多的情况下远优于链表的 O(n)。

链表与红黑树的转换时机

除了链表长度影响树化，实际上还与数组长度有关。

链表到红黑树的转换机制：

• 如果某个桶中的元素数量大于等于 8，且数组长度大于等于 64 时，链表转换为红黑树；
• 如果数组长度小于 64，则选择扩容而不是转换为红黑树。

binCount 从 0 开始计算，大于等于 7 则触发 treeifyBin（树化方法）：

treeifyBin 内还需判断数组的大小：

为什么数组要大于等于 64 才转红黑树？

主要原因有以下两点：

• 避免频繁的树化
• 减少内存占用

当数组容量较小的时候，哈希冲突大，但是扩容后的 HashMap 自然会减少哈希冲突。如果在小数组上过早地进行链表转红黑树，可能会因为很快的扩容导致不必要的树化开销。

刚树化了没多久就扩容了，冲突就少了，此时不就白白树化了？所以设计上设置了数组大小需要大于 64 才允许链表转为红黑树，防止频繁的树化。

红黑树相比链表需要更多的内存，尤其是在节点较少的情况下，红黑树的额外指针和结构占用更大。为了节省内存，HashMap 选择只有在数组容量达到一定规模后才树化，防止红黑树在小规模数据中带来额外的内存负担。

不能抛弃链表，直接使用红黑树吗？

来看下源码的注释:

因为红黑树节点的大小是普通节点大小的两倍，所以为了节省内存空间不会直接只用红黑树，只有当节点到达一定数量才会转成红黑树，这里定义的是 8。

为什么是 8 呢？这个其实 HashMap 注释上也有说，和泊松分布有关系。

简单翻译下就是在默认阈值是 0.75 的情况下，冲突节点长度为 8 的概率为 0.00000006，也就概率比较小（毕竟红黑树耗内存，且链表长度短点时遍历的还是很快的）。

这就是基于时间和空间的平衡了，红黑树占用内存大，所以节点少就不用红黑树，如果万一真的冲突很多，就用红黑树，选个参数为 8 的大小，就是为了平衡时间和空间的问题。

为什么节点小于等于 6 要从红黑树转成链表？

链表树化的节点是 8，除此之外，当树节点数小于等于 6 时候，又会从红黑树转为链表。

这个操作是为了平衡时间和空间，节点太少链表遍历也很快，没必要成红黑树，变成链表节约内存。

为什么定了 6 而不是小于等于 8 就变？

是因为要留个缓冲余地，避免反复横跳。举个例子，一个节点反复添加，从 8 变成 9 ，链表变红黑树，又删了，从 9 变成 8，又从红黑树变链表，再添加，又从链表变红黑树？

所以余一点，毕竟树化和反树化都是有开销的。

TreeMap 和红黑树

• 458. 什么是 Java 的 TreeMap？

JDK 1.8 对 HashMap 除了红黑树还进行了哪些改动？

• 改进了哈希函数的计算：JDK 1.8 中优化了哈希函数，使得哈希值的分布更加均匀，减少了哈希冲突的发生。通过在生成哈希值时使用“扰动函数”，确保哈希值的高低位都能参与到桶的选择中。
• 扩容机制优化：JDK 1.8 改进了扩容时的元素迁移机制。在扩容过程中不再对每个元素重新计算哈希值，而是根据原数组长度的高位来判断元素是留在原位置，还是迁移到新数组中的新位置。这一改动减少了不必要的计算，提升了扩容效率。
• 头插法变为尾插法：头插法的好处就是插入的时候不需要遍历链表，直接替换成头结点，但是缺点是扩容的时候会逆序，而逆序在多线程操作下可能会出现环，产生死循环，于是改为尾插法。

哈希函数的优化

1.7是这样实现的：

1
2
3
4

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

而 1.8 是这样实现的：

1
2
3
4

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

具体而言就是 1.7 的操作太多了，经历了四次异或，所以 1.8 优化了下，它将 key 的哈希码的高 16 位和低 16 位进行了异或，得到的 hash 值同时拥有了高位和低位的特性，使得哈希码的分布更均匀，不容易冲突。

这也是 JDK 开发者根据速度、实用性、哈希质量所做的权衡来做的实现：

扩容机制优化

• 451. Java 中 HashMap 的扩容机制是怎样的？

头插法和尾插法

1.7 是头插法，头插法的好处就是插入的时候不需要遍历链表，直接替换成头结点，但是缺点是扩容的时候会逆序，而逆序在多线程操作下可能会出现环，然后就死循环了。

然后 1.8 是尾插法，每次都从尾部插入的话，扩容后链表的顺序还是和之前一致，所以不可能出现多线程扩容成环的情况。

再延伸一下，改成尾插法之后 HashMap 就不会死循环了吗？

好像还是会，这次是红黑树的问题，我在网上看到这篇文章，有兴趣的可以深入了解下：

https://blog.csdn.net/qq_33330687/article/details/101479385

Java 中的 LinkedHashMap 是什么？

LinkedHashMap 是 Java 集合框架中的一个实现类，它继承自 HashMap，并且保留了键值对的插入顺序或访问顺序。

它内部是通过维护了一个双向链表来记录元素的插入顺序或访问顺序。

使用场景：

• 缓存实现：可以根据访问顺序移除最久未使用的元素，常用于 LRU（Least Recently Used）缓存。
• 数据存储：需要保持元素插入顺序的场景。

插入顺序或访问顺序

LinkedHashMap 提供了多个构造方法，包括默认构造方法和带有访问顺序选项的构造方法。通过指定 accessOrder 参数为 true，可以让 LinkedHashMap 以访问顺序排序，而不是插入顺序。

LinkedHashMap 内部实现剖析

LinkedHashMap 的父类是 HashMap，所以 HashMap 有的它都有，然后基于 HashMap 做了一些扩展。

首先它把 HashMap 的 Entry 加了两个指针：before 和 after。

这目的已经很明显了，就是要把塞入的 Entry 之间进行关联，串成双向链表，如下图红色的就是新增的两个指针：

并且内部还有个 accessOrder 成员，默认是 false， 代表链表是顺序是按插入顺序来排的，如果是 true 则会根据访问顺序来进行调整，就是咱们熟知的 LRU 那种，如果哪个节点访问了，就把它移到最后，代表最近访问的节点。

具体实现其实就是 HashMap 埋了几个方法，然后 LinkedHashMap 实现了这几个方法做了操作，比如以下这三个，从方法名就能看出了：访问节点之后干啥；插入节点之后干啥；删除节点之后干啥。

举个 afterNodeInsertion 的例子，它埋在 HashMap 的 put 里，在塞入新节点之后，会调用这个方法

然后 LinkedHashMap 实现了这个方法，可以看到这个方法主要用来移除最老的节点。

看到这你能想到啥？假如你想用 map 做个本地缓存，由于缓存的数量不可能无限大，所以你就能继承 LinkedHashMap 来实现，当节点超过一定数量的时候，在插入新节点的同时，移除最老最久没有被访问的节点，这样就实现了一个 LRU 了。

具体做法是把 accessOrder 设置为 true，这样每次访问节点就会把刚访问的节点移动到尾部，然后再重写 removeEldestEntry 方法，LinkedHashMap 默认的实现是直接返回 true。

你可以搞个：

1
2
3

protected boolean removeEldestEntry(Entry<K, V> eldest) {
      return this.size() > this.maxCacheSize;
}

这样就简单的实现一个 LRU 了！下面展示下完整的代码，非常简单：

1
2
3
4
5
6
7
8
9
10
11
12

private static final class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxCacheSize;

    LRUCache(int initialCapacity, int maxCacheSize) {
        super(initialCapacity, 0.75F, true);
        this.maxCacheSize = maxCacheSize;
    }

    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return this.size() > this.maxCacheSize;
    }
}

这里还能引申出一个笔试题，手写实现一个 LRU 算法，来我给你写！

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

public class LRUCache<K,V> {
    class Node<K,V> {
        K key;
        V value;
        Node<K,V> prev, next;
        public Node(){}
        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    private int capacity;
    private HashMap<K,Node> map;
    private Node<K,V> head;
    private Node<K,V> tail;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>(capacity);
        head = new Node<>();
        tail = new Node<>();
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        Node<K,V> node = map.get(key);
        if (node == null) {
            return null;
        }
        moveNodeToHead(node);
        return node.value;
    }

    public void put(K key, V value) {
         Node<K,V> node = map.get(key);
       if (node == null) {
            if (map.size() >= capacity) {
                map.remove(tail.prev.key);
                removeTailNode();
            }
            Node<K,V> newNode = new Node<>(key, value);
            map.put(key, newNode);
            addToHead(newNode);
        } else {
            node.value = value;
            moveNodeToHead(node);
        }
    }

    private void addToHead(Node<K,V> newNode) {
        newNode.prev = head;
        newNode.next = head.next;
        head.next.prev = newNode;
        head.next = newNode;
    }

    private void moveNodeToHead(Node<K,V> node) {
        removeNode(node);
        addToHead(node);
    }

    private void removeNode(Node<K,V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void removeTailNode() {
        removeNode(tail.prev);
    }

    public static void main(String[] args) {
        LRUCache<Integer,Integer> lruCache = new LRUCache<>(3);
        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.put(3,3);
        lruCache.get(1);
        lruCache.put(4,4);
        System.out.println(lruCache); // toString 我就没贴了，代码太长了
    }
}

Java 中的 TreeMap 是什么？

TreeMap 内部是通过红黑树实现的，可以让 key 实现 Comparable 接口或者自定义实现一个 comparator 传入构造函数，这样塞入的节点就会根据你定义的规则进行排序。

基本特性：

• 数据结构：TreeMap 基于红黑树实现，红黑树是一种自平衡的二叉查找树，能够保证基本操作（插入、删除、查找）的时间复杂度为 O(log n)。
• 键的有序性：TreeMap 中的键是有序的，默认按自然顺序（键的 Comparable 实现）排序，也可以通过构造时提供的 Comparator 进行自定义排序。
• 不允许 null 键：TreeMap 不允许键为 null，但允许值为 null。

这个用的比较少，常用在跟加密有关的时候，有些加密需要根据字母排序，然后再拼接成字符串排序，在这个时候就可以把业务上的值统一都塞到 TreeMap 里维护，取出来就是有序的。

简单使用示例

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

import java.util.Comparator;
import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        // 使用自然顺序
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(3, "Three");
        treeMap.put(1, "One");
        treeMap.put(2, "Two");
        System.out.println("TreeMap: " + treeMap);

        // 使用自定义比较器
        TreeMap<Integer, String> reverseTreeMap = new TreeMap<>(Comparator.reverseOrder());
        reverseTreeMap.put(3, "Three");
        reverseTreeMap.put(1, "One");
        reverseTreeMap.put(2, "Two");
        System.out.println("Reverse TreeMap: " + reverseTreeMap);

        // 获取子映射
        System.out.println("SubMap (1, 3): " + treeMap.subMap(1, 3));

        // 获取前缀映射
        System.out.println("HeadMap (2): " + treeMap.headMap(2));

        // 获取后缀映射
        System.out.println("TailMap (2): " + treeMap.tailMap(2));
    }
}

红黑树介绍

红黑树（Red-Black Tree）是一种自平衡二叉搜索树（Binary Search Tree，BST），它通过引入颜色（红色和黑色）标记每个节点，确保在最坏情况下的时间复杂度仍然是 O(log n)。红黑树常用于需要高效插入、删除和查找操作的场景，如 Java 中的 TreeMap 和 TreeSet，以及 Linux 内核中的虚拟内存管理。

它具有以下性质：

• 节点是红色或黑色。
• 根节点是黑色。
• 所有叶子节点（NIL 节点）是黑色。
• 红色节点的两个子节点都是黑色（从每个叶子到根的路径上不能有两个连续的红色节点）。
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些性质保证了红黑树的高度近似平衡，从而使得插入、删除、查找操作的时间复杂度保持在 O(log n)。

1）插入操作

• 插入的节点初始颜色总是红色。
• 插入后，可能违反红黑树的某些性质（例如，连续红色节点）。
• 为了恢复红黑树的平衡，可能需要通过旋转（左旋或右旋）和颜色调整来修复违反的性质。

2）删除操作

• 删除一个节点后，可能导致树不再平衡，需要通过调整颜色和旋转操作来恢复平衡。
• 可能会通过替换节点或合并节点的方式来处理删除操作。

3）旋转操作

旋转是红黑树的核心操作，用于恢复平衡：

• 左旋转：将某个节点的右子树提升为其父节点。
• 右旋转：将某个节点的左子树提升为其父节点。

红黑树的优点

• 平衡性：通过旋转和颜色调整，红黑树能够保持相对的平衡性，避免退化成链表，保证了查找、插入和删除操作的时间复杂度为 O(log n)。
• 灵活性：红黑树在插入和删除操作中相对于 AVL 树的调整操作较少，因此在需要频繁插入和删除的场景中性能更好。

关于红黑树动态渲染可以利用这个网站：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

Java 的 CopyOnWriteArrayList 和 Collections.synchronizedList 有什么区别？分别有什么优缺点？

CopyOnWriteArrayList：

是一个线程安全的 List 实现，特性就是写时复制。

每次对 List 的修改操作（如 add, set, remove）都会复制创建一个新的底层数组。读操作不需要加锁，写操作需要加锁。

优点：

• 读操作无锁：每次写操作都会创建并复制新数组，所以读写之间不冲突，因此读操作不需要加锁，能够提供非常高效的并发读性能。

缺点：

• 写操作开销大：每次写操作都会创建并复制新数组，且要将数据复制到新的数组中，在写操作频繁的场景下性能会较低。
• 内存消耗大：每次写操作都会创建并复制新数组，在数据量大的情况下，同一时刻会存在两倍 List 大小的内存占用，开销较大。

CopyOnWriteArrayList 适合读多写少的场景。

Collections.synchronizedList：

是一个包装方法，可以将任何 List 转换为线程安全的版本，它会对每个访问方法（如 get, set, add, remove）进行同步（加 synchronized 锁），从而保证线程安全。

优点：

• 方便：简单一个方法就可以将 List 变为线程安全版本，非常方便。

缺点：

• 并发低：读写操作都需要加锁，高并发场景下性能不高。

Collections.synchronizedList 适用于简单将 List 转为线程安全版本临时使用的场景。特定的场景还需使用并发度高的 JUC 类。

Java 中的 CopyOnWriteArrayList 是什么？

CopyOnWriteArrayList 是 Java 的一个线程安全的动态数组实现，属于 java.util.concurrent 包。

它通过写时复制机制，即在每次修改（写入）操作时，复制原始数组的内容来保证线程安全。

由于写操作涉及复制整个数组，所以它的写操作开销较大，但读取操作则完全无锁。这使得 CopyOnWriteArrayList 适合于读多写少的场景。

源码分析

我们来看一下 CopyOnWriteArrayList 的核心实现，写操作和读操作的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private transient volatile Object[] array;

    //写操作
    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();
        }
    }
    //读操作
    private E get(Object[] a, int index) {
        return (E) a[index];
    }
}

源码解读：

1）数组复制：

• 在 add 方法中，每次添加元素时，会加锁，首先创建了数组的副本 newElements，然后在这个副本中添加新元素。最后，将原数组 elements 替换为新副本 newElements。
• 这样，所有的读操作都是无锁的，因为它们只读数组 elements 的内容，而 elements 在读取时是稳定的。

2） 读操作：

• get 方法直接访问数组中的元素。这是线程安全的，因为数组在读操作期间不会被修改。

3）线程安全保证：

• 由于所有的写操作都涉及到创建新的数组副本，旧数组在写操作完成之前仍然可以被多个线程安全地读取。这样就避免了并发修改问题，确保线程安全。

写时复制（Copy-On-Write）

写时复制是一种保证数据一致性和线程安全的技术，核心思想是在进行写操作时，不直接修改原来的数据结构，而是先复制一份副本，在副本上进行修改，然后将修改后的副本替换原来的数据结构。

在 CopyOnWriteArrayList 中，底层数据结构是一个 volatile 修饰的数组，当对列表进行写操作时，操作步骤如下：

1）读取当前数组：

首先读取当前的数组，这个数组是 CopyOnWriteArrayList 当前持有的数组。

2）复制数组：

创建一个当前数组的副本（新的数组），这个副本会拷贝当前数组中的所有元素。

3）在副本上进行修改：

在副本数组上进行写操作（如添加、删除元素）。

4）用新数组替换旧数组：

将修改后的副本数组设置为 CopyOnWriteArrayList 持有的数组，旧数组将不再使用。

4）读操作读取最新数组：

所有读操作都可以无锁地直接读取 CopyOnWriteArrayList 当前持有的数组，因为这个数组在读操作期间不会被修改。

扩展 Redis 中的写时复制

• Redis 在生成 RDB 文件时如何处理请求？

数组和链表在 Java 中的区别是什么？

在存储结构方面：

数组基于连续的内存块，大小是固定的，需要重新分配内存来改变数组大小，内存使用紧凑但容易浪费空间。

链表是基于节点的结构，在内存中不需要连续存储，可以动态变化大小和插入删除节点，内存不连续但可以动态扩展。

在访问速度方面：

数组支持 O(1) 时间的随机访问，可以通过索引直接访问任何元素。

1
2
3
4
5
6

+----+----+----+----+----+----+
| 10 | 20 | 30 | 40 | 50 | 60 |
+----+----+----+----+----+----+
^
|
Index

而链表访问特定元素需要线性时间O(n)，因为节点在内存中不一定连续，访问效率受限于链表的结构。

1
2
3
4
5
6
7
8
9

Head
 |
 v
+----+----+     +----+----+     +----+----+
| 10 | *----> | 20 | *----> | 30 | *----> NULL
+----+----+     +----+----+     +----+----+
     ^               ^               ^
     |               |               |
   Node             Node             Node

在操作方面：

数组插入和删除需要移动数据，时间复杂度为 O(n)，而链表则很灵活，可在 O(1) 时间插入和修改指定位置元素。

在适用场景方面：

数组适合需要快速随机访问且大小固定的场景，如实现缓存、表格等数据结构。

链表适合需要频繁插入和删除操作且大小不确定的场景，如队列、栈、链表等

拓展

数组的内存是连续的，且存储的元素大小是固定的，实现上是基于一个内存地址，然后由于元素固定大小，支持利用下标的直接访问。

具体是通过下标 * 元素大小+内存基地址算出一个访问地址，然后直接访问，所以随机访问的效率很高，O(1)。

而由于要保持内存连续这个特性，不能在内存中间空一块，所以删除中间元素时就需要搬迁元素，需进行内存拷贝，所以说删除的效率不高。

链表的内存不需要连续，它们是通过指针相连，这样对内存的要求没那么高（数组的申请需要一块连续的内存），链表就可以散装内存，不过链表需要额外存储指针，所以总体来说，链表的占用内存会大一些。

且由于是指针相连，所以直接无法随机访问一个元素，必须从头（如双向链表，可尾部）开始遍历，所以随机查找的效率不高，O(n)。

也由于指针相连这个特性，单方面删除的效率高，因为只需要改变指针即可，没有额外的内存拷贝动作(但是要找到这个元素，费劲儿呀，除非你顺序遍历删)。

两者大致的特点就如上所说，再扯地深一点，就要说到 CPU 亲和性问题

这里可以延展到空间局部性。

空间局部性（spatial locality）：如果一个存储器的位置被引用，那么将来它附近的位置也会被引用。

根据这个原理，就会有预读功能，像 CPU 缓存就会读连续的内存，这样一来如果你本就要遍历数组的，那么你后面的数据就已经被上一次读取前面数据的时候，一块被加载了，这样就是 CPU 亲和性高。

反观链表，由于内存不连续，所以预读不到，所以 CPU 亲和性低。

对了，链表（数组）加了点约束的话，还可以用作栈、队列和双向队列。

像 LinkedList 就可以用来作为栈或者队列使用。

Java 中的 IdentityHashMap 是什么？

IdentityHashMap 是 Java 中的一个 Map 实现，和普通的 HashMap 不同，它使用 引用相等性（reference equality） 作为键的比较方式。换句话说，它使用 == 来比较键值，而不是 equals() 方法。因此，只有当两个键的引用相同时，才被认为是相同的键。

使用场景：

• 对象身份区分：适用于需要基于对象身份（引用）进行区分的场景，比如需要跟踪对象实例，而不是逻辑上的值相等性。
• 特殊缓存：有时用于构建缓存或映射结构，确保即使两个对象内容相同，但只要它们是不同的实例，就会被当作不同的键。

主要特性总结：

• 引用相等：IdentityHashMap 使用 == 比较键的相等性，而不是通过 equals()，这使得它适合那些需要基于对象身份（引用）的场景。
• 哈希实现：虽然名字中有 “Hash”，但 IdentityHashMap 并不使用对象的 hashCode() 方法，而是依赖 System.identityHashCode()，这是基于对象引用的哈希值。
• 允许 null 键和 null 值：类似 HashMap，IdentityHashMap 也允许 null 键和 null 值，但它使用的是对 null 的引用比较。
• 非线程安全：与 HashMap 类似，IdentityHashMap 不是线程安全的，在多线程环境下需要手动同步。

IdentityHashMap 源码分析

首先看它覆盖的 hash 方法：

可以看到，它用了个 System.identityHashCode(x)，而不是 x.hashCode()。

而这个方法会返回原来默认的 hashCode 实现，不管对象是否重写了 hashCode 方法

默认的实现返回的值是：对象的内存地址转化成整数，是不是有点感觉了？

然后我们再看下它的 get 方法：

可以看到，它判断 key 是否相等并不靠 hash 值和 equals，而是直接用了 == 。

而 == 其实就是地址判断！

只有相同的对象进行 == 才会返回 true。

因此我们得知，IdentityHashMap 的中的 key 只认它自己（对象本身）。

即便你伪造个对象，就算值都相等也没用，put 进去 IdentityHashMap 只会多一个键值对，而不是替换，这就是 Identity 的含义。

比如以下代码，identityHashMap 会存在两个 Yes：

1
2
3

Map<String, String> identityHashMap = new IdentityHashMap<>();
identityHashMap.put(new Yes("1"), "1");
identityHashMap.put(new Yes("1"), "2");

这里眼尖的小伙伴发现代码里，为什么返回值是 tab[i+1]？

这是因为 IdentityHashMap 的存储方式有点不一样，它是将 value 存在 key 的后面。

认识到这就差不多了。它是一个非常特殊和有限用途的映射实现，主要用于需要引用相等性的场景。在一些框架中，代理对象可能需要根据实际对象实例进行映射，而不是逻辑相等的对象，这时候 IdentityHashMap 就派上用场了。

Java 中 ConcurrentHashMap 1.7 和 1.8 之间有哪些区别？

JDK 1.7 ConcurrentHashMap 采用的是分段锁，即每个 Segment 是独立的，可以并发访问不同的 Segment，默认是 16 个 Segment，所以最多有 16 个线程可以并发执行。

而 JDK 1.8 移除了 Segment，锁的粒度变得更加细化，锁只在链表或红黑树的节点级别上进行。通过 CAS 进行插入操作，只有在更新链表或红黑树时才使用 synchronized，并且只锁住链表或树的头节点，进一步减少了锁的竞争，并发度大大增加。

并且 JDK 1.7 ConcurrentHashMap 只使用了数组 + 链表的结构，而 JDK 1.8 和 HashMap一样引入了红黑树。

除此之外，还有扩容的区别以及 size 方法的计算也不一样。

ConcurrentHashMap 1.7 简单图解

我们来看下大致的结构。

原理就是先通过 key 的 hash 判断得到 Segment 数组的下标，将这个 Segment 上锁，然后再次通过 key 的 hash 得到 Segment 里 HashEntry 数组的下标，下面这步其实就是 HashMap 一致了，所以我说差别就是引入了一个 Segments 数组。

因此可以简化的这样理解：每个 Segment 数组存放的就是一个单独的 HashMap。

可以看到，图上我们有 6 个 Segment，那么等于有六把锁，因此共可以有六个线程同时操作这个 ConcurrentHashMap，并发度就是 6，相比于直接将 put 方法上锁，并发度就提高了，这就是分段锁。

具体上锁的方式来源于 Segment，这个类实际继承了 ReentrantLock，因此它自身具备加锁的功能。

可以看出，1.7 的分段锁已经有了细化锁粒度的概念，它的一个缺陷是 Segment 数组一旦初始化了之后不会扩容，只有 HashEntry 数组会扩容，这就导致并发度过于死板，不能随着数据的增加而提高并发度。

ConcurrentHashMap 1.8 简单图解

1.8 ConcurrentHashMap 做了更细粒度的锁控制，可以理解为 1.8 HashMap 的数组的每个位置都是一把锁，这样扩容了锁也会变多，并发度也会增加。

思想的转变就是把粒度更加细化。不分段了，我直接把 Node 数组的每个节点分别上一把锁，这样并发度不就更高了吗？

并且 1.8 也不借助于 ReentrantLock 了，直接用 synchronized，这也侧面证明，都 1.8 了 synchronized 优化后的速度已经不下于 ReentrantLock 了。

具体实现思路也简单：当塞入一个值的时候，先计算 key 的 hash 后的下标，如果计算到的下标还未有 Node，那么就通过 cas 塞入新的 Node。如果已经有 node 则通过 synchronized 将这个 node 上锁，这样别的线程就无法访问这个 node 及其之后的所有节点。

然后判断 key 是否相等，相等则是替换 value ，反之则是新增一个 node，这个操作和 HashMap 是一样的。

扩容的区别

JDK 1.7 中的扩容：

• 基于 Segment：ConcurrentHashMap 是由多个 Segment 组成的，每个 Segment 中包含一个 HashMap。当某个 Segment 内的 HashMap 达到扩容阈值时，单独为该 Segment 进行扩容，而不会影响其他 Segment。
• 扩容过程：每个 Segment 维护自己的负载因子，当 Segment 中的元素数量超过阈值时，该 Segment 的 HashMap 会扩容，整体的 ConcurrentHashMap 并不是一次性全部扩容。

JDK 1.8 中的扩容：

• 全局扩容：ConcurrentHashMap 取消了 Segment，变成了一个全局的数组（类似于 HashMap）。因此，当 ConcurrentHashMap 中任意位置的元素超过阈值时，整个 ConcurrentHashMap 的数组都会被扩容。
• 基于 CAS 的扩容：在扩容时，ConcurrentHashMap 采用了类似 HashMap 的方式，但通过CAS 操作确保线程安全，避免了锁住整个数组。在扩容时，多个线程可以同时帮助完成扩容操作。
• 渐进式扩容：JDK 1.8 的 ConcurrentHashMap 引入了渐进式扩容机制，扩容时并不是一次性将所有数据重新分配，而是多个线程共同参与，逐步迁移旧数据到新数组中，降低了扩容时的性能开销。

渐进式扩容分析

当 put 的时候，发现当前 node hash 值是 -1，则表明当前的节点正在扩容，则会触发协助扩容机制：

其实大家大致理解下就够了：

扩容无非就是搬迁 Node，假设当前数组长度为 32，那就可以分着搬迁，31-16 这几个下标的 Node 都由线程 A 来搬迁，然后线程 B 来搬迁 15-0 这几个下标的 Node。

简单说就是会维护一个 transferIndex 变量，来的线程死循环 cas 争抢下标，如果下标已经分配完了，那自然就不需要搬迁了，如果 cas 抢到了要搬运的下标，那就去帮忙搬就好了，就是这么个事儿。

size 逻辑的区别

1.7 有个尝试的思想，当调用 size 方法的时候不会加锁，而是先尝试三次不加锁获取 sum。

如果三次总数一样，说明当前数量没有变化，那就直接返回了。如果总数不一样，那说明此时有线程在增删 map，于是加锁计算，这时候其他线程就操作不了 map 了。

1
2
3
4
5

if (retries++ == RETRIES_BEFORE_LOCK) {
       for (int j = 0; j < segments.length; ++j)
           ensureSegment(j).lock(); // force creation
}
   ...再累加数量

而 1.8 不一样，它就是直接计算返回结果，具体采用的是类似 LongAdder 的思想，累加不再是基于一个成员变量，而是搞了一个数组，每个线程在自己对应的下标地方进行累加，等最后的时候把数组里面的数据统一一下，就是最终的值了。

所以这是一个分解的思想，分而治之。

在 put 的时候，就会通过 addCount 方法维护 counterCells 的数量，当然 remove 的时候也会调用此方法。

总而言之，就是平日的操作会维护 map 里面的节点数量，会先通过 CAS 修改 baseCount ，如果成功就直接返回，如果失败说明此时有线程在竞争，那么就通过 hash 选择一个 CounterCell 对象就行修改，最终 size 的结果就是 baseCount + 所有 CounterCell 。

这种通过 counterCell 数组来减少并发下场景下对单个成员变量的竞争压力，提高了并发度，提升了性能，这也就是 LongAdder 的思想。

CAS

• 500. 什么是 Java 的 CAS（Compare-And-Swap）操作？

Java 中 ConcurrentHashMap 的 get 方法是否需要加锁？

不需要加锁。

通过 volatile 关键字，ConcurrentHashMap 能够确保 get 方法的线程安全，即使在写入发生时，读取线程仍然能够获得最新的数据，不会引发并发问题。

具体是通过Unsafe#getXXXVolatile 和用 volatile 来修饰节点的 val 和 next 指针来实现的。

写时加锁：

写操作如 put 和 remove 需要加锁，以确保写入时的线程安全性和一致性，但 get 操作不需要锁。通过这种方式，ConcurrentHashMap 实现了高效的读写分离，读操作不会阻塞写操作，从而提高了并发性能。

ConcurrentHashMap#get 方法源码分析

主要的定位逻辑在 e = tabAt(tab, (n - 1) & h)) != null 这行。

而 tabAt 内部使用的就是Unsafe#getObjectVolatile来保证可见性。

getObjectVolatile 实际是一个 native 方法，即本地方法，通过 JNI（Java Native Interface）调用底层的 C++ 实现。

它的原理就是根据对象的起始地址和字段的偏移量，直接从内存中读取字段的值。然后通过内存屏障确保该读取操作是 volatile 的，即对于其他线程是可见的。

所谓的内存屏障指的是 getObjectVolatile 方法会确保在读取操作之前插入一个读取屏障（load barrier），在读取操作之后插入一个读取屏障（load barrier）。这保证了字段的值在读取之前和之后都不会被 CPU 缓存，从而实现了 volatile 的语义。

因此，不需要加锁，利用 Unsafe 获取元素，再对比 hash 值以及 key 即可获取 value（这个流程就是普通的 map 的 get 流程，这里不再赘述）。

然后 Node 节点内的 val 和 next 指针也是被 volatile 修饰的，因此也可以保证可见性。

综上，不论是通过 hash 映射到数组中具体的 node 节点，还是因为 hash 冲突可能需要利用 next 指针遍历链表，定位到最终的 node 节点后需要获取 val 值，这几个关键点都可以保证可见性，因此不需要加锁。

Unsafe

Unsafe 类是 Java 提供的一个内部类，用于执行不安全的操作（从名字就可以看出来了）。它提供了直接操作内存和线程的能力。

列举 Unsafe 类的一些关键功能：

• 直接内存访问：允许直接分配、释放、读写内存。
• 对象操作：允许直接操作对象的字段，如设置或获取对象的字段值。
• 线程操作：包括暂停和恢复线程、管理锁等。
• CAS 操作：提供了 compare-and-swap 操作，支持原子性更新操作。

为什么 Java 的 ConcurrentHashMap 不支持 key 或 value 为 null？

为了避免混淆和潜在的并发问题。

ConcurrentHashMap 是为并发环境设计的，在并发访问时，如果允许 key 或 value 为 null，可能导致不可预知的行为和错误。例如，在使用 get(key) 时，如果返回值为 null，无法区分是 key 不存在，还是 value 实际上是 null。因此，为了避免这种歧义，ConcurrentHashMap 不允许 null 值。

为了简化实现。

如果 key 或 value 允许为 null，会给诸如 put、get、containsKey 等操作带来复杂性。例如，get 操作可能会频繁返回 null，需要额外的逻辑去区分是否是因为 key 不存在，还是 value 为 null。

如果允许 null，在并发修改或删除操作时，也可能导致多线程下不一致的状态，增加调试和维护的难度。

其他并发集合的做法

Java 中的其他并发集合如 CopyOnWriteArrayList 和 ConcurrentSkipListMap 也不允许 null。这些设计一致性也是为了防止并发操作中的空值带来的潜在问题，特别是在高并发环境下，维护简洁和可预期的行为。

源码查看

ConcurrentHashMap 中，任何 put 或 get 操作都会对 key 和 value 进行空值校验。如果尝试插入 null，会抛出 NullPointerException。让我们来看看 ConcurrentHashMap 的部分源码（基于 JDK 1.8）：

1
2
3
4

public V put(K key, V value) {
    if (key == null || value == null) throw new NullPointerException();
    return putVal(key, value, false);
}

源码解读：

1. 在 put 方法中，首先检查 key 和 value 是否为 null，如果是，则直接抛出 NullPointerException。
2. 这个 null 检查是为了确保后续操作不会因为 null 而引发不可预知的错误。

再看看 get 方法：

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

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

源码解读：

1. 在 get 方法中，null 值的检查并不是为判断 value 是否为 null 而设计的，而是确保 key 不为 null。因此，内部逻辑专注于如何通过 hash 定位桶，并找到对应的 key。
2. 由于 ConcurrentHashMap 不支持 null，get 操作返回的 null 只能表明该 key 不存在，而不是 value 是 null，从而避免了潜在的混淆。

你遇到过 ConcurrentModificationException 错误吗？它是如何产生的？

它通常在集合被遍历时出现修改操作时抛出，是一个 fail-fast 机制。

ConcurrentModificationException 是 Java 中的一种运行时异常，这个错误是为了检测并发修改的行为，在非线程安全的集合中，并发修改集合数据可能会发生数据丢失等一些奇怪的问题。

因此 Java 引入了这个错误，是为了保证集合迭代时语义的一致性。

原理

它的原理是在集合内部维护了一个修改次数的记录，即 Iterator 的 modCount 变量。如果发生了修改，那么这个次数会增加，即 modCount 也会改变。在每次迭代的时候会检查这个次数，如果发现 modCount 与 expectedModCount不匹配，则会抛出 ConcurrentModificationException

以 ArrayList 为例分析

ArrayList 的 modCount 变量记录了集合的修改次数。在 Iterator 的 next() 方法中，会检查当前的 modCount 是否与 expectedModCount 相同，如果不相同，则抛出 ConcurrentModificationException。

示例源码（ArrayList 的 modCount 机制）：

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

public class ArrayList<E> extends AbstractList<E> implements List<E> {
    transient int modCount = 0;
    
    public Iterator<E> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<E> {
        private int cursor; // 当前游标位置
        private int expectedModCount = modCount; // 预期的修改次数
        
        public boolean hasNext() {
            checkForComodification();
            return cursor != size;
        }
        
        public E next() {
            checkForComodification();
            return ArrayList.this.get(cursor++); // 获取当前元素并移动游标
        }
        
        final void checkForComodification() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
        }
    }
}

源码解读：

• modCount 记录了集合的修改次数，而 expectedModCount 记录了迭代器创建时的修改次数。
• 每次调用 next() 方法时，checkForComodification() 会检查当前的 modCount 是否与 expectedModCount 相同。如果不同，说明集合在遍历过程中被修改过，因此抛出 ConcurrentModificationException。

解决方案：

• 使用 Iterator 的 remove 方法：使用 Iterator 进行遍历时，调用 Iterator 的 remove 方法来删除元素是安全的。
• 使用线程安全的集合：对于多线程环境，可以选择线程安全的集合，如 ConcurrentHashMap、CopyOnWriteArrayList 等，它们能够在并发操作时提供一致性。
• 同步控制：对于需要在多线程环境中进行修改的集合，可以使用外部同步来确保一致性。例如，可以使用 synchronizedList 包装一个 ArrayList。

Iterator remove 示例

如果单线程在一个循环中遍历集合的同时直接修改集合也会报这个错，可以通过 Iterator 进行遍历，并使用 Iterator 提供的 remove 方法来删除元素，可以避免 ConcurrentModificationException。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ConcurrentModificationExceptionExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");

        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String s = iterator.next();
            if (s.equals("A")) {
                iterator.remove();  // 正确的删除方式
            }
        }

        System.out.println(list);  // 输出: [B, C]
    }
}

什么是 Fail-fast？

Fail-fast 是一种程序设计理念，指的是在程序执行过程中，如果遇到错误或异常状态，系统会立即停止或抛出异常，而不是继续执行下去。

通过这种机制，程序可以在问题发生的初期阶段迅速暴露出潜在的错误，避免在后续的操作中引发更严重的问题或导致数据不一致。

Java 中的 WeakHashMap 是什么 ？

WeakHashMap 是 Java 中的一个特殊的 Map 实现，它使用弱引用（Weak Reference） 作为键。弱引用允许垃圾回收器在没有其他强引用指向该对象时回收它的内存。因此，当一个键不再被其他对象引用时，WeakHashMap 会自动删除与该键相关联的条目。

常用于缓存（内存敏感场景）的实现。当缓存中的键不再被其他地方引用时，可以自动移除相应的缓存条目，节省内存，防止内存泄漏。

Java 中的强引用、软引用、弱引用和虚引用

• 532.Java 中的强引用、软引用、弱引用和虚引用分别是什么？

WeakHashMap 的实际应用：

• 动态代理缓存：Java 的动态代理生成过程中可能会生成多个代理类实例，而这些实例在不再使用时可能会浪费内存。WeakHashMap 可以用于缓存这些代理类，确保当代理类不再被引用时，它们可以被及时回收。
• Event Listener 管理：某些事件监听器（Listener）模式中，可能需要根据对象的生命周期动态添加和移除监听器，WeakHashMap 可以用于管理这些监听器，确保当监听器对象不再使用时，它们会自动被移除，避免内存泄漏。