Java面试题汇总——Java集合框架中的面试题

List

Collections 和 Collection 的区别

Collection 是 Java 集合框架中的顶级接口。它定义了一组通用的操作和方法，如添加、删除、遍历等，用于操作和管理一组对象。Collection 接口有许多实现类，如 List、Set 和 Queue 等。

Collections（注意有一个s）是Java提供的一个工具类，位于 java.util 包中。它提供了一系列静态方法，用于对集合进行操作和算法。Collections 类中的方法包括排序、查找、替换、反转、随机化等等。这些方法可以对实现了 Collection 接口的集合进行操作，如 List 和 Set。

说说 List 和 Set 的区别是什么？

List是有序、可重复的集合，核心是按索引下标访问，保留了元素的插入顺序

Set是无序（部分有序）、不可重复的集合，核心是保持元素的唯一性和去重

特性	List	Set
元素重复性	允许重复元素	不允许重复元素（依赖`equals()`和`hashCode()`判断）
有序性	元素有「插入顺序 / 访问顺序」，支持下标随机访问	多数实现无序（如 HashSet）；少数有序（如 TreeSet 按自然序、LinkedHashSet 按插入序）
索引访问	支持（get (int index)）	不支持索引访问（无 get (index) 方法）
核心实现类	ArrayList、LinkedList、Vector	HashSet、TreeSet、LinkedHashSet
判重逻辑	无判重逻辑，插入即保留	HashSet：通过 hashCode+equals 判重；TreeSet：通过 Comparator/Comparable 判重
底层数据结构	ArrayList（数组）、LinkedList（双向链表）	HashSet（哈希表 / HashMap）、TreeSet（红黑树）、LinkedHashSet（哈希表 + 链表）

对于它们的有序性多说一句

Set 的无序 ≠ 随机：HashSet 中元素的存储顺序由哈希值决定，看似无序，而 LinkedHashSet，基于链表维护插入顺序，他有序，TreeSet 更不用说了，基于红黑树按自然顺序排序

List 的有序：无论 ArrayList 还是 LinkedList，都严格保留元素的插入顺序，能通过索引精准获取 / 修改元素。

说说 List 和 Queue 的区别呢？

Queue 的设计定位是队列，遵循 FIFO 核心规则，和 List 的自由存取有本质区别。

特性	List	Queue
核心规则	无固定存取规则，可随机访问、任意位置增删	遵循 FIFO（先进先出），部分实现支持优先级（`PriorityQueue`）
存取方式	基于索引`get/set/add (int index)`	基于队列首尾`offer/poll/peek` 等，无索引操作
空值支持	允许存储 null（如 `ArrayList`、`LinkedList`）	多数实现不允许 null（如 `ArrayDeque`、`PriorityQueue`），避免和队列为空混淆
核心实现类	`ArrayList`、`LinkedList`	`LinkedList`（同时实现 `List` 和 `Queue`）、`ArrayDeque`、`PriorityQueue`
异常处理	索引越界抛 `IndexOutOfBoundsException`	队列空时：`remove ()` 抛 `NoSuchElementException`，`poll ()` 返回 `null`；队列满时：`add ()` 抛 `IllegalStateException`，`offer ()` 返回 `false`

LinkedList 同时实现了 List 和 Queue 接口，所以它既可以当 List 用（索引访问），也可以当 Queue 用（offer/poll），但实际开发中如果用队列特性，建议声明为 Queue 类型（Queue<String> queue = new LinkedList<>()），语义更清晰。

注意，PriorityQueue优先队列不一定是 FIFO，因为它按元素优先级排序，队首是优先级最高的元素。

所以说，两者的使用场景也不一样

List：需要随机访问、任意位置修改的列表
Queue：需要按顺序处理任务

ArrayList 和 Array（数组）的区别

首先，ArrayList 是实现了 List 接口的一个容器类，可以动态地调整大小，它内部使用数组来存储元素；数组 Array 是 Java 语言内置的一个原生数据结构，用于存储相同类型的多个元素。它在内存中分配一块连续的空间来存储元素，通过索引访问每个元素。

由于 ArrayList 可以动态调整大小，因此非常适合在运行时添加、删除或修改元素的情况下使用，它还提供了一组方便的 API 来处理集合数据。而当我们提到Array 的时候，通常认为它是具有固定长度的，适用于已知元素数量且不会改变的情况，创建它通常需要指定大小，而且认为它只提供索引访问的能力，不具备动态添加、删除元素的能力，需依赖 java.util.Arrays 工具类

ArrayList 可以存储任何类型的对象，但是只能存储对象，包括基本数据类型的包装类和其他引用类；数组 Array 既可以存储基本类型数据，也可以存储对象。

ArrayList 允许使用泛型来确保类型安全，Array 则不可以。而且对于类型安全，ArrayList是编译期间使用泛型检查，Array 是运行时类型检查。

而且对于基本类型的存储 Array 比 ArrayList<Integer> 快很多

ArrayList 可以添加 null 值吗?

ArrayList 中可以存储任何类型的对象，包括 null 值。不过，不建议向ArrayList 中添加 null 值， null 值无意义，会让代码难以维护比如忘记做判空处理就会导致空指针异常。

通常情况下，面对可能出现存储 null 的容器，我们都使用 Optional 来优雅的处理可能存在的 null，来避免在服务运行时候出现 NPE 的情况

ArrayList 插入和删除元素的时间复杂度？

对于插入：

头部插入：由于需要将所有元素都依次向后移动一个位置，因此时间复杂度是 O(n)。
尾部插入：当 ArrayList 的容量未达到极限时，往列表末尾插入元素的时间复杂度是 O(1)，因为它只需要在数组末尾添加一个元素即可；当容量已达到极限并且需要扩容时，则需要执行一次 O(n) 的操作将原数组复制到新的更大的数组中，然后再执行 O(1) 的操作添加元素。
指定位置插入：需要将目标位置之后的所有元素都向后移动一个位置，然后再把新元素放入指定位置。这个过程需要移动平均 n/2 个元素，因此时间复杂度为 O(n)。

