概念

常见的 Java 集合：

• ArrayList： 动态数组，实现了 List 接口，支持动态增长。
• LinkedList： 双向链表，也实现了 List 接口，支持快速的插入和删除操作。
• HashMap： 基于哈希表的 Map 实现，存储键值对，通过键快速查找值。
• HashSet： 基于 HashMap 实现的 Set 集合，用于存储唯一元素。
• TreeMap： 基于红黑树实现的有序 Map 集合，可以按照键的顺序进行排序。
• LinkedHashMap： 基于哈希表和双向链表实现的 Map 集合，保持插入顺序或访问顺序。
• PriorityQueue： 优先队列，可以按照比较器或元素的自然顺序进行排序。

线程安全的集合

java.util 包：

• Vector
• Hashtable java.util.concurrent 包提供的都是线程安全的集合：
• ConcurrentHashMap：它与 HashTable 的主要区别是二者加锁粒度的不同，在 JDK1.7，ConcurrentHashMap 加的是分段锁，也就是 Segment 锁，每个 Segment 含有整个 table 的一部分，这样不同分段之间的并发操作就互不影响。在 JDK 1.8 ，它取消了 Segment 字段，直接在 table 元素上加锁，实现对每一行进行加锁，进一步减小了并发冲突的概率。对于 put 操作，如果 Key 对应的数组元素为 null，则通过 CAS 操作（Compare and Swap）将其设置为当前值。如果 Key 对应的数组元素（也即链表表头或者树的根元素）不为 null，则对该元素使用 synchronized 关键字申请锁，然后进行操作。如果该 put 操作使得当前链表长度超过一定阈值，则将该链表转换为红黑树，从而提高寻址效率。
• ConcurrentSkipListMap：实现了一个基于 SkipList（跳表）算法的可排序的并发集合，SkipList 是一种可以在对数预期时间内完成搜索、插入、删除等操作的数据结构，通过维护多个指向其他元素的“跳跃”链接来实现高效查找。 并发 Set：
• ConcurrentSkipListSet：是线程安全的有序的集合。底层是使用 ConcurrentSkipListMap 实现。
• CopyOnWriteArraySet：是线程安全的 Set 实现，它是线程安全的无序的集合，可以将它理解成线程安全的 HashSet。有意思的是，CopyOnWriteArraySet 和 HashSet 虽然都继承于共同的父类 AbstractSet；但是，HashSet 是通过“散列表”实现的，而 CopyOnWriteArraySet 则是通过“动态数组 (CopyOnWriteArrayList)”实现的，并不是散列表。 并发 List：
• CopyOnWriteArrayList：它是 ArrayList 的线程安全的变体，其中所有写操作（add，set 等）都通过对底层数组进行全新复制来实现，允许存储 null 元素。即当对象进行写操作时，使用了 Lock 锁做同步处理，内部拷贝了原数组，并在新数组上进行添加操作，最后将新数组替换掉旧数组；若进行的读操作，则直接返回结果，操作过程中不需要进行同步。 并发 Queue：
• ConcurrentLinkedQueue：是一个适用于高并发场景下的队列，它通过无锁的方式 (CAS)，实现了高并发状态下的高性能。通常，ConcurrentLinkedQueue 的性能要好于 BlockingQueue 。
• BlockingQueue：与 ConcurrentLinkedQueue 的使用场景不同，BlockingQueue 的主要功能并不是在于提升高并发时的队列性能，而在于简化多线程间的数据共享。BlockingQueue 提供一种读写阻塞等待的机制，即如果消费者速度较快，则 BlockingQueue 则可能被清空，此时消费线程再试图从 BlockingQueue 读取数据时就会被阻塞。反之，如果生产线程较快，则 BlockingQueue 可能会被装满，此时，生产线程再试图向 BlockingQueue 队列装入数据时，便会被阻塞等待。 并发 Deque：
• LinkedBlockingDeque：是一个线程安全的双端队列实现。它的内部使用链表结构，每一个节点都维护了一个前驱节点和一个后驱节点。LinkedBlockingDeque 没有进行读写锁的分离，因此同一时间只能有一个线程对其进行操作
• ConcurrentLinkedDeque：ConcurrentLinkedDeque 是一种基于链接节点的无限并发链表。可以安全地并发执行插入、删除和访问操作。当许多线程同时访问一个公共集合时，ConcurrentLinkedDeque 是一个合适的选择。

