我的个人博客

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

Java 集合，也叫作容器，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 、 Queue。

• List(对付顺序的好帮手): 存储的元素是有序的、可重复的。

• Set(注重独一无二的性质): 存储的元素不可重复的。

• Queue(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。

• Map(用 key 来搜索的专家): 使用键值对（key-value）存储，类似于数学上的函数 y=f(x)，“x” 代表 key，“y” 代表 value，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

集合	实现	特点
List	ArrayList
	vector	线程安全
	LinkedList
Set	HashSet
	LinkedHashSet
	TreeSet
Map	HashMap	线程不安全，key、value都可为null
	LinkedHashMap
	HashTable	线程安全，数组+链表组成的，数组是 HashTable 的主体，链表则是主要为了解决哈希冲突而存在的。HashTable 的加锁方法是给每个方法加上synchronized 关键字，不支持null键和值
	TreeMap	红黑树
	ConcurrentHashMap	Node数组+链表+红黑树实现，线程安全的（jdk1.8以前Segment锁，1.8以后volatile + CAS 或者 synchronized）

Queue

• PriorityQueue

• DelayQueue

• ArrayDeque

HashSet，TreeSet，ArrayList,LinkedList,HashMap,TreeMap 都是线程不安全的。

1 List

1.1 ArrayList和LinkedList区别

1. 底层数据结构：

   • ArrayList使用动态数组实现。它的内部是一个数组，当数组容量不足时，会自动进行扩容。
   • LinkedList使用双向链表实现。每个元素都包含一个指向前一个元素和一个指向后一个元素的引用。

2. 随机访问性能：

   • ArrayList支持快速的随机访问，因为它是基于数组的，可以通过索引直接访问元素。
   • LinkedList在随机访问时性能较差，因为必须从链表的头部或尾部开始遍历，直到找到目标元素。

3. 插入和删除操作性能：

   • ArrayList在中间插入或删除元素时性能较差，因为需要移动数组中的元素。
   • LinkedList在插入和删除元素时性能较好，因为只需要改变相邻元素的引用。

4. 空间复杂度：

   • ArrayList相对较省空间，因为它只需要存储元素值和数组容量。
   • LinkedList相对较耗费空间，因为每个元素都需要额外的两个引用字段。

5. 迭代器性能：

   • ArrayList上的迭代器性能较好，因为它可以通过索引直接访问元素。
   • LinkedList上的迭代器性能较差，因为必须沿着链表一个一个地移动。

6. 适用场景：

   • 如果需要频繁进行随机访问，使用ArrayList更为合适。
   • 如果需要频繁进行插入和删除操作，特别是在集合的中间位置，使用LinkedList更为合适。

2 Set

2.1 Comparable和Comparator

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

• Comparable 接口实际上是出自java.lang包 它有一个 compareTo(Object obj)方法用来排序

• Comparator接口实际上是出自 java.util 包它有一个compare(Object obj1, Object obj2)方法用来排序

2.2 Hashset、LinkedHashSet、TreeSet

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

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

3 Map

3.1 HashMap和TreeMap

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

3.2 HashMap

[!note]
JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突），JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间

在 JDK 1.7 版本之前， HashMap 数据结构是数组和链表，HashMap通过哈希算法将元素的键（Key）映射到数组中的槽位（Bucket）。如果多个键映射到同一个槽位，它们会以链表的形式存储在同一个槽位上，因为链表的查询时间是O(n)，所以冲突很严重，一个索引上的链表非常长，效率就很低了。

3.2.1 哈希冲突解决方式

• 链接法：使用链表或其他数据结构来存储冲突的键值对，将它们链接在同一个哈希桶中。

• 开放寻址法：在哈希表中找到另一个可用的位置来存储冲突的键值对，而不是存储在链表中。常见的开放寻址方法包括线性探测、二次探测和双重散列。

• 再哈希法（Rehashing）：当发生冲突时，使用另一个哈希函数再次计算键的哈希值，直到找到一个空槽来存储键值对。

• 哈希桶扩容：当哈希冲突过多时，可以动态地扩大哈希桶的数量，重新分配键值对，以减少冲突的概率。

3.2.2 hashcode和equals

equals相等的两个对象，hashCode一定相等。hashCode相等的两个对象，equals不一定相等

3.2.3 扩容机制

1. 初始容量和负载因子：

   • HashMap 有一个初始容量和一个负载因子。初始容量是哈希表在创建时的容量，默认为 16。负载因子是一个在哈希表大小超过其容量乘以负载因子时，哈希表将进行扩容的阈值，默认为 0.75。

2. 扩容操作：

   • 当哈希表的元素个数达到了负载因子所定义的阈值，HashMap 将进行扩容操作。
   • 扩容操作包括创建一个新的哈希表，其容量为原容量的两倍，然后将所有元素重新分配到新的哈希表中。
     HashMap的扩容机制 - 知乎 (zhihu.com)
     HashMap实现原理， 扩容机制，面试题和总结_hashmap扩容机制面试-CSDN博客

3.2.4 HashMap多线程导致死循环

当一个桶位中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束。为了解决这个问题，JDK1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。

疫苗：Java HashMap的死循环 | 酷 壳 - CoolShell

3.2.5 HashMap为什么线程不安全

多线程环境下，HashMap 扩容时会造成死循环 和数据丢失的问题。在 HashMap 中，多个键值对可能会被分配到同一个桶（bucket），并以链表或红黑树的形式存储。多个线程对HashMap的put操作会导致线程不安全，可能产生数据覆盖.
数据不一致

3.2.3.1 同时检测到桶位置为空，插入元素

• 两个线程同时进行put操作，并且存在哈希冲突

• 由于线程首先都执行完了hash碰撞的判断，桶为空

• 每个线程再向空桶中插入元素

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 {
    // ...
}

3.2.3.2 多个线程同时put操作导致size不正确

• 两个线程都先获取size，在++size

• 添加两次元素，而size只增加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) {
    // ...
    // 实际大小大于阈值则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

基于JDK8的HashMap实现(万字详解) - 知乎 (zhihu.com)

3.2.6 底层实现

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashcode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

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

3.2.7 put添加元素过程

1. 计算哈希码（Hash Code）：

   • 当你向 HashSet 中添加一个元素时，首先会调用该元素的 hashCode() 方法，得到元素的哈希码。
   • 如果元素为 null，则它的哈希码为 0。

2. 映射到桶位置（Bucket Position）：

   • 哈希码经过一系列的变换和运算，被映射到哈希表中的一个桶位置（bucket position）。
   • 桶位置是一个数组索引，表示存储元素的位置。

3. 处理哈希冲突：

   • 哈希表可能存在冲突，即不同元素映射到相同的桶位置。为了解决冲突，HashSet 使用链表或红黑树（在JDK 8之后）来存储相同桶位置上的元素。
   • 如果桶位置上已经有一个元素，新元素会被添加到链表或红黑树的末尾。

4. 检查元素唯一性：

   • 在添加元素的过程中，HashSet 会通过调用元素的 equals() 方法来检查元素的唯一性。
   • 如果已经存在相同的元素（根据 equals() 判断），新元素不会被加入。

3.2.8 如何做到让HashMap线程安全

1. 使用Collections.synchronizedMap方法：
   Map<K, V> synchronizedMap = Collections.synchronizedMap(new HashMap<K, V>());

   这将返回一个线程安全的Map，它在每个方法上都使用同步机制来确保线程安全。但请注意，虽然这确保了每个方法的原子性，但在多个操作之间，仍然可能需要额外的同步。

2. 使用ConcurrentHashMap： ConcurrentHashMap是Java提供的线程安全的Map实现。它使用分段锁机制，每个段相当于一个小的HashMap，不同的段之间互不影响，这样可以提高并发性能。

   Map<K, V> concurrentMap = new ConcurrentHashMap<K, V>();

3.3 ConcurrentHashMap

[!note]
ConcurrentHashMap：Node数组+链表+红黑树实现，线程安全的（jdk1.8以前Segment锁，1.8以后volatile + CAS 或者 synchronized）

3.3.1 JDK 1.7

Segment数组，通过分段锁（Segmentation）实现线程安全。它将整个哈希表分成多个段（Segment），每个段都是一个小的哈希表，并且拥有自己的锁。这样，多个线程可以并发地访问不同的段，从而减少了锁的竞争，提高了并发性能。

3.3.2 JDK 1.8

在 JDK 1.7 中它使用的是数组加链表的形式实现的，而数组又分为：大数组 Segment 和小数组 HashEntry。 Segment 是一种可重入锁（ReentrantLock），在 ConcurrentHashMap 里扮演锁的角色；HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组，一个 Segment 里包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素。

直接在table元素上加锁，实现对每一行进行加锁，进一步减小了并发冲突的概率。

• 对于put操作，如果Key对应的数组元素为null，则通过CAS操作（Compare and Swap）将其设置为当前值。

• 如果Key对应的数组元素（也即链表表头或者树的根元素）不为null，则对该元素使用 synchronized 关键字申请锁，然后进行操作。

• 如果该 put 操作使得当前链表长度超过一定阈值，则将该链表转换为红黑树，从而提高寻址效率。

使用了一种更细粒度的锁策略，结合CAS（Compare-and-Swap）无锁算法来实现线程安全。在JDK 1.8中，ConcurrentHashMap将整个哈希表看作一个整体，不再进行分段。而是通过Node数组+链表+红黑树的结构来存储数据，并使用Synchronized和CAS来协调并发访问。

锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，就不会影响其他 Node 的读写，效率大幅提升。

3.3.3 JDK 1.7 和 JDK 1.8 的 ConcurrentHashMap 实现有什么不同？

• 线程安全实现方式：JDK 1.7 采用 Segment 分段锁来保证安全， Segment 是继承自 ReentrantLock。JDK1.8 放弃了 Segment 分段锁的设计，采用 Node + CAS + synchronized 保证线程安全，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点。

• Hash 碰撞解决方法 : JDK 1.7 采用拉链法，JDK1.8 采用拉链法结合红黑树（链表长度超过一定阈值时，将链表转换为红黑树）。

• 并发度：JDK 1.7 最大并发度是 Segment 的个数，默认是 16。JDK 1.8 最大并发度是 Node 数组的大小，并发度更大。

ConcurrentHashMap 源码分析 | JavaGuide
一文彻底搞懂CAS实现原理 & 深入到CPU指令 - 知乎 (zhihu.com)
Java集合常见面试题总结(下) | JavaGuide

4 Atomic

java.util.concurrent.atomic 包提供了一组用于在多线程环境中进行原子操作的类。这些类通过使用硬件级别的原子性操作或者利用 sun.misc.Unsafe 提供的 CAS（Compare-And-Swap）操作来确保对变量的操作是原子的。这些类大多数都是基于原始数据类型的，例如 int、long，还有一些是引用类型。

以下是 java.util.concurrent.atomic 包中一些主要的类以及它们的用途：

1. AtomicInteger： 用于对整数进行原子操作，支持原子的自增（incrementAndGet()）、自减（decrementAndGet()）等操作。

2. AtomicLong： 用于对长整型进行原子操作，同样支持原子的自增、自减等操作。

3. AtomicBoolean： 用于对布尔类型进行原子操作，支持原子的设置和获取操作。

4. AtomicReference： 用于对引用类型进行原子操作，支持原子的获取和设置引用对象。

5. AtomicIntegerArray、AtomicLongArray、AtomicReferenceArray： 用于对数组中的元素进行原子操作，提供了一些原子性的数组操作。

6. AtomicIntegerFieldUpdater、AtomicLongFieldUpdater、AtomicReferenceFieldUpdater： 用于对类的字段进行原子更新，允许在并发环境中对对象的字段进行原子性操作。

这些原子类提供了一种比使用 synchronized 关键字更轻量级的线程安全机制，特别适用于一些简单的计数器、状态标志等场景。在需要进行原子操作而又不需要全局的锁的情况下，这些类可以提供更好的性能。

虽然这些类提供了原子性的操作，但并不是所有的操作都可以用原子方式完成，因此在使用时仍然需要注意保证原子性的操作是否符合预期。