对于删除：

头部删除：由于需要将所有元素依次向前移动一个位置，因此时间复杂度是 O(n)。
尾部删除：当删除的元素位于列表末尾时，时间复杂度为 O(1)。
指定位置删除：需要将目标元素之后的所有元素向前移动一个位置以填补被删除的空白位置，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。

LinkedList 插入和删除元素的时间复杂度？

头部插入/删除：只需要修改头结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。

尾部插入/删除：只需要修改尾结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。

指定位置插入/删除：需要先移动到指定位置，再修改指定节点的指针完成插入/删除，不过由于有头尾指针，可以从较近的指针出发，因此需要遍历平均 n/4 个元素，时间复杂度为 O(n)。

ArrayList 与 LinkedList 区别?

底层数据结构： ArrayList 底层使用的是 Object动态数组；LinkedList 底层使用的是 双向链表 数据结构。
插入和删除是否受元素位置的影响：
- ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)），时间复杂度就为 O(n)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的 (n-i) 个元素都要执行向后位/向前移一位的操作。
- LinkedList 采用链表存储，所以在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst()、 removeLast()），时间复杂度为 O(1)，如果是要在指定位置 i 插入和删除元素的话（add(int index, E element)，remove(Object o),remove(int index)），时间复杂度为 O(n) ，因为需要先移动到指定位置再插入和删除。
是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，需要顺着链表遍历，所以是O(n)访问，而 ArrayList（实现了 RandomAccess 接口）支持O(1)按照下标访问。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
内存空间占用：这里分两点说
- ArrayList 因为动态数组的底层结构所以使用的是连续的内存空间，LinkedList因为使用链表而。
- ArrayList 的空间浪费主要体现每个元素存储的对象引用，而 LinkedList 的空间花费则为链表的前后指针和数据对象引用，LinkedList存储每一个元素都需要消耗比 ArrayList 更多的空间，内存开销差很多。

所以说最后，它们的区别诞生了它们在不同的应用场景下使用他们，ArrayList 适合使用读多写少的常见， LinkedList 适合于头尾插入删除多的场景，因为LinkedList 其他情况增删元素的平均时间复杂度都是 O(n)

实际开发中，90% 以上的场景都该用 ArrayList，因为现代 CPU 对连续内存的缓存命中率远高于链表这种跳来跳去的结构。

说一说 ArrayList 的扩容机制吧，还有LinkedList为什么不需要扩容

首先，ArrayList 扩容是因为 ArrayList 底层是基于 Object[] 数组实现的动态数组，而 ArrayList 要支持动态增长，元素塞满了就得扩容。创建更大的新数组，并将旧数据复制过去，这就是扩容的本质。

具体就是当执行 add(E e) 这种添加元素的操作时，如果当前元素数量（size）加 1 超过了底层数组 elementData 的长度（即 capacity），就会触发扩容。

若使用无参构造器时，那么ArrayList的初始容量不是10，根据elementData，ArrayList初始是一个空数组{}，首次添加元素时才扩容到 10。

后续扩容策略是新容量 = 旧容量 + (旧容量 >> 1)，即 1.5 倍扩容，这是最佳扩容大小，而 ArrayList 会计算一个最小扩容大小，也就是扩容的目标大小 - 当前空间 = 最小扩容空间，如果最小扩容大小大于了最佳扩容大小，ArrayList 会选择最小扩容大小。

选 1.5 倍是时间和空间的折中。2 倍扩容次数少但太浪费内存，1.5 倍既能减少扩容次数，又不会让内存利用率太低。另外有个有意思的点：1.5 倍扩容时，老数组释放后的内存加上一些零碎空间，往往刚好能容纳新数组，减少内存碎片。

扩容是创建了一个更大的新数组，调用 Arrays.copyOf() 把老数据拷过去，修改elementData的引用指向新数组，不是原地变大。所以说扩容的时间空间开销也是比较大的，实际开发中尽量预估数据量然后避免大量扩容。

LinkedList 不需要扩容的根本原因是 LinkedList 底层是双向链表，不是连续内存结构，此时，内存是按需动态分配的。因此，LinkedList 没有“容量”概念，也不存在“扩容”操作

所以，ArrayList 的扩容是为了在连续内存限制下模拟动态增长，而 LinkedList 天然具备动态性，因为它基于链式存储，内存可以不连续

集合中的 fail-fast 和 fail-safe 是什么？

fail-fast（快速失败）和 fail-safe（安全失败）是Java集合框架在处理并发修改问题时，两种截然不同的设计哲学和容错策略。

快速失败的思想即针对可能发生的异常进行提前表明故障并停止运行，通过尽早的发现和停止错误，降低故障系统级联的风险。

在java.util包下的大部分集合（如 ArrayList, HashMap）是不支持线程安全的，为了能够提前发现并发操作导致线程安全风险，提出通过维护一个modCount记录修改的次数，迭代期间通过比对预期修改次数expectedModCount和modCount是否一致来判断是否存在并发操作，从而实现快速失败，由此保证在避免在异常时执行非必要的复杂代码。

而fail-safe也就是安全失败的含义，它旨在即使面对意外情况也能恢复并继续运行，这使得它特别适用于不确定或者不稳定的环境：

该思想常运用于并发容器，最经典的实现就是CopyOnWriteArrayList的实现，通过写时复制（Copy-On-Write）的思想保证在进行修改操作时复制出一份快照，基于这份快照完成添加或者删除操作后，将CopyOnWriteArrayList底层的数组引用指向这个新的数组空间，由此避免迭代时被并发修改所干扰所导致并发操作安全问题，当然这种做法也存在缺点，即进行遍历操作时无法获得实时结果

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

两者都是线程安全的 List，但是思路完全不一样

一个是使用 JUC 并发包里的并发容器，靠COW写时复制保持线程安全，读时无锁，但是因此写入时双倍内存，因此适合读多写少的场景。迭代CopyOnWriteArrayList是快照迭代，不抛异常。