Collections 和 Collection 的区别

• Collection 是 Java 集合框架中的一个接口，它是所有集合类的基础接口。它定义了一组通用的操作和方法，如添加、删除、遍历等，用于操作和管理一组对象。Collection 接口有许多实现类，如 List、Set 和 Queue 等。
• Collections（注意有一个 s）是 Java 提供的一个工具类，位于 java.util 包中。它提供了一系列静态方法，用于对集合进行操作和算法。Collections 类中的方法包括排序、查找、替换、反转、随机化等等。这些方法可以对实现了 Collection 接口的集合进行操作，如 List 和 Set。

遍历集合方法

• 普通 for 循环
• for-each 循环
• Iterator 迭代器
• ListIterator 迭代器
• forEach 方法
• Stream API

List

常见 List 集合（非线程安全）：

• ArrayList：动态数组实现
• LinkedList：双向链表实现 常见 List 集合（线程安全）：
• Vector：Vector 和 ArrayList 类似，也是基于数组实现。Vector 中的方法大多是同步的
• CopyOnWriteArrayList 在对列表进行修改（如添加、删除元素）时，会创建一个新的底层数组，将修改操作应用到新数组上，而读操作仍然在原数组上进行，这样可以保证读操作不会被写操作阻塞，实现了读写分离，提高了并发性能。适用于读操作远远多于写操作的并发场景，如事件监听列表等，在这种场景下可以避免大量的锁竞争，提高系统的性能和响应速度。

list 可以一边遍历一边修改元素吗？

• for 循环：可以
• for-each 循环：不可以，破坏迭代器内部状态
• 迭代器遍历 list.iterator()：用迭代器的 set 方法可以

ArrayList 怎么变成线程安全的

• 使用 Collections 类的 synchronizedList 方法将 ArrayList 包装成线程安全的 List：

List<String> synchronizedList = Collections.synchronizedList(arrayList);

• 使用 CopyOnWriteArrayList 类代替 ArrayList，它是一个线程安全的 List 实现：

CopyOnWriteArrayList<String> copyOnWriteArrayList = new CopyOnWriteArrayList<>(arrayList);

• 使用 Vector 类代替 ArrayList，Vector 是线程安全的 List 实现：

Vector<String> vector = new Vector<>(arrayList);

线程安全的 List， CopyonWriteArraylist 是如何实现线程安全的

CopyOnWriteArrayList 底层也是通过一个数组保存数据，使用 volatile 关键字修饰数组，保证当前线程对数组对象重新赋值后，其他线程可以及时感知到。

private transient volatile Object[] array;

在写入操作时，加了一把互斥锁 ReentrantLock 以保证线程安全。

public boolean add(E e) {
    //获取锁
    final ReentrantLock lock = this.lock;
    //加锁
    lock.lock();
    try {
        //获取到当前List集合保存数据的数组
        Object[] elements = getArray();
        //获取该数组的长度（这是一个伏笔，同时len也是新数组的最后一个元素的索引值）
        int len = elements.length;
        //将当前数组拷贝一份的同时，让其长度加1
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        //将加入的元素放在新数组最后一位，len不是旧数组长度吗，为什么现在用它当成新数组的最后一个元素的下标？建议自行画图推演，就很容易理解。
        newElements[len] = e;
        //替换引用，将数组的引用指向给新数组的地址
        setArray(newElements);
        return true;
    } finally {
        //释放锁
        lock.unlock();
    }
}

看到源码可以知道写入新元素时，首先会先将原来的数组拷贝一份并且让原来数组的长度 +1 后就得到了一个新数组，新数组里的元素和旧数组的元素一样并且长度比旧数组多一个长度，然后将新加入的元素放置都在新数组最后一个位置后，用新数组的地址替换掉老数组的地址就能得到最新的数据了。