Collections.synchronizedList靠的是代理模式，直接给原来的 List 中的每个方法都加synchrorized锁来保证线程安全，读写都要抢同一把锁，读写互斥，并发性能很差。而且迭代需要手动加锁。

你忘了 Stack 是怎么被废弃掉的了？

Java 中的 CopyOnWriteArrayList 是什么？它的靠什么机制保证的线程安全？

CopyOnWriteArrayList 是 JUC 包下的一个线程安全的 List 实现，核心机制是写时复制：每次写操作都会复制一份新数组，在新数组上修改，然后修改引用指向新数组来替换旧数组。

这样写时复制就实现了读写分离，读操作肯定是线程安全的，顶多可能读到旧的数据，写操作在副本上改，改完再替换。这样读和写之间就不会互相阻塞。

写时复制是有性能问题的，旧数组要等没有线程引用才能被 GC 回收，这个过程相对不稳定，所以如果写操作很频繁，内存里会同时存在多个数组副本，容易频繁 GC 或者直接 OOM

所以数据量大或写入频繁的场景就不应该用 CopyOnWriteArrayList

所以写操作开销很大，因为要复制整个数组；但读操作完全无锁，直接读数组就行。所以它适合读多写少的场景，比如配置列表、监听器列表这种写入频率低但读取频繁的数据。

CopyOnWriteArrayList 的迭代器遍历的是创建迭代器那一刻的数组快照，遍历过程中其他线程的写操作不会影响迭代，也不会抛 ConcurrentModificationException，但是数据是弱一致性的，而且也不能 remove()

Set

有一个学生类，想按照分数排序，再按学号排序，应该怎么做？Comparable 和 Comparator 的区别？

可以使用Comparable接口来实现按照分数排序，再按照学号排序。

首先在学生类中实现 Comparable 接口，并重写compareTo方法，然后类内部的compareTo方法中实现按照分数排序和按照学号排序的逻辑。

public class Student implements Comparable<Student> {
    private int id;
    private int score;

    // 构造方法和其他属性、方法省略

    @Override
    public int compareTo(Student other) {
        if (this.score != other.score) {
            return Integer.compare(other.score, this.score); // 按照分数降序排序
        } else {
            return Integer.compare(this.id, other.id); // 如果分数相同，则按照学号升序排序
        }
    }
}

// 用到的时候直接用就可以
List<Student> students = new ArrayList<>();
Collections.sort(students);

Comparator 是外部比较器，无需修改 Student 类，通过自定义 Comparator 实现排序规则，更灵活，可以用匿名内部类或者 Lambda 表达式来写

// 匿名内部类
Collections.sort(students, (s1, s2) -> {
    int scoreCompare = s2.getScore() - s1.getScore();
    return scoreCompare == 0 ? s1.getId().compareTo(s2.getId()) : scoreCompare;
});

// Comparator 静态方法是更好看的写法
Collections.sort(students, 
    Comparator.comparingInt(Student::getScore).reversed() // 分数降序
    .thenComparing(Student::getId) // 分数相等则学号升序
);

Comparable 接口和 Comparator 接口都是 Java 中用于排序的接口，它们在实现类对象之间比较大小、排序等方面发挥了重要作用：

Comparable是内部比较器，接口实际上是出自java.lang包，它有一个 compareTo(Object obj)方法用来排序
Comparator是外部比较器，接口实际上是出自 java.util 包，它有一个compare(Object obj1, Object obj2)方法用来排序

那么，它们的设计哲学完全不同，Comparable的定义是自然排序，Comparator的定义是定制排序。Comparable只能定义一套排序规则，Comparator可定义多套排序规则

一般我们需要对一个集合使用自定义排序时，我们就要重写compareTo()方法或compare()方法，但是当我们需要对某一个集合实现两种排序方式，我们可以重写compareTo()方法和使用自制的Comparator方法，因为Comparable<T>只能有一种排序规则，而Comparator<T>可以有多个排序规则，可以按需定义，而且Comparator<T>支持Lambda，Comparable<T>不支持

例如，对下面这样的一个类

// Student.java
public class Student {
    private String name;
    private int score;

    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }

    public String getName() { return name; }
    public int getScore() { return score; }

    @Override
    public String toString() {
        return name + "(" + score + ")";
    }
}

使用 Comparable：定义“自然排序”（比如按分数升序）

public class Student implements Comparable<Student> {
    // ... 上述字段和构造器 ...

    @Override
    public int compareTo(Student other) {
        // 按分数升序（注意：避免 o1 - o2，防止溢出！）
        return Integer.compare(this.score, other.score);
    }

    // ... toString() ...
}

Collections.sort(list); // 自动使用 compareTo()

使用 Comparator：定义多种排序规则

// 1. 按姓名排序（Lambda）
Comparator<Student> byName = (s1, s2) -> s1.getName().compareTo(s2.getName());

// 2. 按分数降序（方法引用 + reversed）
Comparator<Student> byScoreDesc = Comparator.comparingInt(Student::getScore).reversed();

// 3. 先按分数降序，再按姓名升序（链式）
Comparator<Student> complex = 
    Comparator.comparingInt(Student::getScore).reversed()
              .thenComparing(Student::getName);

// 使用
List<Student> list = ...; // 同上

list.sort(byName);         // 按姓名
list.sort(byScoreDesc);    // 按分数降序
list.sort(complex);        // 复合排序

上述排序都不是自然排序，所以，当需要到其他的排序方法的时候，就需要Comparator，要不然你就得改 compareTo()

而且Comparator对处理 null 有自己的支持

1	Comparator.nullsLast(Comparator.naturalOrder()) // null 放最后

而且若同时存在 Comparable 和传入，Comparator 优先！

1	Collections.sort(list, myComparator); // 忽略 compareTo()

无序性和不可重复性的含义是什么

无序性不等于随机性，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。也就是输出顺序与插入顺序不一致，但每次 JVM 运行中，只要哈希值不变，遍历顺序是确定的，除非你重写了 hashCode()

不可重复性是指添加的元素按照 equals() 判断时，返回 false，需要同时重写 equals() 方法和 hashCode() 方法。

比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同

HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类，都能保证元素唯一，并且都不是线程安全的。

底层数据结构不同：HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表（基于 HashMap 实现）。LinkedHashSet 的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。

唯一性判断不同：对于 HashSet 和 LinkedHashSet，比较它们的元素都是依赖 hashCode() + equals() 判断唯一性，而 TreeSet 是依赖 compareTo() 或 compare()，返回 0 视为重复

有序性不同：HashSet无序，这意味着插入元素的顺序和遍历或者输出元素的顺序可能不一致。LinkedHashSet是有序的，它保持元素的插入顺序，并且不允许重复元素。TreeSet不仅有序，还能根据自然排序或者 Comparator 的实现来自定义排序

应用场景不同：底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景，LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景，TreeSet 用于支持对元素自定义排序规则的场景

操作的性能不同：HashSet的元素增删查的时间复杂度是 O(1)，LinkedHashSet也是O(1)，但是 LinkedHashSet因为要维护链表，使用起来要比 HashSet 慢一点，而且 TreeSet 因为红黑树平衡操作，所以是O(log n)

允许 null 的情况：HashSet 和 LinkedHashSet 都允许一个 null，TreeSet不允许 null，会抛 NullPointerException

Set<String> hashSet = new HashSet<>();
Set<String> linkedHashSet = new LinkedHashSet<>();
Set<String> treeSet = new TreeSet<>();

// 插入相同元素（乱序）
Collections.addAll(hashSet, "Banana", "Apple", "Orange");
Collections.addAll(linkedHashSet, "Banana", "Apple", "Orange");
Collections.addAll(treeSet, "Banana", "Apple", "Orange");

System.out.println("HashSet:      " + hashSet);      
// 输出：[Apple, Orange, Banana] （无序）

System.out.println("LinkedHashSet: " + linkedHashSet); 
// 输出：[Banana, Apple, Orange] （插入顺序）

System.out.println("TreeSet:       " + treeSet);       
// 输出：[Apple, Banana, Orange] （字典序）

描述一下 HashSet 的去重原理

HashSet 是基于 HashMap 实现的，它利用哈希表（Hash Table）来存储元素，并通过对象的 hashCode() 和 equals() 方法来实现去重。

具体来说，HashSet 的去重原理如下：

底层结构 HashSet 内部封装了一个 HashMap，所有存入 HashSet 的元素实际上作为 HashMap 的 key 存储，而 value 则是一个固定的 Object 对象（通常是 PRESENT 哨兵对象）。由于 HashMap 的 key 本身不允许重复，这就天然保证了 HashSet 的元素唯一性。
插入过程中的去重逻辑 当调用 add(E e) 方法添加元素时：
- 首先调用该元素的 hashCode() 方法，计算其哈希值；
- 根据哈希值确定在底层哈希表（数组 + 链表/红黑树）中的存储位置（即桶 index）；
- 如果该位置为空，则直接插入；
- 如果该位置已有元素（发生哈希冲突），则遍历该位置上的链表或红黑树，依次调用 equals() 方法与新元素比较；
  - 若存在某个已有元素 e.equals(newElement) 返回 true，说明元素已存在，不插入；
  - 否则，将新元素插入到该位置（链表尾部或树中）。
为了保证 HashSet 正确去重，hashCode() 与 equals()必须遵守 Java 的通用约定：

如果两个对象通过 equals() 判定为相等，那么它们的 hashCode() 必须相同；反之，如果 hashCode() 相同，equals() 不一定为 true（即哈希冲突是允许的）。
如果只重写 equals() 而不重写 hashCode()，可能导致逻辑上相等的对象被存入 HashSet 多次，破坏去重语义。

也就是说，HashSet 的去重依赖于对象的 hashCode() 定位存储位置，再通过 equals() 精确判断是否重复，二者缺一不可。

Set 中如何实现对自定义类的去重？需要重写什么方法？

定义一个Person类，包含id和name两个属性。要求在HashSet中存储Person对象时，能够正确去重。

在自定义类中重写hashCode和equals方法，确保HashSet能够正确判断两个对象是否相等就可以

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

class Person {
    private int id;
    private String name;

    public Person(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Person person = (Person) obj;
        return id == person.id && Objects.equals(name, person.name);
    }

    @Override
    public String toString() {
        return "Person{id=" + id + ", name='" + name + "'}";
    }
}

public class PersonHashSetExample {
    public static void main(String[] args) {
        Set<Person> set = new HashSet<>();
        set.add(new Person(1001, "A"));
        set.add(new Person(1001, "A"));

        System.out.println(set); // 输出 [Person{id=1001, name='A'}]
    }
}

那么这里再总结一下 Set 集合的去重机制

方法	描述
`hashCode`	计算对象的哈希值，用于快速定位存储位置。
`equals`	判断两个对象是否相等，用于在存储位置上进一步判断是否重复。

首先通过hashCode方法计算哈希值，然后通过equals方法判断是否相等。

为什么在修改Set集合中对象的属性值后，可能会导致删除失败？

因为修改属性值后，对象的哈希值可能会发生变化，导致Set集合无法找到该对象。

Queue / Deque

Queue 与 Deque 的区别

Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则，通常情况下用来模拟队列

而 Deque 是双端队列，在队列的两端均可以插入或删除元素，也可以模拟栈

Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同，可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。

`Queue` 接口	抛出异常	返回特殊值
插入队尾	add(E e)	offer(E e)
删除队首	remove()	poll()
查询队首元素	element()	peek()

而且 Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：

`Deque` 接口	抛出异常	返回特殊值
插入队首	addFirst(E e)	offerFirst(E e)
插入队尾	addLast(E e)	offerLast(E e)
删除队首	removeFirst()	pollFirst()
删除队尾	removeLast()	pollLast()
查询队首元素	getFirst()	peekFirst()
查询队尾元素	getLast()	peekLast()