在我们执行替换地址操作之前，读取的是老数组的数据，数据是有效数据；执行替换地址操作之后，读取的是新数组的数据，同样也是有效数据，而且使用该方式能比读写都加锁要更加的效率。读操作，读是没有加锁的，所以读是一直都能读

Map

常见的 Map 集合（非线程安全）：

• HashMap：数组 + 链表 + 红黑树（长链表转红黑树）
• LinkedHashMap：继承自 HashMap，它在 HashMap 的基础上，使用双向链表维护了键值对的插入顺序或访问顺序
• TreeMap：基于红黑树实现的 Map，它可以对键进行排序，默认按照自然顺序排序，也可以通过指定的比较器进行排序 常见的 Map 集合（线程安全）：
• Hashtable：用了 synchronized 关键字来保证线程安全
• ConcurrentHashMap：在 JDK 1.8 以前采用了分段锁等技术来提高并发性能。在 ConcurrentHashMap 中，将数据分成多个段（Segment），每个段都有自己的锁。在进行插入、删除等操作时，只需要获取相应段的锁，而不是整个 Map 的锁，这样可以允许多个线程同时访问不同的段，提高了并发访问的效率。在 JDK 1.8 以后是通过 volatile + CAS 或者 synchronized 来保证线程安全的。

Map 遍历

• for-each + entrySet()
• for-each + keySet()
• 迭代器：如 map.entrySet().iterator()
• Lambda + forEach()：map.forEach((key, value) -> ... )
• Stream API：map.entrySet().stream.filter(entry -> ...)

哈希冲突解决方法

• 链接法：使用链表或其他数据结构来存储冲突的键值对，将它们链接在同一个哈希桶中。
• 开放寻址法：在哈希表中找到另一个可用的位置来存储冲突的键值对，而不是存储在链表中。常见的开放寻址方法包括线性探测、二次探测和双重散列。
• 再哈希法（Rehashing）：当发生冲突时，使用另一个哈希函数再次计算键的哈希值，直到找到一个空槽来存储键值对。
• 哈希桶扩容：当哈希冲突过多时，可以动态地扩大哈希桶的数量，重新分配键值对，以减少冲突的概率。

HashMap put 过程

为什么 HashMap 要用红黑树而不是平衡二叉树？

• 平衡二叉树追求的是一种 “完全平衡” 状态：任何结点的左右子树的高度差不会超过 1，优势是树的结点是很平均分配的。这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。
• 红黑树不追求这种完全平衡状态，而是追求一种 “弱平衡” 状态：整个树最长路径不会超过最短路径的 2 倍。优势是虽然牺牲了一部分查找的性能效率，但是能够换取一部分维持树平衡状态的成本。与平衡树不同的是，红黑树在插入、删除等操作，不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整，这也是我们为什么大多数情况下使用红黑树的原因。

HashMap 的扩容机制介绍一下

HashMap 默认的负载因子是 0.75，即如果 hashmap 中的元素个数超过了总容量 75%，则会触发扩容，扩容分为两个步骤：