事实上，Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈

ArrayDeque 与 LinkedList 的区别

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都能模拟成栈和队列的功能，而且，都非线程安全

ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持，因为 LinkedList 同时实现了 List 接口，而 List 允许 null。

ArrayDeque不是不能支持null，但是poll() / peek() 等方法返回 null 表示“队列为空”。如果允许存 null，就无法区分是“空”还是“存了 null”，容易引发歧义或空指针异常。所以索性就不让存 null 了
ArrayDeque在中间增删是O(n)，LinkedList中间增删是O(1)，而且ArrayDeque每个元素内存占用比LinkedList少很多，ArrayDeque内存连续，LinkListDeque不连续，所以对性能、内存敏感的场景更好一些，而LinkedList在需要频繁在中间位置插入删除时候使用。
ArrayDeque 插入时可能存在扩容过程，不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。
ArrayDeque 未实现 List 接口，也没用 RandomAccess 接口标记，所以不支持随机访问，而 LinkedList 能够进行遍历的形式来随机访问

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈

Java 中的 PriorityQueue 是如何实现的？为什么它不支持 null 元素？线程安全吗？

Java 的 PriorityQueue 是基于可变长数组实现的二叉最小堆（min-heap）。它的核心操作如 offer()和 poll()的时间复杂度均为 O(log n)，而 peek() 是 O(1)。

关于 null 元素，PriorityQueue 不允许插入 null。原因在于它的 poll() 和 peek() 方法在队列为空时会返回 null。如果允许存入 null，就无法区分队列为空还是堆顶元素就是 null，会导致语义歧义，甚至引发逻辑错误或空指针异常。这是一种防御性编程设计。

此外，PriorityQueue 不是线程安全的。如果多线程并发访问，必须手动加锁，或者改用并发版本 PriorityBlockingQueue。

而且，PriorityQueue 既然基于可变长数组实现的，那么它也有初始的内存分配，并且会自动扩容。机制和 ArrayList 很像

PriorityQueue虽然内部是堆结构，但迭代器不保证有序，因为堆只保证堆顶最小，其余元素无全局顺序。

如何用 PriorityQueue 找出一个大数组中最大的 K 个元素？要求时间复杂度尽可能低。

创建一个容量为 K 的 最小堆，也就是 PriorityQueue，然后遍历数组：

如果堆 size < K，直接加入；
否则，若当前元素 > 堆顶（即当前 K 个中的最小值），则弹出堆顶，加入当前元素。

遍历结束后，堆中就是最大的 K 个元素

import java.util.*;

public class TopK {
    public static List<Integer> findTopK(int[] nums, int k) {
        if (k <= 0 || nums == null || nums.length == 0) 
            return new ArrayList<>();
        
        // 最小堆：堆顶是当前 K 个中的最小值
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        
        for (int num : nums) {
            if (minHeap.size() < k) {
                minHeap.offer(num);
            } else if (num > minHeap.peek()) {
                minHeap.poll();      // 弹出最小的
                minHeap.offer(num);  // 加入更大的
            }
        }
        
        // 返回结果（顺序不重要，或可排序）
        return new ArrayList<>(minHeap);
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 1, 5, 6, 4};
        System.out.println(findTopK(arr, 2)); // 可能输出 [5, 6] 或 [6, 5]
    }
}

什么是 BlockingQueue？其实现类有哪些？

BlockingQueue （阻塞队列）是一个接口，继承自 Queue。BlockingQueue阻塞的原因是其支持当队列没有元素时一直阻塞，直到有元素；还支持如果队列已满，一直等到队列可以放入新元素时再放入。

BlockingQueue 常用于生产者-消费者模型中，生产者线程会向队列中添加数据，而消费者线程会从队列中取出数据进行处理

Java 中常用的阻塞队列实现类有以下几种：

ArrayBlockingQueue：使用数组实现的有界阻塞队列。在创建时需要指定容量大小，并支持公平和非公平两种方式的锁访问机制。
LinkedBlockingQueue：使用单向链表实现的可选有界阻塞队列。在创建时可以指定容量大小，如果不指定则默认为Integer.MAX_VALUE。和ArrayBlockingQueue不同的是，它仅支持非公平的锁访问机制。
PriorityBlockingQueue：支持优先级排序的无界阻塞队列。元素必须实现Comparable接口或者在构造函数中传入Comparator对象，并且不能插入 null 元素。
SynchronousQueue：同步队列，是一种不存储元素的阻塞队列。每个插入操作都必须等待对应的删除操作，反之删除操作也必须等待插入操作。因此，SynchronousQueue通常用于线程之间的直接传递数据。
DelayQueue：延迟队列，其中的元素只有到了其指定的延迟时间，才能够从队列中出队。

ArrayBlockingQueue 和 LinkedBlockingQueue 有什么区别？

ArrayBlockingQueue 和 LinkedBlockingQueue 是 Java 并发包中常用的两种阻塞队列实现，它们都是线程安全的。不过，不过它们之间也存在下面这些区别：

底层实现：ArrayBlockingQueue 基于数组实现，而 LinkedBlockingQueue 基于链表实现。
是否有界：ArrayBlockingQueue 是有界队列，必须在创建时指定容量大小。LinkedBlockingQueue 创建时可以不指定容量大小，默认是Integer.MAX_VALUE，也就是无界的。但也可以指定队列大小，从而成为有界的。
锁是否分离： ArrayBlockingQueue中的锁是没有分离的，即生产和消费用的是同一个锁；LinkedBlockingQueue中的锁是分离的，即生产用的是putLock，消费是takeLock，这样可以防止生产者和消费者线程之间的锁争夺。
内存占用：ArrayBlockingQueue 需要提前分配数组内存，而 LinkedBlockingQueue 则是动态分配链表节点内存。这意味着，ArrayBlockingQueue 在创建时就会占用一定的内存空间，且往往申请的内存比实际所用的内存更大，而LinkedBlockingQueue 则是根据元素的增加而逐渐占用内存空间