• 对哈希表长度的扩展（2 倍）
• 将旧哈希表中的数据放到新的哈希表中。 因为我们使用的是 2 次幂的扩展 (指长度扩为原来 2 倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动 2 次幂的位置。如我们从 16 扩展为 32 时，具体的变化如下所示： 因此元素在重新计算 hash 之后，因为 n 变为 2 倍，那么 n-1 的 mask 范围在高位多 1bit(红色)，因此新的 index 就会发生这样的变化： 因此，我们在扩充 HashMap 的时候，不需要重新计算 hash，只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了，是 0 的话索引没变，是 1 的话索引变成“原索引 +oldCap”。可以看看下图为 16 扩充为 32 的 resize 示意图： 这个设计确实非常的巧妙，既省去了重新计算 hash 值的时间，而且同时，由于新增的 1bit 是 0 还是 1 可以认为是随机的，因此 resize 的过程，均匀的把之前的冲突的节点分散到新的 bucket 了。

HashMap 的大小为什么是 2 的 n 次方大小呢？

在 JDK1.7 中，HashMap 整个扩容过程就是分别取出数组元素，一般该元素是最后一个放入链表中的元素，然后遍历以该元素为头的单向链表元素，依据每个被遍历元素的 hash 值计算其在新数组中的下标，然后进行交换。这样的扩容方式会将原来哈希冲突的单向链表尾部变成扩容后单向链表的头部。

而在 JDK 1.8 中，HashMap 对扩容操作做了优化。由于扩容数组的长度是 2 倍关系，所以对于假设初始 tableSize = 4 要扩容到 8 来说就是 0100 到 1000 的变化（左移一位就是 2 倍），在扩容中只用判断原来的 hash 值和左移动的一位（newtable 的值）按位与操作是 0 或 1 就行，0 的话索引不变，1 的话索引变成原索引加上扩容前数组。

之所以能通过这种“与运算“来重新分配索引，是因为 hash 值本来就是随机的，而 hash 按位与上 newTable 得到的 0（扩容前的索引位置）和 1（扩容前索引位置加上扩容前数组长度的数值索引处）就是随机的，所以扩容的过程就能把之前哈希冲突的元素再随机分布到不同的索引中去。

Hashmap 和 Hashtable 有什么不一样的？Hashmap 一般怎么用？

• HashMap 线程不安全，效率高一点，可以存储 null 的 key 和 value，null 的 key 只能有一个，null 的 value 可以有多个。默认初始容量为 16，每次扩充变为原来 2 倍。创建时如果给定了初始容量，则扩充为 2 的幂次方大小。底层数据结构为数组 + 链表，插入元素后如果链表长度大于阈值（默认为 8），先判断数组长度是否小于 64，如果小于，则扩充数组，反之将链表转化为红黑树，以减少搜索时间。
• HashTable 线程安全，效率低一点，其内部方法基本都经过 synchronized 修饰，不可以有 null 的 key 和 value。默认初始容量为 11，每次扩容变为原来的 2n+1。创建时给定了初始容量，会直接用给定的大小。底层数据结构为数组 + 链表。它基本被淘汰了，要保证线程安全可以用 ConcurrentHashMap。

ConcurrentHashMap 怎么实现的？

JDK 1.7，由 Segment 数组 + HashEntry 链表 + ReentrantLock 可重入锁 组成

在 JDK 1.7 中，ConcurrentHashMap 虽然是线程安全的，但因为它的底层实现是数组 + 链表的形式，所以在数据比较多的情况下访问是很慢的，因为要遍历整个链表，而 JDK 1.8 则使用了数组 + 链表/红黑树的方式优化了 ConcurrentHashMap 的实现，具体实现结构如下：

JDK 1.8 ConcurrentHashMap JDK 1.8 ConcurrentHashMap 主要通过 volatile + CAS 或者 synchronized 来实现的线程安全的。添加元素时首先会判断容器是否为空：

• 如果为空则使用 volatile 加 CAS 来初始化
• 如果容器不为空，则根据存储的元素计算该位置是否为空。
  • 如果根据存储的元素计算结果为空，则利用 CAS 设置该节点；
  • 如果根据存储的元素计算结果不为空，则使用 synchronized ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。 如果把上面的执行用一句话归纳的话，就相当于是 ConcurrentHashMap 通过对头结点加锁来保证线程安全的，锁的粒度相比 Segment 来说更小了，发生冲突和加锁的频率降低了，并发操作的性能就提高了。而且 JDK 1.8 使用的是红黑树优化了之前的固定链表，那么当数据量比较大的时候，查询性能也得到了很大的提升，从之前的 O(n) 优化到了 O(logn) 的时间复杂度

已经用了 synchronized，为什么还要用 CAS 呢？

ConcurrentHashMap 使用这两种手段来保证线程安全主要是一种权衡的考虑，在某些操作中使用 synchronized，还是使用 CAS，主要是根据锁竞争程度来判断的。

比如：在 putVal 中，如果计算出来的 hash 槽没有存放元素，那么就可以直接使用 CAS 来进行设置值，这是因为在设置元素的时候，因为 hash 值经过了各种扰动后，造成 hash 碰撞的几率较低，那么我们可以预测使用较少的自旋来完成具体的 hash 落槽操作。

当发生了 hash 碰撞的时候说明容量不够用了或者已经有大量线程访问了，因此这时候使用 synchronized 来处理 hash 碰撞比 CAS 效率要高，因为发生了 hash 碰撞大概率来说是线程竞争比较强烈。

ConcurrentHashMap 用了悲观锁还是乐观锁?

悲观锁和乐观锁都有用到。添加元素时首先会判断容器是否为空：

• 如果为空则使用 volatile 加 CAS （乐观锁） 来初始化。
• 如果容器不为空，则根据存储的元素计算该位置是否为空。
• 如果根据存储的元素计算结果为空，则利用 CAS（乐观锁） 设置该节点；
• 如果根据存储的元素计算结果不为空，则使用 synchronized（悲观锁） ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。

HashTable 实现

• Hashtable 的底层数据结构主要是数组加上链表，数组是主体，链表是解决 hash 冲突存在的。
• HashTable 是线程安全的，实现方式是Hashtable 的所有公共方法均采用 synchronized 关键字，当一个线程访问同步方法，另一个线程也访问的时候，就会陷入阻塞或者轮询的状态。

说一下 HashMap 和 Hashtable、ConcurrentMap 的区别

• HashMap 线程不安全，效率高一点，可以存储 null 的 key 和 value，null 的 key 只能有一个，null 的 value 可以有多个。默认初始容量为 16，每次扩充变为原来 2 倍。创建时如果给定了初始容量，则扩充为 2 的幂次方大小。底层数据结构为数组 + 链表，插入元素后如果链表长度大于阈值（默认为 8），先判断数组长度是否小于 64，如果小于，则扩充数组，反之将链表转化为红黑树，以减少搜索时间。
• HashTable 线程安全，效率低一点，其内部方法基本都经过 synchronized 修饰，不可以有 null 的 key 和 value。默认初始容量为 11，每次扩容变为原来的 2n+1。创建时给定了初始容量，会直接用给定的大小。底层数据结构为数组 + 链表。它基本被淘汰了，要保证线程安全可以用 ConcurrentHashMap。
• ConcurrentHashMap 是 Java 中的一个线程安全的哈希表实现，它可以在多线程环境下并发地进行读写操作，而不需要像传统的 HashTable 那样在读写时加锁。ConcurrentHashMap 的实现原理主要基于分段锁和 CAS 操作。它将整个哈希表分成了多 Segment（段），每个 Segment 都类似于一个小的 HashMap，它拥有自己的数组和一个独立的锁。在 ConcurrentHashMap 中，读操作不需要锁，可以直接对 Segment 进行读取，而写操作则只需要锁定对应的 Segment，而不是整个哈希表，这样可以大大提高并发性能。

Set

Set 集合通过内部的数据结构（如哈希表、红黑树等）来实现 key 的无重复。当向 Set 集合中插入元素时，会先根据元素的 hashCode 值来确定元素的存储位置，然后再通过 equals 方法来判断是否已经存在相同的元素，如果存在则不会再次插入，保证了元素的唯一性。

有序的 Set

• 有序的 Set 是 TreeSet 和 LinkedHashSet。TreeSet 是基于红黑树实现，保证元素的自然顺序。LinkedHashSet 是基于双重链表和哈希表的结合来实现元素的有序存储，保证元素添加的自然顺序
• 记录插入顺序的集合通常指的是 LinkedHashSet，它不仅保证元素的唯一性，还可以保持元素的插入顺序。当需要在 Set 集合中记录元素的插入顺序时，可以选择使用 LinkedHashSet 来实现。