Map

HashMap 和 Hashtable 的区别

线程是否安全：HashMap 是非线程安全的，Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过synchronized 修饰。但是这样加锁性能是真不好，所以说足够好的并发容器出现后，Hashtable它就基本被替代了。如果你要保证线程安全的话就使用 ConcurrentHashMap 吧
效率： 因为线程安全的问题，HashMap 要比 Hashtable 效率高一点。另外，Hashtable 基本被淘汰，不要在代码中使用它；
对 Null key 和 Null value 的支持：HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
初始容量大小和每次扩充容量大小的不同：
- 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。
- 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小，后面会介绍到为什么是 2 的幂次方。
底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间。Hashtable 没有这样的机制，它就是数组加上链表。
哈希函数的实现：HashMap 对哈希值进行了高位和低位的混合扰动处理以减少冲突，而 Hashtable 直接使用键的 hashCode() 值。

HashMap 的构造函数中有一个 tableSizeFor(int cap) 方法，它的作用就是将用户传入的任意初始容量，自动调整为大于等于该值的最小 2 的幂次方。

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);
}
 public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

下面这个方法保证了 HashMap 总是使用 2 的幂作为哈希表的大小。

/**
 * Returns a power of two size for the given target capacity.
 */
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;
}

说一下 Map 和 Set 的区别？

首先，Map 是键值对（Key-Value）集合，核心是通过键快速查找值，本质是映射关系的存储

而 Set 是单值集合，核心诉求是保证元素唯一性，本质是不重复的单个元素的存储，且 Set 的底层实现几乎都是基于 Map，用 Map 的 Key 来保证 Set 元素的唯一性

Set 本身没有独立的底层实现，而是借用 Map 的 Key 来保证唯一性，Value 用一个固定的空对象填充（

存储结构：

Map 存键值对，Key 和 Value 是两个独立维度；

Set 是单值存储
元素唯一性和空值支持：

Map 仅 Key 唯一，Value 可重复，而且 HashMap 允许 1 个 null Key，剩下大部分 Map 不允许 key 为 null。

Set 保持元素唯一，HashSet 允许 1 个 null，TreeSet 不允许 null
有序性：

Map 多数无序，LinkedHashMap 按插入顺序 / 访问顺序；TreeMap 按 Key 排序；

Set 也是多数无序，LinkedHashSet 按插入顺序；TreeSet 按元素自然排序
访问方式：

Map 通过 Key 操作，无索引概念

Set 能直接操作元素，也无索引、无 Key 概念
底层数据结构

HashMap 是哈希表，链表，红黑树，TreeMap 是红黑树、LinkedHashMap 是哈希表 + 链表

Set 大部分的底层实现依赖于 Map

HashMap 和 TreeMap 区别

TreeMap 和HashMap 都继承自AbstractMap ，但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap 接口。所以说，TreeMap是有序的

实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。因为NavigableMap 接口提供了丰富的方法来探索和操作键值对
1. 定向搜索: ceilingEntry(), floorEntry(), higherEntry()和 lowerEntry() 等方法可以用于定位大于等于、小于等于、严格大于、严格小于给定键的最接近的键值对。
2. 子集操作: subMap(), headMap()和 tailMap() 方法可以高效地创建原集合的子集视图，而无需复制整个集合。
3. 逆序视图:descendingMap() 方法返回一个逆序的 NavigableMap 视图，使得可以反向迭代整个 TreeMap。
4. 边界操作: firstEntry(), lastEntry(), pollFirstEntry()和 pollLastEntry() 等方法可以方便地访问和移除元素。
这些方法都是基于红黑树数据结构的属性实现的，红黑树保持平衡状态，从而保证了搜索操作的时间复杂度为 O(log n)，这让 TreeMap 成为了处理有序集合搜索问题的强大工具。

实现SortedMap接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。

/**
 * @author shuang.kou
 * @createTime 2020年06月15日 17:02:00
 */
public class Person {
    private Integer age;

    public Person(Integer age) {
        this.age = age;
    }

    public Integer getAge() {
        return age;
    }


    public static void main(String[] args) {
        TreeMap<Person, String> treeMap = new TreeMap<>(new Comparator<Person>() {
            @Override
            public int compare(Person person1, Person person2) {
                int num = person1.getAge() - person2.getAge();
                return Integer.compare(num, 0);
            }
        });
        treeMap.put(new Person(3), "person1");
        treeMap.put(new Person(18), "person2");
        treeMap.put(new Person(35), "person3");
        treeMap.put(new Person(16), "person4");
        treeMap.entrySet().stream().forEach(personStringEntry -> {
            System.out.println(personStringEntry.getValue());
        });
    }
}

综上，相比于HashMap来说，TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力

描述一下HashMap 的底层实现

JDK1.8 之前

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用，也就是 链表散列。

HashMap 通过 key 的 hashcode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置，如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决哈希冲突。

HashMap 中的扰动函数（hash 方法）是用来优化哈希值的分布。通过对原始的 hashCode() 进行额外处理，扰动函数可以减小由于高低位的分配问题的 hashCode() 实现导致的碰撞，从而提高数据的分布均匀性。

JDK 1.8 的 hash 方法相比于 JDK 1.7 hash 方法更加简化，但是原理不变。

static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^：按位异或
      // >>>:无符号右移，忽略符号位，空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

JDK1.8 之后

相比于之前的版本， JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树。

这样做的目的是减少搜索时间：链表的查询效率为 O(n)（n 是链表的长度），红黑树是一种自平衡二叉搜索树，其查询效率为 O(log n)。当链表较短时，O(n) 和 O(log n) 的性能差异不明显。但当链表变长时，查询性能会显著下降。

数组扩容能减少哈希冲突的发生概率（即将元素重新分散到新的、更大的数组中），这在多数情况下比直接转换为红黑树更高效。因为红黑树需要保持自平衡，维护成本较高。并且，过早引入红黑树反而会增加复杂度。

对于数组扩容，HashMap 有个负载因子默认 0.75，意思就是数组用了 75% 就自动扩容，把数组大小翻倍，然后把所有数据重新算位置放到新数组里，这个操作叫 rehash，比较耗性能，所以初始化时最好给个预估容量，避免频繁扩容

为什么选择阈值 8 和 64？

泊松分布表明，链表长度达到 8 的概率极低，小于千万分之一。在绝大多数情况下，链表长度都不会超过 8。阈值设置为 8，可以保证性能和空间效率的平衡。
数组长度阈值 64 同样是经过实践验证的经验值。在小数组中扩容成本低，优先扩容可以避免过早引入红黑树。数组大小达到 64 时，冲突概率较高，此时红黑树的性能优势开始显现。

TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。

所以说，被问到使用 HashMap 时，有哪些提升性能的技巧？就可以结合上面的进行分析

少扩容，初始容量给够，避免rehash，优先使用官方0.75的负载因子，确保 hashCode 均匀分布

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

HashMap 的扩容由负载因子控制，默认是 0.75。

0.75 是时间和空间之间的一个平衡点。负载因子太低，扩容太频繁，内存浪费；太高，冲突太多，查找变慢。0.75 经过大量实践验证，在大多数场景下都能保持不错的性能。

意思就是当元素数量超过 容量 × 0.75 时触发扩容。比如初始容量 16，阈值就是 12，存第 13 个元素时就会扩容。

扩容的规则很简单：容量直接翻倍，从 16 变 32，32 变 64，为了始终保持容量是 2 的幂次。

但是扩容后所有元素要重新分配位置，这个过程叫 rehashing。即每个元素的存储位置会根据新容量的大小重新计算，并移动到新的数组中。这是比较消耗性能的，应该避免

JDK8对于 HashMap 的 rehash 算法进行了优化，使用了位运算

JDK 1.8 对 HashMap 除了引入红黑树，上述的扩容机制使用位运算优化也是发生在 1.8 的

所以说，JDK 1.8 对 HashMap 除了引入红黑树，还有三个重要改动，

哈希函数简化，只做一次哈希，把 key 的 hashCode 高 16 位和低 16 位异或一下就完事了。这样既保证了高低位都能参与索引计算

扩容不再逐个取模：1.7 扩容时每个元素都要重新算一遍 hash % newCapacity，1.8 利用了一个巧妙的特性，元素要么留原位，要么挪到「原位置 + 老数组长度」，通过一次位运算就能判断

头插法改尾插法：1.7 插入新节点直接往链表头部塞，扩容时链表会倒过来。多线程环境下，两个线程同时扩容可能把链表搞成环然后死循环。1.8 改成尾插法，扩容后顺序不变，避免了成环问题。

HashMap 的长度为什么是 2 的幂次方

HashMap 的容量被设计为 2 的幂次方，主要是出于性能优化和算法实现简便性的考虑

使用高效的位运算替代取模运算，提升索引计算速度

首先，在 HashMap 中，我们需要根据 key 的哈希值来确定它应该存放在底层数组桶（table）中的哪个位置（索引）。最直观的方法是使用取模运算：index = hash % length。

但是，取模运算（%）在 CPU 层面涉及除法操作，效率相对较低。通常情况下，我们会用位与运算（&） 来代替它。HashMap 也是这样设计的

当数组长度 length 是 2 的幂次方时，length - 1 的二进制表示会是一串连续的 1。例如，长度为 16（2^4）时，length - 1 = 15，其二进制是 1111。

此时，hash & (length - 1) 的效果就等同于 hash % length，但它只进行一次非常快速的位运算，极大地提升了计算索引的性能。
确保内部的哈希值能均匀分布，减少哈希的冲突

其次，这个设计有助于更均匀地分布元素，从而减少哈希冲突

因为 length - 1 全是 1，所以 hash & (length - 1) 实际上是在截取哈希值的低 n 位（n 是 length 的指数）。这使得哈希值的低位信息能够充分参与索引计算。

如果长度不是 2 的幂，比如 10，那么 length - 1 = 9（二进制 1001），进行 & 运算时，只有特定的非0位（第0位和第3位）会起作用，其他位会被屏蔽掉。这会导致很多不同的哈希值映射到同一个索引上，造成严重的哈希冲突，降低 HashMap 的性能。
简化扩容（resize）时的元素迁移逻辑

HashMap 扩容时，新容量是原容量的两倍，因此新容量也必然是 2 的幂次方。

在这种情况下，一个元素在扩容后的新位置只有两种可能：
- 要么保持在原来的位置；
- 要么移动到 原位置 + 原容量 的位置。
这个判断只需要检查哈希值新增的那一位是 0 还是 1 即可，即 hash & oldCap 是否为 0，如果是 0 说明保持在原位置，1 就是进行了移动

HashMap 的构造函数中有一个 tableSizeFor(int cap) 方法，它的作用就是将用户传入的任意初始容量，自动调整为大于等于该值的最小 2 的幂次方。

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);
}
 public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

下面这个方法保证了 HashMap 总是使用 2 的幂作为哈希表的大小。

/**
 * Returns a power of two size for the given target capacity.
 */
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;
}

HashMap 的 put 流程是怎么样的

HashMap 的 put() 方法用于向 HashMap 中添加键值对

根据要添加的键的哈希码计算在数组中的位置
检查数组中该位置是否为空
- 如果为空，则直接在该位置创建一个新的 Entry 对象来存储键值对。然后放入数组。将HashMap的修改次数modCount 加1
如果该位置已经存在其他键值对，检查该位置的第一个键值对的哈希码和键是否与要添加的键值对相同
- 如果相同，则表示找到了相同的键，直接将新的值替换旧的值，完成更新操作。
如果第一个键值对的哈希码和键不相同，则需要遍历链表或红黑树来查找是否有相同的键
- 如果键值对集合是链表结构，从链表的头部开始逐个比较键的哈希码和 equals() 方法，直到找到相同的键或达到链表末尾。
  - 找到了相同的就更新
  - 没有找到相同的键就将新的键值对添加到链表的头部。
- 如果键值对集合是红黑树结构，在红黑树中使用哈希码和 equals()方法进行查找。根据键的哈希码，定位到红黑树中的某个节点来比较键，直到找到相同的键或达到红黑树末尾。
  - 找到了相同的就更新
  - 没有找到相同的键就将新的键值对添加到红黑树中
检查链表长度是否达到阈值，默认为8
- 如果链表长度超过阈值，且 HashMap 的数组长度大于等于64，则会将链表转换为红黑树，以提高查询效率。
检查负载因子是否超过阈值，默认0.75
- 大于需要进行扩容
  - 创建一个新的两倍大小的数组
  - 将旧数组中的键值对进行 rehash 并分配到新数组中的位置。
  - 更新 HashMap 的数组引用和阈值参数。
添加操作完成

说一下 HashMap 多线程操作导致死循环问题

JDK1.7 及之前版本的 HashMap 在多线程环境下扩容操作可能存在死循环问题，这是由于当一个桶位中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束。

为了解决这个问题，JDK1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。但是还是不建议在多线程下使用 HashMap，因为多线程下使用 HashMap 还是会存在数据覆盖的问题。并发环境下，推荐使用 ConcurrentHashMap 。

说一下HashMap 为什么线程不安全

HashMap 不是线程安全的。在多线程环境下对 HashMap 进行并发写操作，可能会导致两种主要问题：

数据丢失：并发 put 操作可能导致一个线程的写入被另一个线程覆盖。
无限循环：在 JDK 7 及以前的版本中，并发扩容时，由于头插法可能导致链表形成环，从而在 get 操作时引发无限循环，CPU 飙升至 100%。

数据丢失这个在 JDK1.7 和 JDK 1.8 中都存在，这里以 JDK 1.8 为例进行介绍。

JDK 1.8 后，在 HashMap 中，多个键值对可能会被分配到同一个桶（bucket），并以链表或红黑树的形式存储。多个线程对 HashMap 的 put 操作会导致线程不安全，具体来说会有数据覆盖的风险。

举个例子：

两个线程 1,2 同时进行 put 操作，并且发生了哈希冲突（hash 函数计算出的插入下标是相同的）。
不同的线程可能在不同的时间片获得 CPU 执行的机会，当前线程 1 执行完哈希冲突判断后，由于时间片耗尽挂起。线程 2 先完成了插入操作。
随后，线程 1 获得时间片，由于之前已经进行过 hash 碰撞的判断，所有此时会直接进行插入，这就导致线程 2 插入的数据被线程 1 覆盖了。

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) {
    // ...
    // 判断是否出现 hash 碰撞
    // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 桶中已经存在元素（处理hash冲突）
    else {
    // ...
}

还有一种情况是这两个线程同时 put 操作导致 size 的值不正确，进而导致数据覆盖的问题：

线程 1 执行 if(++size > threshold) 判断时，假设获得 size 的值为 10，由于时间片耗尽挂起。
线程 2 也执行 if(++size > threshold) 判断，获得 size 的值也为 10，并将元素插入到该桶位中，并将 size 的值更新为 11。
随后，线程 1 获得时间片，它也将元素放入桶位中，并将 size 的值更新为 11。
线程 1、2 都执行了一次 put 操作，但是 size 的值只增加了 1，也就导致实际上只有一个元素被添加到了 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) {
    // ...
    // 实际大小大于阈值则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

Java 中的 LinkedHashMap 是什么？

LinkedHashMap 继承自 HashMap，在 HashMap 的基础上用双向链表把所有节点串起来，保证遍历顺序和插入顺序一致。

它有两种排序模式：插入顺序和访问顺序。默认是插入顺序，谁先 put 谁在前面；

而访问顺序模式天然适合做 LRU 缓存，只要继承 LinkedHashMap 重写 removeEldestEntry 方法，就能在插入新元素时自动淘汰最老的节点。Mybatis 的本地缓存 LruCache 就是这么实现的。

LinkedHashMap 不是线程安全的，和 HashMap 一样。因为引入了双向链表，遍历是O(n)，但是相比 HashMap 遍历的 O(n)好处是不会遍历空桶，效率更稳定。

ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

而两者的底层的数据结构大差不差， JDK 1.7 之前都是分段的数组+链表 实现，在 JDK1.8 中采用的数据结构跟 HashMap 的结构一样，数组+链表/红黑二叉树。

ConcurrentHashMap 是如何实现线程安全的？ConcurrentHashMap用了悲观锁还是乐观锁?

ConcurrentHashMap在数据结构上的实现和HashMap差别不大，重点是实现线程安全的原理

JDK 1.7：数组加链表

数组又分为：大数组 Segment 和小数组 HashEntry。
- Segment 是一种可重入锁（ReentrantLock的子类），在 ConcurrentHashMap 里扮演锁的角色
- HashEntry 则用于存储键值对数据。
一个 ConcurrentHashMap 里包含一个 Segment 数组，一个 Segment 里包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素。

JDK 1.7 ConcurrentHashMap 分段锁技术将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。
JDK 1.8：数组 + 链表/红黑树

ConcurrentHashMap 主要通过 volatile + CAS 或者 synchronized 来实现的线程安全的。

添加元素时首先会判断容器是否为空：
- 如果为空则使用 volatile 加 CAS 来初始化
- 如果容器不为空
  - 需要被存储的元素在容器中的位置为空，则利用 CAS 设置该节点；
  - 需要被存储的元素在容器中的位置不为空，则使用 synchronized ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。
是ConcurrentHashMap通过对头结点加锁来保证线程安全的，锁的粒度相比 Segment 来说更小了，发生冲突和加锁的频率降低了，并发操作的性能就提高了。