1 汇总
1.1 [1]图示
01.第1类
Collection
├── List
│ ├── ArrayList
│ │ ├── 排列有序，可重复
│ │ ├── 底层使用数组
│ │ ├── 速度快，增删慢，getter()和setter()方法快
│ │ ├── 线程不安全
│ │ └── 当容量不够时，ArrayList默认当前容量*1.5 + 1
│ ├── Vector
│ │ ├── 排列有序，可重复
│ │ ├── 底层使用数组
│ │ ├── 速度快，增删慢
│ │ ├── 线程安全，效率低
│ │ └── 当容量不够时，Vector默认扩展一倍容量
│ ├── LinkedList
│ │ ├── 排列有序，可重复
│ │ ├── 底层使用双向链表数据结构
│ │ ├── 适合增删、增删快，add()和remove()方法快
│ │ └── 线程不安全
│ └── CopyOnWriteArrayList
│ ├── 排列有序，可重复
│ ├── 底层使用数组
│ ├── 适合读多写少的场景
│ ├── 线程安全
│ └── 写操作时复制整个数组
├── Set
│ ├── HashSet
│ │ ├── 排列无序，不可重复
│ │ ├── 底层用Hash表实现
│ │ ├── 查找速度快
│ │ └── 内部是HashMap
│ ├── TreeSet
│ │ ├── 排序有序，不可重复
│ │ ├── 底层使用红黑树实现
│ │ ├── 排序存储
│ │ └── 内部是TreeMap的SortedSet
│ ├── LinkedHashSet
│ │ ├── 采用Hash表存储，并用双向链表记录插入顺序
│ │ └── 内部是LinkedHashMap
│ └── CopyOnWriteArraySet
│ ├── 排列无序，不可重复
│ ├── 底层使用CopyOnWriteArrayList
│ ├── 适合读多写少的场景
│ └── 线程安全
└── Queue
├── BlockingQueue (阻塞队列)
│ ├── ArrayBlockingQueue
│ │ ├── 基于数组实现
│ │ ├── 有界队列
│ │ ├── 单锁(可选公平/非公平)
│ │ └── 适用于生产者-消费者模型
│ ├── LinkedBlockingQueue
│ │ ├── 基于链表实现
│ │ ├── 可有界或无界
│ │ ├── 双锁(入队/出队分离)
│ │ └── 适用于高并发场景
│ ├── PriorityBlockingQueue
│ │ ├── 基于优先级堆
│ │ ├── 无界队列
│ │ ├── 支持优先级排序
│ │ └── 适用于优先级处理场景
│ ├── DelayQueue
│ │ ├── 基于优先级堆
│ │ ├── 无界队列
│ │ ├── 支持延迟获取
│ │ └── 适用于延迟任务处理
│ ├── SynchronousQueue
│ │ ├── 容量为零
│ │ ├── 插入需等待移除
│ │ └── 适用于严格同步场景
│ ├── LinkedTransferQueue
│ │ ├── 基于链表实现
│ │ ├── 无界队列
│ │ ├── 支持生产者等待
│ │ └── 适用于传输场景
│ └── LinkedBlockingDeque
│ ├── 基于链表实现
│ ├── 可有界或无界
│ ├── 支持双端操作
│ └── 适用于双端并发场景
└── NonBlockingQueue (非阻塞队列)
├── ConcurrentLinkedQueue
│ ├── 基于链表实现
│ ├── 无界队列
│ ├── 使用CAS操作
│ └── 适用于高并发场景
├── ConcurrentLinkedDeque
│ ├── 基于链表实现
│ ├── 无界队列
│ ├── 支持双端操作
│ └── 适用于双端并发场景
├── ConcurrentSkipListQueue
│ ├── 基于跳表实现
│ ├── 无界队列
│ ├── 支持有序性
│ └── 适用于有序并发场景
├── PriorityQueue
│ ├── 基于优先级堆
│ ├── 无界队列
│ ├── 支持优先级排序
│ └── 适用于优先级场景
├── LinkedList
│ ├── 基于双向链表
│ ├── 无界队列
│ ├── 支持双端操作
│ └── 适用于双端操作场景
└── ArrayDeque
├── 基于数组实现
├── 无界队列
├── 支持双端操作
└── 适用于双端操作场景
02.第2类
Map
├── HashMap
│ ├── 键不可重复，值可重复
│ ├── 底层用哈希表
│ ├── 线程不安全
│ └── 允许key和value为null
├── Hashtable
│ ├── 键不可重复，值可重复
│ ├── 底层哈希表
│ ├── 线程安全
│ └── key和value都不允许为null
├── TreeMap
│ ├── 键不可重复，值可重复
│ ├── 底层是红黑树
│ ├── 排序存储
│ └── 线程不安全
├── LinkedHashMap
│ ├── 键不可重复，值可重复
│ ├── 底层用哈希表和双向链表
│ ├── 保证插入顺序或访问顺序
│ └── 线程不安全
├── ConcurrentHashMap
│ ├── 键不可重复，值可重复
│ ├── 底层用哈希表
│ ├── 线程安全
│ └── 不允许key和value为null
└── WeakHashMap
├── 键不可重复，值可重复
├── 底层用哈希表
├── 使用弱引用键
└── 线程不安全
1.2 [1]集合框架：2类
01.Collection
a.List：有序，可以重复
a.分类1
ArrayList 数组的形式存储 连续的内存存储 查找快，插入/删除慢
LinkedList 链表的形式存储 非连续的内存存储 查找慢，插入/删除快
Vector 数组的形式存储 连续的内存存储
b.分类2
ArrayList 删除中间的元素的时候会把删除元素的后面的元素往前移动 线程不安全，效率高
LinkedList 链式存储，无法根据偏移量计算出下一个元素的位置，需要追历才能找到 线程不安全，效率高
Vector 线程安全，效率低
b.Set：无序，不可以重复
HashSet HashXxx：底层借助了"哈希表"的数据结构，默认不支持排序
TreeSet TreeXxx：底层借助了"红黑树"的数据结构，默认支持"排序"
LinkedHashSet HashXxx：底层借助了"哈希表"的数据结构，默认不支持排序
c.Queue
ArrayBlockingQueue 基于【数组】，内部实现只用了一把锁，可以指定公平或者非公平锁
LinkedBlockingQueue： 基于【链表】，内部实现用了两把锁，take一把、put一把，所以入队和出队这两个操作是可以并行的，从这里看并发度应该比ArrayBlockingQueue高
PriorityBlockingQueue 支持优先级排序的无界阻塞队列
DelayQueue 支持延迟获取元素的无界阻塞队列
SynchronousQueue 容量为零的阻塞队列，每次插入操作必须等待对应的移除操作
02.Map
a.分类1
HashMap 查找快，插入/删除慢
HashTable
LinkedHashMap 查找慢，插入/删除快
TreeMap
b.分类2
HashMap HashXxx：底层借助了"哈希表"的数据结构，默认不支持排序 乱序 线程不安全，效率高
HashTable HashXxx：底层借助了"哈希表"的数据结构，默认不支持排序 线程安全，效率低
LinkedHashMap 顺序 线程不安全，效率高
TreeMap TreeXxx：底层借助了"红黑树"的数据结构，默认支持"排序" 线程不安全，效率高
1.3 [2]Map接口不继承Collection接口
01.Map接口为什么不继承Collection接口？
a.回答
Map继承Collection毫无意义
b.说明
尽管Map接口和它的实现也是集合框架的一部分，但Map不是集合，集合也不是Map
因此，【Map继承Collection毫无意义】，反之亦然
1.4 [2]List、Set
01.List和Set区别？
a.不同点1
List，Set都是继承自 Collection 接口
List：元素有放入顺序，元素可重复
Set：元素无放入顺序，元素不可重复，重复元素会覆盖掉
b.不同点2
Set：检索指定的元素效率高，删除和插入效率高，插入和删除可能会引起元素位置改变
List：和数组类似，List 可以动态增长，查找指定的元素效率低，插入删除指定的元素效率低，因为可能会引起其他元素位置改变
如果是随机访问（指定下标），则List会快于Set
02.图示
特性 List Set
元素顺序 保持插入顺序 不保证顺序
可以通过索引访问元素 具体顺序取决于实现类
元素唯一性 允许重复元素 不允许重复元素
访问元素 通过索引访问元素，时间复杂度为 O(1) 通过元素值访问，时间复杂度取决于实现类
例如 ArrayList 例如 HashSet 为 O(1)，TreeSet 为 O(log n)
插入和删除操作 插入和删除操作时间复杂度取决于实现类 插入和删除操作时间复杂度取决于实现类
例如 ArrayList 为 O(n)，LinkedList 为 O(1) 例如 HashSet 为 O(1)，TreeSet 为 O(log n)
适用场景 需要保持元素顺序和允许重复元素的场景 需要唯一元素集合的场景
例如有序列表 例如集合运算、唯一性检查
线程安全性 非线程安全 非线程安全
可使用 Collections.synchronizedList 可使用 Collections.synchronizedSet
包装为线程安全 包装为线程安全
常见实现类 ArrayList、LinkedList HashSet、TreeSet、LinkedHashSet
1.5 [2]List、Map
01.List和Map区别？
List是对象集合，允许对象重复
Map是键值对的集合，不允许key重复
02.图示
特性 List Set
元素顺序 保持插入顺序 不保证顺序
可以通过索引访问元素 具体顺序取决于实现类
元素唯一性 允许重复元素 不允许重复元素
访问元素 通过索引访问元素，时间复杂度为 O(1) 通过元素值访问，时间复杂度取决于实现类
例如 ArrayList 例如 HashSet 为 O(1)，TreeSet 为 O(log n)
插入和删除操作 插入和删除操作时间复杂度取决于实现类 插入和删除操作时间复杂度取决于实现类
例如 ArrayList 为 O(n)，LinkedList 为 O(1) 例如 HashSet 为 O(1)，TreeSet 为 O(log n)
适用场景 需要保持元素顺序和允许重复元素的场景 需要唯一元素集合的场景
例如有序列表 例如集合运算、唯一性检查
线程安全性 非线程安全 非线程安全
可使用 Collections.synchronizedList 可使用 Collections.synchronizedSet
包装为线程安全 包装为线程安全
常见实现类 ArrayList、LinkedList HashSet、TreeSet、LinkedHashSet
1.6 [3]Array、ArrayList
01.Array和ArrayList有何区别？
Array可以容纳基本类型和对象，而ArrayList只能容纳对象
Array是指定大小的，而ArrayList大小是固定的，可自动扩容
Array没有提供ArrayList那么多功能，比如addAll、removeAll和iterator等
02.图示
特性 Array ArrayList
大小 固定大小 动态大小
在创建时指定，不能改变 可以根据需要自动调整大小
性能 访问元素时间复杂度为 O(1) 访问元素时间复杂度为 O(1)
插入和删除操作时间复杂度为 O(n) 插入和删除操作时间复杂度为 O(n)
类型 可以存储基本数据类型和对象 只能存储对象
初始化 需要显式初始化 自动初始化
内置方法 没有内置方法 提供丰富的内置方法，如 add、
remove、size 等
线程安全性 非线程安全 非线程安全
可使用 Collections.synchronizedList
包装为线程安全
内存使用 内存使用效率高 内存使用效率较低
适用场景 需要固定大小的数组 需要动态调整大小的列表
和高效的内存使用 和丰富的内置方法
1.7 [3]ArrayList、LinkedList
01ArrayList和LinkedList区别？
a.线程
ArrayList：线程不安全
LinkedList：线程不安全
b.底层
ArrayList：数组
LinkedList：双向链表
c.访问元素
ArrayList：访问元素更快，适合频繁随机访问
LinkedList：访问元素较慢，不适合频繁随机访问
d.插入和删除元素
ArrayList：插入和删除较慢，适合不频繁插入和删除的场景
LinkedList：插入和删除更快，适合频繁插入和删除的场景
e.内存占用
ArrayList：使用连续内存，空间利用率高
LinkedList：由于存储额外的指针，内存开销较大
f.扩容
ArrayList：需要动态扩容，扩容是一个耗时操作
LinkedList：不需要扩容，但由于链表结构，可能会导致更多的内存碎片
02.图示
特性 ArrayList LinkedList
底层数据结构 动态数组 双向链表
访问元素 访问元素时间复杂度为 O(1) 访问元素时间复杂度为 O(n)
插入和删除操作 插入和删除操作时间复杂度为 O(n) 插入和删除操作时间复杂度为 O(1)
内存使用 内存使用效率较高 内存使用效率较低
但需要连续内存块 但不需要连续内存块
适用场景 需要频繁访问元素的场景 需要频繁插入和删除元素的场景
例如随机访问 例如队列、双端队列
线程安全性 非线程安全 非线程安全
可使用 Collections.synchronizedList 可使用 Collections.synchronizedList
包装为线程安全 包装为线程安全
内置方法 提供丰富的内置方法，如 add、 提供丰富的内置方法，如 add、
remove、size 等 remove、size、addFirst、addLast等
内存消耗 较低 较高
由于数组需要预分配空间 由于链表节点需要额外的存储空间
1.8 [4]HashSet、TreeSet
01.HashSet和TreeSet区别？
a.HashSet
用一个 hash 表来实现的
因此，它的元素是无序的。添加，删除和 HashSet 包括的方法的持续时间复杂度是 O(1)
b.TreeSet
用一个树形结构实现的
因此，它是有序的。添加，删除和 TreeSet 包含的方法的持续时间复杂度是 O(logn)
b.图示
特性 HashSet TreeSet
底层数据结构 哈希表（HashMap） 红黑树（Red-Black Tree）
元素顺序 不保证顺序 保证元素的自然顺序或自定义顺序
性能 插入、删除、查找操作时间复杂度为 O(1) 插入、删除、查找操作时间复杂度O(log n)
是否允许 null 元素 允许一个 null 元素 不允许 null 元素
线程安全性 非线程安全， 非线程安全
适用场景 需要快速查找、插入和删除操作的场景 需要有序集合，且需要按自然顺序或自定义顺序排序的场景
1.9 [4]HashSet、HashMap
01.HashSet和HashMap区别？
a.HashSet
Set 是线性结构，值不能重复
HashSet 是 Set 的 hash 实现，HashSet 中值不能重复是用 HashMap 的 key 来实现的
b.HashMap
Map 是键值对映射，可以空键空值
HashMap 是 Map 的 hash 实现，key 的唯一性是通过 key 值 hashcode 的唯一来确定，value 值是则是链表结构
c.图示
不同点 HashMap HashSet
实现的接口 Map接口 Set接口
存储方式 存储键值对 存储对象
存储方法 使用put函数 使用add函数
性能高低 快，因为使用唯一的键来获取对象 慢
默认初始化容量 16 低
哈希值 使用键对象计算哈希值 使用成员对象计算哈希值
1.10 [4]HashMap、HashTable
01.HashMap和Hashtable区别？
a.初始化容量不同
hashmap：HashMap 的初始容量为：16
hashtable：Hashtable 初始容量为：11
两者的负载因子默认都是：0.75
b.扩容机制不同
hashmap：已用容量>总容量 * 负载因子时，HashMap 扩容规则为当前容量翻倍
hashtable：已用容量>总容量 * 负载因子时，Hashtable 扩容规则为当前容量翻倍 +1
c.支持的遍历种类不同
hashmap：HashMap只支持Iterator遍历
hashtable：HashTable支持Iterator和Enumeration两种方式遍历
d.同步性不同
hashmap：HashMap是一个不同步的Map，这意味着HashMap不是线程安全的，如果没有适当的同步代码，则无法在多个线程之间共享
hashtable：Hashtable是一个同步的Map，Hashtable是线程安全的，可以在多个线程之间共享。如果您需要使用同步的 Map，Hashtable 比在同步包装器中使用 HashMap 更快
e.线程安全
hashmap：线程不安全，性能比hashtable高一点
hashtable：线程安全
f.null值
hashmap：允许使用null作为key或value
hashtable：不允许使用null作为key和value，如果试图把null值放进Hashtable中，将会引发空指针异常，但HashMap可以
02.图示
特性 HashMap Hashtable
线程安全性 非线程安全 线程安全
可使用 Collections.synchronizedMap 使用内置 synchronized 方法
键和值是否允许 null 允许 null 键和值 不允许 null 键和值
性能 较高 较低
因为没有同步开销 因为所有方法都同步
初始容量和扩容机制 默认初始容量为 16，扩容时容量为原来的两倍 默认初始容量为 11，扩容时容量为原来的两倍加1
负载因子默认为 0.75 负载因子默认为 0.75
底层数据结构 哈希表（数组 + 链表/红黑树） 哈希表（数组 + 链表）
迭代器一致性 弱一致性 强一致性
在迭代过程中，如果有其他线程修改了集合， 在迭代过程中，不允许修改集合，否则抛出
迭代器不会抛出 ConcurrentModificationException ConcurrentModificationException
但不保证实时一致性
适用场景 适用于非线程安全的环境 适用于线程安全的环境
需要高性能的场景 需要线程安全的场景
1.11 [4]HashMap、LinkedHashMap
01.HashMap和LinkedHashMap区别？
a.迭代顺序
HashMap：不保证键值对的顺序，迭代时的顺序可能与插入顺序不同。
LinkedHashMap：维护键值对的插入顺序，迭代时按插入顺序或最近访问顺序（如果开启了访问顺序模式）。
b.底层实现
HashMap：基于哈希表实现，不维护元素的顺序。
LinkedHashMap：继承自 HashMap，但使用双向链表来维护插入顺序或访问顺序。
c.性能
HashMap：略快于 LinkedHashMap，因为它不维护顺序。
LinkedHashMap：由于维护了顺序，在插入和删除操作时可能稍慢。
d.用途
HashMap：适用于不需要维护顺序的场景。
LinkedHashMap：适用于需要维护插入顺序或访问顺序的场景，如实现 LRU 缓存。
02.图示
特性 HashMap LinkedHashMap
底层数据结构 哈希表（数组 + 链表/红黑树） 哈希表（数组 + 链表/红黑树）+ 双向链表
元素顺序 不保证顺序 保证插入顺序或访问顺序
访问顺序 不维护访问顺序 可选择维护访问顺序
性能 较高 较高，但略低于 HashMap
因为没有维护顺序的开销 因为维护顺序的开销
键和值是否允许 null 允许 null 键和值 允许 null 键和值
线程安全性 非线程安全 非线程安全
可使用 Collections.synchronizedMap 可使用 Collections.synchronizedMap
初始容量和扩容机制 默认初始容量为 16，扩容时容量为原来的两倍 默认初始容量为 16，扩容时容量为原来的两倍
负载因子默认为 0.75 负载因子默认为 0.75
迭代器一致性 弱一致性 弱一致性
在迭代过程中，如果有其他线程修改了集合， 在迭代过程中，如果有其他线程修改了集合
迭代器不会抛出 ConcurrentModificationException 迭代器不会抛出 ConcurrentModificationException
但不保证实时一致性 但不保证实时一致性
适用场景 适用于不需要维护顺序的场景 适用于需要维护插入顺序或访问顺序的场景
1.12 [4]HashMap、LinkedHashMap、TreeMap
01.图示
特性 HashMap LinkedHashMap TreeMap
底层数据结构 哈希表（数组 + 链表/红黑树） 哈希表（数组 + 链表/红黑树）+ 双向链表 红黑树（Red-Black Tree）
元素顺序 不保证顺序 保证插入顺序或访问顺序 保证元素的自然顺序或自定义顺序
访问顺序 不维护访问顺序 可选择维护访问顺序 维护元素的自然顺序或自定义顺序
性能 较高 较高，但略低于 HashMap 插入、删除、查找操作时间复杂度
因为没有维护顺序的开销 因为维护顺序的开销 为 O(log n)
键和值是否允许 null 允许 null 键和值 允许 null 键和值 不允许 null 键和值
线程安全性 非线程安全 非线程安全 非线程安全
可使用 Collections.synchronizedMap 可使用 Collections.synchronizedMap 可使用 Collections.synchronizedMap
初始容量和扩容机制 默认初始容量为 16，扩容时容量为原来的两倍 默认初始容量为 16，扩容时容量为原来的两倍 初始容量根据需要动态调整
负载因子默认为 0.75 负载因子默认为 0.75 负载因子默认为 0.75
迭代器一致性 弱一致性 弱一致性 弱一致性
在迭代过程中，如果有其他线程修改了集合， 在迭代过程中，如果有其他线程修改了集合， 在迭代过程中，如果有其他线程修改了集合，
迭代器不会抛出 ConcurrentModificationException 迭代器不会抛出 ConcurrentModificationException 迭代器不会抛出 ConcurrentModificationException|
但不保证实时一致性 但不保证实时一致性 但不保证实时一致性
适用场景 适用于不需要维护顺序的场景 适用于需要维护插入顺序或访问顺序的场景 适用于需要有序集合的场景
需要高性能的场景 例如缓存实现 例如按自然顺序或自定义顺序排序
1.13 [4]HashMap、ConcurrentHashMap
01.HashMap、ConcurrentHashMap区别
1.除了加锁，原理上无太大区别
2.HashMap键值对：允许有null
ConCurrentHashMap键值对：都不允许为null
02.图示
特性 HashMap ConcurrentHashMap
线程安全性 非线程安全 线程安全
可使用 Collections.synchronizedMap包装为线程安全 使用分段锁和 CAS 操作确保线程安全
键和值是否允许 null 允许 null 键和值 不允许 null 键和值
性能 较高 高并发性能
适用于单线程或低并发环境 适用于高并发环境
初始容量和扩容机制 默认初始容量为 16，扩容时容量为原来的两倍 默认初始容量为 16，扩容时容量为原来的两倍
负载因子默认为 0.75 负载因子默认为 0.75
底层数据结构 哈希表（数组 + 链表/红黑树） 哈希表（数组 + 链表/红黑树）
迭代器一致性 弱一致性 弱一致性
在迭代过程中，如果有其他线程修改了集合， 在迭代过程中，如果有其他线程修改了集合，
迭代器不会抛出 ConcurrentModificationException 迭代器不会抛出 ConcurrentModificationException
但不保证实时一致性 但不保证实时一致性
适用场景 适用于非线程安全的环境 适用于高并发环境
需要高性能的场景 需要线程安全和高并发性能的场景
2 汇总2
2.1 [1]线程安全：4种
01.线程安全
a.方式1：使用同步包装器
使用Collections.synchronizedList() 或 Collections.synchronizedMap()
List<Integer> list = Collections.synchronizedList(new ArrayList<>());
Map<Integer, String> map = Collections.synchronizedMap(new HashMap<>());
b.方式2：使用线程安全的集合
使用CopyOnWriteArrayList替代ArrayList或LinkedList
使用ConcurrentHashMap替代HashMap或LinkedHashMap
c.方式3：手动加锁
使用synchronized或ReentrantLock（可重入锁）来手动控制线程访问
d.方式4：使用Java 8 Stream并行操作
对于【只读】操作，可以使用Java8的Stream API进行并行处理
02.线程安全
a.CopyOnWriteArrayList
a.说明
Collections.synchronizedList(list); ArrayList默认容量10，扩容为1.5倍
b.原理
写时复制（Copy-On-Write，简称COW）
这个机制的核心思想在于，当需要修改数据时，不直接操作原始数据，而是先复制一份原始数据，在副本上进行修改，最后再将修改后的副本替换原始数据
CopyOnWriteArrayList并不是完全意义上的线程安全，【如果涉及到remove操作，一定要谨慎处理】
b.ConcurrentHashSet（hutool）
a.说明
Collections.synchronizedSet(set);
b.原理
略
c.ConcurrentHashMap（java.util.concurrent）
a.说明
Collections.synchronizedMap(map); HashMap默认容量16，负载因子默认0.75，已用容量>总容量*负载因子时，HashMap扩容规则为当前容量翻倍
b.原理
写时复制（Copy-On-Write，简称COW）
当对CopyOnWriteArraySet进行写入操作时，会先将原数组复制一份，然后将修改操作在新数组上执行，最后将新数组替换为原数组
这样，多个线程可以同时对原数组进行读取操作，而不会出现线程冲突和数据不一致的问题
2.2 [1]线程安全：List方法
00.汇总
Vector 线程安全，但性能较低
CopyOnWriteArrayList 适用于读多写少的场景
Collections.synchronizedList 简单易用，但性能较低
Synchronized Collections from Guava 提供了线程安全的集合类，使用方便，但性能较低
01.Vector
a.功能
Vector 是一种线程安全的 List 实现，通过在所有方法上添加同步锁来确保线程安全
是 ArrayList 的线程安全版本
b.详细介绍
通过在所有方法上添加 synchronized 关键字实现线程安全
每次对 Vector 的操作（如 add、get、remove 等）都需要获取对象级别的锁
c.优点
线程安全，适用于小规模并发访问
d.缺点
性能较低，因为所有访问方法都需要获取同步锁，导致较高的锁竞争
e.使用示例
import java.util.Vector;
public class VectorExample {
public static void main(String[] args) {
Vector<String> vector = new Vector<>();
// 插入元素
vector.add("one");
vector.add("two");
// 获取元素
for (String element : vector) {
System.out.println(element);
}
}
}
02.CopyOnWriteArrayList
a.功能
CopyOnWriteArrayList 是一种线程安全的 List 实现，通过在每次修改操作时创建一个新的底层数组来实现线程安全
b.详细介绍
在进行写操作（如 add、set、remove 等）时，会创建一个新的底层数组，并在新数组上进行修改操作
修改完成后，将新数组替换为底层数组
适用于读多写少的场景
c.优点
读操作无锁，提供了高效的并发读操作
d.缺点
写操作需要复制整个数组，开销较大，不适用于写操作频繁的场景
e.使用示例
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class CopyOnWriteArrayListWithLockExample {
public static void main(String[] args) {
List<String> list = new CopyOnWriteArrayList<>();
Lock lock = new ReentrantLock();
// 添加元素
list.add("one");
list.add("two");
list.add("three");
// 读取元素
for (String element : list) {
System.out.println(element);
}
// 修改元素
list.set(1, "two updated");
// 删除元素
list.remove("three");
// 读取元素
for (String element : list) {
System.out.println(element);
}
// 在迭代过程中进行 remove 操作，使用显式锁确保线程安全
lock.lock();
try {
for (String element : list) {
if ("two updated".equals(element)) {
list.remove(element); // 使用显式锁确保线程安全
}
}
} finally {
lock.unlock();
}
// 读取元素
for (String element : list) {
System.out.println(element);
}
}
}
03.Collections.synchronizedList
a.功能
Collections.synchronizedList 方法可以将一个普通的 List 包装成线程安全的 List
b.详细介绍
使用方法级别的同步，即在每个方法上使用 synchronized 关键字
确保线程安全，但导致较高的锁竞争，尤其在高并发环境下
c.优点
简单易用，适用于小规模并发访问
d.缺点
性能较低，因为所有访问方法都需要获取同步锁
e.使用示例
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SynchronizedListExample {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
List<String> synchronizedList = Collections.synchronizedList(list);
// 插入元素
synchronizedList.add("one");
synchronizedList.add("two");
// 获取元素
synchronized (synchronizedList) {
for (String element : synchronizedList) {
System.out.println(element);
}
}
}
}
04.Synchronized Collections from Guava
a.功能
Google Guava 提供了一些线程安全的集合类，可以通过 Lists.synchronizedList 方法创建线程安全的 List
b.详细介绍
Guava 提供了 Lists.synchronizedList 方法，可以将一个普通的 List 包装成线程安全的 List
确保线程安全，但导致较高的锁竞争
c.优点
提供了线程安全的集合类，使用方便
d.缺点
性能较低，因为所有访问方法都需要获取同步锁
e.使用示例
import com.google.common.collect.Lists;
import java.util.List;
public class GuavaSynchronizedListExample {
public static void main(String[] args) {
List<String> list = Lists.newArrayList();
List<String> synchronizedList = Lists.synchronizedList(list);
// 插入元素
synchronizedList.add("one");
synchronizedList.add("two");
// 获取元素
synchronized (synchronizedList) {
for (String element : synchronizedList) {
System.out.println(element);
}
}
}
}
2.3 [1]线程安全：Map方法
00.总结
ReadWriteLock 读写分离的线程安全Map，提高并发性能
ConcurrentHashMap ConcurrentMap接口，【synchronized/ReentrantLock】确保迭代remove的线程安全
ConcurrentSkipListMap ConcurrentMap接口，线程安全且有序的Map，适用于需要键有序的场景
Collections.synchronizedMap 简单易用，但性能较低
01.ReadWriteLock
a.功能
使用ReadWriteLock可以实现读写分离的线程安全Map
b.详细介绍
提供了读写分离的锁机制，读操作使用读锁，写操作使用写锁
读锁是共享锁，多个线程可以同时获取读锁进行读操作
写锁是独占锁，同一时刻只有一个线程可以获取写锁进行写操作
c.优点
读写分离，提高并发性能
适用于读多写少的场景
d.缺点
实现较为复杂，需要手动管理锁
e.使用示例
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
public class ReadWriteLockMapExample {
private final Map<String, Integer> map = new HashMap<>();
private final ReadWriteLock lock = new ReentrantReadWriteLock();
public void put(String key, Integer value) {
lock.writeLock().lock();
try {
map.put(key, value);
} finally {
lock.writeLock().unlock();
}
}
public Integer get(String key) {
lock.readLock().lock();
try {
return map.get(key);
} finally {
lock.readLock().unlock();
}
}
public static void main(String[] args) {
ReadWriteLockMapExample example = new ReadWriteLockMapExample();
example.put("one", 1);
System.out.println("Value for key 'one': " + example.get("one"));
}
}
02.ConcurrentHashMap
a.功能
ConcurrentHashMap是一个线程安全的Map
b.详细介绍
提供了线程安全的Map操作方法，如putIfAbsent、remove、replace等
c.优点
提供了线程安全的Map操作方法
适用于高并发环境
d.缺点
需要选择具体的实现类，如 ConcurrentHashMap 或 ConcurrentSkipListMap。
e.使用示例
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
public class ConcurrentMapExample {
public static void main(String[] args) {
ConcurrentMap<String, Integer> map = new ConcurrentHashMap<>();
// 插入键值对
map.put("one", 1);
map.put("two", 2);
// 获取值
System.out.println("Value for key 'one': " + map.get("one"));
// 使用 putIfAbsent 方法
map.putIfAbsent("three", 3);
System.out.println("Value for key 'three': " + map.get("three"));
// 使用 replace 方法
map.replace("one", 10);
System.out.println("Updated value for key 'one': " + map.get("one"));
}
}
03.ConcurrentSkipListMap
a.功能
ConcurrentSkipListMap是一个线程安全的有序Map，基于跳表（Skip List）实现
b.详细介绍
通过跳表实现，支持高效的并发访问
跳表是一种平衡数据结构，能够在 O(log n) 时间复杂度内进行插入、删除和查找操作
保证键的有序性，适用于需要有序键的场景
c.优点
支持高效的并发访问
保证键的有序性
d.缺点
在某些场景下性能可能稍低于 ConcurrentHashMap
e.使用示例
import java.util.concurrent.ConcurrentSkipListMap;
public class ConcurrentSkipListMapExample {
public static void main(String[] args) {
ConcurrentSkipListMap<String, Integer> map = new ConcurrentSkipListMap<>();
// 插入键值对
map.put("one", 1);
map.put("two", 2);
// 获取值
System.out.println("Value for key 'one': " + map.get("one"));
}
}
04.Collections.synchronizedMap
a.功能
Collections.synchronizedMap方法可以将一个普通的Map包装成线程安全的Map
通过在所有访问方法上添加同步锁来确保线程安全
b.详细介绍
使用方法级别的同步，即在每个方法上使用synchronized关键字
确保线程安全，但导致较高的锁竞争，尤其在高并发环境下
c.优点
简单易用，适用于小规模并发访问
d.缺点
性能较低，因为所有访问方法都需要获取同步锁
e.使用示例
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
public class SynchronizedMapExample {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
Map<String, Integer> synchronizedMap = Collections.synchronizedMap(map);
// 插入键值对
synchronizedMap.put("one", 1);
synchronizedMap.put("two", 2);
// 获取值
synchronized (synchronizedMap) {
System.out.println("Value for key 'one': " + synchronizedMap.get("one"));
}
}
}
2.4 [1]线程不安全：ArrayList、LinkedList、LinkedHashMap、HashMapHashMap
00.总结
链表断裂：LinkedList、LinkedHashMap
哈希桶冲突：HashMap、LinkedHashMap
死循环：HashMap（HashMap在并发执行put操作时，可能会导致形成循环链表）、LinkedHashMap
01.ArrayList、LinkedList、LinkedHashMap、HashMapHashMap线程为什么不安全
a.缺乏同步机制
这些集合类的操作方法（如 add、remove、put、get 等）都没有加锁，也没有其他同步机制来保证线程安全
在多线程环境中，多个线程可能会同时访问或修改集合的内部结构（如数组、链表等），导致数据不一致或结构损坏
b.竞态条件
多个线程同时对集合进行读写操作时，会出现竞态条件（Race Condition），导致操作结果不可预测
c.内部结构复杂性
这些集合类的底层实现（如动态数组、链表、哈希表等）在多线程操作下容易出现状态不一致的问题
2.5 [2]list：去重
01.汇总
1.通过HashSet踢除重复元素
2.删除ArrayList中重复元素，保持顺序
3.把list里的对象遍历一遍，用list.contains()，如果不存在就放入到另外一个list集合中
4.retainAll和retainAll用法
5.用JDK1.8 Stream中对List进行去重：list.stream().distinct()
02.实现删除List集合中的重复元素？
1.通过HashSet踢除重复元素
public static List removeDuplicate(List list) {
HashSet h = new HashSet(list);
list.clear();
list.addAll(h);
return list;
}
2.删除ArrayList中重复元素，保持顺序
public static void removeDuplicateWithOrder(List list) {
Set set = new HashSet();
List newList = new ArrayList();
for (Iterator iter = list.iterator(); iter.hasNext();) {
Object element = iter.next();
if (set.add(element))
newList.add(element);
}
list.clear();
list.addAll(newList);
System.out.println( " remove duplicate " + list);
}
3.把list里的对象遍历一遍，用list.contains()，如果不存在就放入到另外一个list集合中
public static List removeDuplicate(List list){
List listTemp = new ArrayList();
for(int i=0;i<list.size();i++){
if(!listTemp.contains(list.get(i))){
listTemp.add(list.get(i));
}
}
return listTemp;
}
4.retainAll和retainAll用法
List<String> a = Arrays.asList ("a", "f", "e", "x", "w");
List<String> b = Arrays.asList ("a", "b", "c", "d");
List<String> c = null;
List<String> d = null;
c = new ArrayList(a);
c.retainAll(b); // 得到 a, b 的交集。
d = new ArrayList(a);
d.addAll(b); // 合并 a, b 值到 d 中。
d.removeAll(c);// 去掉交集 c 中的所有条目。留下只出现在a 或 b 中的条目。
System.out.println(d);
5.用JDK1.8 Stream中对List进行去重：list.stream().distinct()
List<String> a = new ArrayList<> ();
a.add("a");
a.add("b");
a.add("b");
List<String> b = new ArrayList<> ();
b.add("a");
b.add("c");
b.add("b");
a.addAll(b);
List list=(List) a.stream().distinct().collect(Collectors.toList());
System.out.println(list);
2.6 [2]list：排序
01.汇总
1.JAVA中我们可以使用java.util.Collections类的sort(List list)方法对list集合中的元素排序。
2.JDK8之后特别是lambda表达式的盛行，而且Collections的sort方法其实是调用了List接口自己的sort方法；所以可以使用List接口自己的sort方法排序
3.方式2的lambda写法
4.Stream流的sort方法写法
5.使用 Comparable 进行排序
6.使用 Comparator 进行排序
02.实现对List集合中的元素进行排序？
a.JAVA中我们可以使用java.util.Collections类的sort(List list)方法对list集合中的元素排序。
List<String> list = Arrays.asList("banana", "apple", "cherry");
Collections.sort(list);
// 排序结果: [apple, banana, cherry]
b.JDK8之后特别是lambda表达式的盛行，而且Collections的sort方法其实是调用了List接口自己的sort方法；所以可以使用List接口自己的sort方法排序
List<String> list = Arrays.asList("banana", "apple", "cherry");
list.sort(Comparator.naturalOrder());
// 排序结果: [apple, banana, cherry]
c.方式2的lambda写法
List<String> list = Arrays.asList("banana", "apple", "cherry");
list.sort((s1, s2) -> s1.compareTo(s2));
// 排序结果: [apple, banana, cherry]
d.Stream流的sort方法写法
List<String> list = Arrays.asList("banana", "apple", "cherry");
List<String> sortedList = list.stream().sorted().collect(Collectors.toList());
// 排序结果: [apple, banana, cherry]
e.使用 Comparable 进行排序
public class Person implements Comparable<Person> {
private String name;
// Constructor, getters, and setters
@Override
public int compareTo(Person other) {
return this.name.compareTo(other.name);
}
}
List<Person> list = Arrays.asList(new Person("Bob"), new Person("Alice"));
Collections.sort(list);
// 排序结果: [Alice, Bob]
f.使用 Comparator 进行排序
List<String> list = Arrays.asList("banana", "apple", "cherry");
list.sort(Comparator.reverseOrder());
// 排序结果: [cherry, banana, apple]
2.7 [2]List：交集
01.如何查找两个集合的重复数据？
a.初始化两个集合
如果两个集合中存放的都是 String 类型数据，那这个操作就会简单很多，这里先初始化一下两个集合的数据作为参考。
List<String> listA = Arrays.asList("Apple", "Banana", "Cherry", "Date");
List<String> listB = Arrays.asList("Banana", "Date", "Fig", "Grape");
b.使用 retainAll()
retainAll() 方法会修改原始的集合 A，使其只包含同时存在于集合 A 和集合 B 中的元素。
listA.retainAll(listB);
System.out.println("Elements in both lists: " + listA);
c.使用 stream() 和 filter()
使用 stream() 方法和 filter() 方法找到两个集合的交集。
List<String> intersection = listA.stream()
.filter(listB::contains)
.collect(Collectors.toList());
System.out.println("Elements in both lists: " + intersection);
d.使用 stream() 和 anyMatch()
使用 anyMatch() 检查集合 A 中的每个元素是否在集合 B 中。
-----------------------------------------------------------------------------------------------------
List<String> intersection = listA.stream()
.filter(element -> listB.stream().anyMatch(b -> b.equals(element)))
.collect(Collectors.toList());
System.out.println("Elements in both lists: " + intersection);
-----------------------------------------------------------------------------------------------------
上面的代码使用 listB.stream().anyMatch(b -> b.equals(element))。对于 listA 中的每个元素，它创建一个新的流来遍历 listB 的所有元素，直到找到相等的元素或遍历完所有元素。每次调用 anyMatch 都会遍历 listB，这同样是一个 O(n) 操作；但它在内部使用了流，这会增加额外的开销。
e.使用 Collection 的 intersection()
如果你想要获取两个集合的交集，可以使用 Collection 接口提供的 intersection() 方法。
-----------------------------------------------------------------------------------------------------
Set<String> intersectionSet = new HashSet<>(listA);
intersectionSet.retainAll(listB);
List<String> intersection = new ArrayList<>(intersectionSet);
System.out.println("Elements in both lists: " + intersection);
f.查询集合 B 中不与集合 A 重合的数据
这时候如果要查询包含集合 B 中不与集合 A 重合的数据，我们只要简单修改一下上面的方法即可，我们还是使用 Java 8 的 Stream API 来创建一个新的集合，这个集合包含集合 B 中独有的元素。
-----------------------------------------------------------------------------------------------------
List<String> uniqueInB = listB.stream()
.filter(element -> !listA.contains(element))
.collect(Collectors.toList());
System.out.println("Elements in list B only: " + uniqueInB);
-----------------------------------------------------------------------------------------------------
在数据量不大的情况下，使用 Stream API 的方法通常是足够高效的，并且代码简洁易读。如果数据量非常大，您可能需要考虑其他方法，例如将集合转换为 HashSet 以提高查找效率，或者使用并行流（parallel streams）来利用多核处理器。
02.假设集合 A 的数据更多，该如何优化？
a.优化点
如果集合 A 的数据比集合 B 中的数据更多，为了提高效率，我们可以做一些调整。这里有两个优化点：
我们使用了 listB::contains 来检查一个元素是否在集合 B 中。如果集合 A 更大，那么使用 listA::contains 可能会更高效，因为遍历较小的集合将减少必要的 contains 检查次数。
.contains 方法的性能取决于被搜索的集合的类型。对于 ArrayList，contains 方法的时间复杂度是 O(n)，它会遍历整个列表来查找元素，而对于 HashSet，时间复杂度是 O(1)，因为它使用哈希表进行查找。我们这时候就可以将集合 A 转换为一个 HashSet。
b.完整的示例代码
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;
List<String> listA = Arrays.asList("Apple", "Banana", "Cherry", "Date", "Fig", "Grape");
List<String> listB = Arrays.asList("Banana", "Date", "Fig");
Set<String> setA = new HashSet<>(listA);
List<String> listC = listB.stream()
.filter(setA::contains)
.collect(Collectors.toList());
List<String> listD = listB.stream()
.filter(element -> !setA.contains(element))
.collect(Collectors.toList());
System.out.println("List C (common elements): " + listC);
System.out.println("List D (unique to list B): " + listD);
c.补充说明
如果集合 A 和集合 B 都是使用 List 实现，那么两种方法的时间复杂度在本质上是相同的。每次调用 contains 方法时，都会在另一个列表上进行线性搜索，这意味着每次调用的时间复杂度都是 O(n)。
对集合 A 中的每个元素调用 listB::contains，如果集合 A 有 n 个元素，集合 B 有 m 个元素，那么总的时间复杂度就是 O(n*m)。
对集合 B 中的每个元素调用 listA::contains，同样地，如果集合 A 有 n 个元素，集合 B 有 m 个元素，那么总的时间复杂度也是 O(n*m)。
如果集合 A 远大于集合 B，遍历较小的集合 B 通常在实际应用中效率更高，即使时间复杂度在理论上是相等的。这是因为较小的集合遍历次数更少，从而减少了实际执行的总步骤数。不过，这种效率的差异只能在实际运行时才能体现。
03.如果集合中存放的是对象，该如何操作？
a.定义对象
通常情况下，我们不会在集合中存放字符串，都是放一些对象数据，这时候该如何获取呢？在这里我们定义一个 Person 作为示例，假设 Person 对象在 name 和 age 属性都相同时被认为是相等的。
b.重写 equals 和 hashCode 方法
在 Java 中使用 contains 方法来检查一个集合是否包含某个对象时，就需要重写对象的 equals 和 hashCode 方法。这是因为 contains 方法的实现依赖于 equals 方法来比较对象，而 hashCode 方法则用于快速查找和确定对象在散列数据结构（如 HashSet 或 HashMap）中的位置。
equals 和 hashCode 方法之间有一个重要的一致性约定：
如果两个对象根据 equals 方法是相等的，那么它们的 hashCode 方法也必须返回相同的值。
如果两个对象的 hashCode 值不同，那么它们一定不相等（根据 equals 方法）。
这个约定对于 HashSet、HashMap 等集合的正确运作至关重要。如果你只重写了 equals 方法而没有重写 hashCode 方法，可能会导致集合的行为不符合预期，例如，即使两个对象相等，HashSet 也可能认为它们是不同的对象并存储两个副本。
c.示例代码
public class Person {
private String name;
private int age;
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Person person = (Person) o;
return Objects.equals(name, person.name) && age == person.age;
}
@Override
public int hashCode() {
int result = 17;
result = 31 * result + Objects.hashCode(name);
result = 31 * result + Integer.hashCode(age);
return result;
}
}
-----------------------------------------------------------------------------------------------------
在这个实现中，equals 方法首先检查是否是同一个对象，然后检查对象是否为空或者是否是不同的类型。如果这些检查都通过了，它会通过 Objects.equals 方法比较 name 属性，并直接比较 age 属性的值。
hashCode 方法使用了一个固定的质数（在这里是 17）作为初始哈希码。然后，它使用 31 作为乘数（31 是一个质数，通常用于计算哈希码，因为它有助于避免哈希冲突）。hashCode 方法分别对 name 和 age 属性调用 Objects.hashCode 和 Integer.hashCode 方法来计算它们的哈希码，并将它们组合起来。
2.8 [2]map：排序
01.四种排序
a.插入顺序排序
a.实现
使用 LinkedHashMap，它保持元素的插入顺序
b.示例
Map<String, Integer> map = new LinkedHashMap<>();
map.put("one", 1);
map.put("two", 2);
b.自然顺序排序
a.实现
使用 TreeMap，它根据键的自然顺序进行排序
b.示例
Map<String, Integer> map = new TreeMap<>();
map.put("two", 2);
map.put("one", 1);
c.按访问顺序排序
a.实现
使用 LinkedHashMap 并在 put 操作后调用 get 方法，来维护元素的访问顺序（最近访问的在最后）
b.示例
LinkedHashMap<String, Integer> map = new LinkedHashMap<String, Integer>(16, 0.75f, true);
map.put("one", 1);
map.put("two", 2);
map.get("one"); // 使 "one" 变为最近访问的
d.按自定义规则排序
a.实现
使用 TreeMap 并传入自定义 Comparator
b.示例
Map<String, Integer> map = new TreeMap<>(new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
return s2.compareTo(s1); // 逆序排序
}
});
map.put("one", 1);
map.put("two", 2);
2.9 [3]Generics泛型
01.常用信息
a.定义
a.背景
Java集合有个缺点—把一个对象“丢进”集合里之后，集合就会“忘记”这个对象的数据类型，
当再次取出该对象时，该对象的编译类型就变成了Object类型（其运行时类型没变）。
b.通用性
Java集合之所以被设计成这样，是因为集合的设计者不知道我们会用集合来保存什么类型的对象，
所以他们把集合设计成能保存任何类型的对象，只要求具有很好的通用性。
c.两个问题
集合对元素类型没有任何限制，这样可能引发一些问题。例如，想创建一个只能保存Dog对象的集合，但程序也可以轻易地将Cat对象“丢”进去，所以可能引发异常。
由于把对象“丢进”集合时，集合丢失了对象的状态信息，只知道它盛装的是Object，因此取出集合元素后通常还需要进行强制类型转换。这种强制类型转换既增加了编程的复杂度，也可能引发ClassCastException异常。
b.作用
a.数据安全
略
b.防止类型转换时出错
list.add(默认返回值是Object类型到)
如果加了Double泛型，则自动变成了Iist.add(必须加入Double类型到)，其返回值也必须是Double类型的数据
简言之，以Double泛型为例，
如果不加泛型，则默认操作的是Object类型，
如果加了Double泛型，则默认操作的是Double类型
c.泛型可以把类型当作参数一样传递
使得像一些集合类可以明确存储的对象类型，不用显示地强制转化（在没泛型之前只能是Object，然后强转）
d.在编译期能识别类型，类型错误则会提醒，增加程序的健壮性和可读性
略
02.常用信息
a.泛型擦除
参数类型在编译之后就被抹去了，也就是生成的class文件是没有泛型信息的，所以称之为擦除。
b.关键字
T：Type，类型
R：Return Type，返回类型
K：Key，键
V：Value，值
E：Element，元素
c.T (Type)
T 代表类型（Type），通常用在通用的类型参数中。
示例：public class Box<T> { private T t; }
d.R (Return Type)
R 代表返回类型（Return Type），通常用在方法返回类型中。
示例：public interface Function<T, R> { R apply(T t); }
e.K (Key)
K 代表键（Key），通常用在表示键值对的泛型类中，如映射（Map）。
示例：public class HashMap<K, V> { ... }
f.V (Value)
V 代表值（Value），通常与 K 一起使用，表示键值对中的值。
示例：public class HashMap<K, V> { ... }
g.E (Element)
E 代表元素（Element），通常用在表示集合中的元素类型。
示例：public interface Collection<E> { ... }
03.使用方式
a.汇总
泛型类、泛型接口、泛型方法
b.泛型类
a.定义
//此处T可以随便写为任意标识，常见的如T、E、K、V等形式的参数常用于表示泛型
//在实例化泛型类时，必须指定T的具体类型
public class Generic<T>{
private T key;
public Generic(T key) {
this.key = key;
}
public T getKey(){
return key;
}
}
b.实例化泛型类
Generic<Integer> genericInteger = new Generic<Integer>(123456);
c.泛型接口
a.定义
public interface Generator<T> {
public T method();
}
b.实现泛型接口，不指定类型
class GeneratorImpl<T> implements Generator<T>{
@Override
public T method() {
return null;
}
}
c.实现泛型接口，指定类型
class GeneratorImpl implements Generator<String> {
@Override
public String method() {
return "hello";
}
}
d.泛型方法
a.定义
public static < E > void printArray( E[] inputArray )
{
for ( E element : inputArray ){
System.out.printf( "%s ", element );
}
System.out.println();
}
b.使用
// 创建不同类型数组：Integer, Double 和 Character
Integer[] intArray = { 1, 2, 3 };
String[] stringArray = { "Hello", "World" };
printArray( intArray );
printArray( stringArray );
04.代码示例
a.示例1
public static <T> List<T> extractListFromMap(Map<String, Object> map, String key, Class<T> clazz) {
// 获取 Map 中指定 Key 对应的 Value
Object value = map.get(key);
// 判断 Value 是否为 Collection 类型
if (value instanceof Collection<?>) {
return ((Collection<?>) value).stream()
.map(clazz::cast)
.collect(Collectors.toList());
}
throw new IllegalArgumentException("该 Value 不是 Collection 类型");
}
b.示例2
private <T> int handleBatchOperationSysUser(List<T> list, String sqlOperationName) {
if (ObjectUtil.isEmpty(list)) {
return 0;
}
int count = 0;
final int batchSize = 3000;
for (int i = 0, sizes = list.size(); i < sizes; i += batchSize) {
List<T> batchList = list.subList(i, Math.min(i + batchSize, sizes));
try {
switch (sqlOperationName) {
// SysUser
case "insertSysUserBatch":
if (!(batchList.get(0) instanceof SysUser)) {
throw new IllegalArgumentException("insertSysUserBatch 批量数据类型不匹配，期望 SysUser 类型");
}
count += sysUserMapper.upsertSysUserBatch((List<SysUser>) batchList);
break;
case "updateSysUserBatch":
if (!(batchList.get(0) instanceof SysUser)) {
throw new IllegalArgumentException("updateSysUserBatch 批量数据类型不匹配，期望 SysUser 类型");
}
count += sysUserMapper.upsertSysUserBatch((List<SysUser>) batchList);
break;
case "bulkDeleteSysUser":
if (!(batchList.get(0) instanceof String)) {
throw new IllegalArgumentException("bulkDeleteSysUser 批量数据类型不匹配，期望 String 类型");
}
count += sysUserMapper.bulkDeleteSysUser((List<String>) batchList);
break;
default:
throw new IllegalArgumentException("不支持的操作类型: " + sqlOperationName);
}
} catch (Exception e) {
// 执行数据库，运行过程抛出异常抛出异常
throw new RuntimeException("操作数据库异常：" + sqlOperationName, e);
}
}
return count;
}
2.10 [3]iterator迭代器
01.介绍
迭代器是一种设计模式，它是一个对象，它可以遍历并选择序列中的对象，而开发人员不需要了解该序列的底层结构。
Java中的Iterator功能比较简单，并且只能单向移动：
02.使用
a.iterator()
要求容器返回一个Iterator。第一次调用Iterator的next()方法时，它返回序列的第一个元素
注意：iterator()方法是java.lang.Iterable接口,被Collection继承
b.next()
获得序列中的下一个元素
c.hasNext()
检查序列中是否还有元素
d.remove()
将迭代器新返回的元素删除
2.11 [3]遍历数组和集合：3种
01.遍历数组和集合，一般有以下三种形式
a.普通for循环
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + ",");
}
b.增强for循环，也叫foreach
int count = 0;
for (Integer i : list) {
System.out.print(i + ",");
count++;
}
c.迭代器遍历
int count = 0;
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + ",");
count++;
}
d.跳出多层循环
outerLoop:
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
System.out.println("i = " + i + ", j = " + j);
// 某个条件满足时跳出外层循环
if (i == 2 && j == 3) {
break outerLoop;
}
}
}
02.方式一：普通for循环
a.数组
int[] nums = new int[]{1, 2, 3, 4}
for (int i=0; i<num.length; i++) { for (初始值; 循环条件; 更新变量) {
System.out.println(num[i]); 循环操作
} }
b.集合
a.遍历ArrayList
List<String> arr = new ArrayList<String>();
arr.add("元素1");
arr.add("元素2");
arr.add("元素3");
for (int i = 0; i < arr.size(); i++) { // for适用于循环次数已知
System.out.println(arr.get(i));
}
-------------------------------------------------------------------------------------------------
元素1
元素2
元素3
b.遍历HashMap
// 创建一个HashMap
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("One", 1);
hashMap.put("Two", 2);
hashMap.put("Three", 3);
// 获取键的集合
Object[] keys = hashMap.keySet().toArray();
String[] keys = hashMap.keySet().toArray(new String[list.size()]);
// 使用普通for循环遍历键，并获取对应的值
for (int i = 0; i < keys.length; i++) {
String key = (String) keys[i];
Integer value = hashMap.get(key);
System.out.println("Key: " + key + ", Value: " + value);
}
-------------------------------------------------------------------------------------------------
Key: One, Value: 1
Key: Two, Value: 2
Key: Three, Value: 3
03.方式二：增强For循环，也叫foreach
a.数组
int[] nums = new int[]{1, 2, 3, 4} // JAVA1.5引入增加型for循环，变量值相当于num[i]
for (int i: nums) { for (元素类型 变量值: 数组/集合){
System.out.println(i) 循环操作
} }
b.集合
a.遍历ArrayList
List<String> arr = new ArrayList<String>(); // foreach适用于循环次数未知
arr.add("one");
arr.add("two");
arr.add("three");
for(String str : arr) {
System.out.println(str);
}
元素1
元素2
元素3
-------------------------------------------------------------------------------------------------
List<String> arr = new LinkedList<String>(); // foreach适用于循环次数未知
arr.add("one");
arr.add("two");
arr.add("three");
for(String str : arr) {
System.out.println(str);
}
元素1
元素2
元素3
c.遍历HashMap
Map<String, String> mapstr = new HashMap<String, String>();
mapstr.put("王", "男");
mapstr.put("李", "男");
mapstr.put("张", "女");
for (Map.Entry<String, String> s : mapstr.entrySet()) { // HashMap，乱序
System.out.print("key=" + s.getKey() + '\t');
System.out.print("value=" + s.getValue() + '\n');
}
key=张 value=女
key=王 value=男
key=李 value=男
-------------------------------------------------------------------------------------------------
Map<String, String> mapstr = new LinkedHashMap<String, String>();
mapstr.put("王", "男");
mapstr.put("李", "男");
mapstr.put("张", "女");
for (Map.Entry<String, String> s : mapstr.entrySet()) { // LinkedHashMap，正序
System.out.print("key=" + s.getKey() + '\t');
System.out.print("value=" + s.getValue() + '\n');
}
key=王 value=男
key=李 value=男
key=张 value=女
03.方式三：迭代器遍历
a.数组
int[] nums = new int[]{1, 2, 3, 4};
Iterator iter = nums.iterator(); // 提示报错，int[]没有一个叫做iterator的方法
b.集合
a.遍历ArrayList
List list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Iterator iter = list.iterator();
while (iter.hasNext()) {
int j = (int) iter.next();
System.out.print(j + "\t");
}
-------------------------------------------------------------------------------------------------
1 2 3
b.遍历HashSet
Set set = new HashSet<>();
set.add(new Theme(1, "标题1", "简介1"));
set.add(new Theme(2, "标题2", "简介1"));
Iterator iter = set.iterator();
while (iter.hasNext()) {
Theme theme = (Theme) iter.next();
System.out.println(theme.getId() + theme.getTitle() + theme.getRemark());
}
-------------------------------------------------------------------------------------------------
1 标题1 简介1
2 标题2 简介1
c.遍历HashMap
Map map = new HashMap<>();
map.put(1, "a");
map.put(2, "b");
map.put(3, "c");
Set set = map.keySet(); // 所有Key组成一个集合
Iterator iter = set.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
Set set2 = map.keySet(); // 所有Key组成一个集合
System.out.println(set2);
Collection col = map.values(); // 所有Value组成一个集合
System.out.println(col);
-------------------------------------------------------------------------------------------------
1
2
3
[1, 2, 3]
[a, b, c]
d.遍历HashMap
Map map = new HashMap<>();
map.put(1, "a");
map.put(2, "b");
map.put(3, "c");
Set<Map.Entry<Integer, String>> entrySet = map.entrySet(); // entrySet是Key:Value的集合
Iterator<Map.Entry<Integer, String>> iter = entrySet.iterator();
while (iter.hasNext()) {
Map.Entry<Integer, String> entry = iter.next();
System.out.print("Key：" + entry.getKey() + "\t");
System.out.print("Value：" + entry.getValue() + "\n");
}
-------------------------------------------------------------------------------------------------
Key：1 Value：a
Key：2 Value：b
Key：3 Value：c
3 ArrayList：动态数组
3.1 [0]常见API
01.ArrayList常见API（包括继承自父类的API）
boolean add(E e) 将指定的元素添加到列表的末尾
void add(int index, E element) 在列表中的指定位置插入指定的元素
boolean addAll(Collection<? extends E> c) 将指定集合中的所有元素追加到此列表的末尾
boolean addAll(int index, Collection<? extends E> c) 将指定集合中的所有元素插入到列表中的指定位置
void clear() 从列表中移除所有元素
Object clone() 返回此ArrayList实例的浅表副本
boolean contains(Object o) 如果列表中包含指定的元素，则返回true
void ensureCapacity(int minCapacity) 增加此ArrayList实例的容量，以确保它至少可以容纳指定的最小容量
E get(int index) 返回列表中指定位置的元素
int indexOf(Object o) 返回列表中第一次出现的指定元素的索引，如果列表不包含该元素，则返回-1
boolean isEmpty() 如果列表不包含元素，则返回true
Iterator<E> iterator() 返回列表中元素的迭代器
int lastIndexOf(Object o) 返回列表中最后一次出现的指定元素的索引，如果列表不包含该元素，则返回-1
ListIterator<E> listIterator() 返回列表中元素的列表迭代器（按适当顺序）
ListIterator<E> listIterator(int index) 从列表中的指定位置开始，返回列表中元素的列表迭代器（按适当顺序）
E remove(int index) 移除列表中指定位置的元素
boolean remove(Object o) 移除列表中第一次出现的指定元素（如果存在）
boolean removeAll(Collection<?> c) 移除列表中包含在指定集合中的所有元素
void replaceAll(UnaryOperator<E> operator) 使用指定的运算符替换列表中的每个元素
boolean retainAll(Collection<?> c) 仅保留列表中包含在指定集合中的元素
E set(int index, E element) 用指定的元素替换列表中指定位置的元素
int size() 返回列表中的元素数
void sort(Comparator<? super E> c) 使用指定的比较器对列表进行排序
Spliterator<E> spliterator() 创建一个后期绑定和快速失败的Spliterator
List<E> subList(int fromIndex, int toIndex) 返回列表中指定的fromIndex（包括）和toIndex（不包括）之间的部分视图
Object[] toArray() 返回包含列表中所有元素的数组
<T> T[] toArray(T[] a) 返回包含列表中所有元素的数组；返回数组的运行时类型是指定数组的类型
void trimToSize() 将此ArrayList实例的容量调整为列表的当前大小
02.继承自父类的API（AbstractList、AbstractCollection、Object）
boolean equals(Object o) 比较指定对象与列表的相等性。
int hashCode() 返回列表的哈希码值。
String toString() 返回列表的字符串表示形式。
void forEach(Consumer<? super E> action) 对列表中的每个元素执行给定的操作。
boolean removeIf(Predicate<? super E> filter 删除列表中所有满足给定谓词的元素。
void replaceAll(UnaryOperator<E> operator) 使用指定的运算符替换列表中的每个元素。
void sort(Comparator<? super E> c) 使用指定的比较器对列表进行排序。
Spliterator<E> spliterator() 创建一个后期绑定和快速失败的Spliterator。
3.2 [0]ArrayList特性
00.总结
a.ArrayList初始化时使用懒加载机制，只初始化变量
ArrayList在创建时并不会立即分配内存空间，而是初始化一个空的数组。数组在首次添加元素时进行初始化
b.存储元素，实现快速访问
ArrayList是一个动态数组，能够存储任意类型的元素。它提供了基于索引的快速访问和修改操作
c.元素可以是null
ArrayList允许存储null元素，可以在任意位置插入null
d.非同步，线程不安全
ArrayList是非同步的，多个线程同时访问ArrayList可能会导致数据不一致。如果需要线程安全的动态数组，可以使用Collections.synchronizedList(new ArrayList<>())或者使用CopyOnWriteArrayList
e.底层是动态数组，不保证有序
ArrayList底层是一个动态数组，元素的插入顺序即为存储顺序。虽然插入顺序是有序的，但在进行删除或插入操作时，可能会导致元素位置发生变化
f.自动扩容机制
ArrayList在添加元素时，如果内部数组的容量不足，会自动扩容。默认情况下，扩容后的新容量为旧容量的1.5倍
3.3 [1]ArrayList容量限制？8GB
01.ArrayList有没有容量限制？
最大为Integer.MAX_VALUE，即((2^31)-1)2147483647，大约8GB
ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素
3.4 [1]ArrayList扩容机制？默认容量10，扩容为1.5倍，负载因子1，扩容时间复杂度为O(n)
01.扩容机制
a.底层实现
ArrayList 底层是基于动态数组实现的
当我们向 ArrayList 中添加元素时，如果当前数组的容量不足以容纳新的元素，就需要进行扩容
b.默认容量
当创建一个新的 ArrayList 时，如果没有指定初始容量，默认容量为 10
c.扩容机制
每次添加元素时，如果当前数组已经满了，ArrayList 会创建一个新的、更大的数组
并将旧数组中的元素复制到新数组中。新的数组容量通常是旧容量的 1.5 倍
02.主要步骤
1.检查容量：在添加元素时，检查当前容量是否足够。如果不足，则需要扩容
2.计算新容量：新容量通常是旧容量的 1.5 倍，即 newCapacity = oldCapacity + (oldCapacity >> 1)。这种增长策略可以在时间和空间之间取得平衡
3.创建新数组：根据计算的新容量，创建一个新的数组
4.复制旧数组：将旧数组中的元素复制到新数组中
5.引用新数组：将 ArrayList 的内部数组引用指向新数组
03.扩容示例
a.假设我们有一个默认的 ArrayList，初始容量为 10
初始容量：10
当第 11 个元素被添加时，ArrayList 会进行扩容，新的容量将是 10 + 10 / 2 = 15
当第 16 个元素被添加时，ArrayList 会再次进行扩容，新的容量将是 15 + 15 / 2 = 22
b.总结
ArrayList 的默认初始容量是 10
当元素数量超过当前容量时，ArrayList 会进行扩容
扩容后的新容量通常是当前容量的 1.5 倍（具体来说是 当前容量 + 当前容量 / 2）
3.5 [1]ArrayList不可以自动缩容
01.ArrayList不可以自动缩容
a.回答
与自动扩容不同，ArrayList 不会 在元素被移除后自动缩小其内部数组的容量
这意味着即使删除了大量元素，ArrayList 的内部数组容量仍可能保持较大，以便未来可能的扩展
b.手动缩容
如果希望手动缩小 ArrayList 的容量以匹配其当前大小，可以使用 trimToSize() 方法
ArrayList<String> list = new ArrayList<>();
list.trimToSize(); // 调整内部数组的容量，使其与当前元素数量一致
02.自动扩容、自动缩容
自动扩容：ArrayList 会在添加元素时自动增加容量
自动缩容：ArrayList 不会自动减少容量，但可以通过调用 trimToSize() 方法手动调整
3.6 [2]什么时候用Array？
01.什么时候更适合用Array？
a.场景1
如果列表的大小已经指定，大部分情况下是存储和遍历它们
b.场景2
对于遍历基本数据类型，尽管 Collections 使用自动装箱来减轻编码任务
在指定大小的基本类型的列表上工作也会变得很慢
c.场景3
如果你要使用多维数组，使用 [][] 比 List 会方便
3.7 [2]什么时候用Collection？
01.什么时候用Collection？
a.场景1
Collection的长度会自动适应，不必人工干预
b.场景2
Collection可以获取到真实的数据个数size
c.场景3
用集合可以方便实现对象的增删改查
4 CopyOnWriteArrayList：写时复制数组列表，读多写少，无锁并发编程
4.1 [1]原理
01.定义
1.对数组的写操作加锁，读操作不加锁
2.通过加锁 + 数组拷贝+ volatile 来保证线程安全
3.实现List接口，通过在每次修改操作时创建一个新的底层数组来实现线程安全性
02.原理
a.介绍
CopyOnWriteArrayList 的核心原理是“写时复制”（Copy-On-Write）
当对列表进行修改（如添加、删除或更新元素）时，它会创建一个新的底层数组，并在新的数组上进行修改
修改完成后，新的数组会替换旧的数组
由于读操作不会修改底层数组，因此读操作可以在没有锁的情况下安全地进行
b.写时复制
当对列表进行修改操作时（如 add、remove、set 等），CopyOnWriteArrayList 会创建一个新的底层数组，并在新的数组上进行修改
修改完成后，新的数组会替换旧的数组
c.读操作无锁
由于读操作不会修改底层数组，因此读操作可以在没有锁的情况下安全地进行
读操作直接访问底层数组，不需要进行同步
d.原子操作
通过写时复制机制，CopyOnWriteArrayList 实现了线程安全性
多个线程可以同时进行读操作，而不会相互干扰
写操作会创建新的数组，并在替换旧数组时使用原子操作，确保线程安全
03.应用场景
a.读多写少
在读操作远多于写操作的场景中，CopyOnWriteArrayList 提供了高效的并发访问
b.线程安全的列表
在需要线程安全的列表的场景中，CopyOnWriteArrayList 提供了高效的实现
c.迭代器
在需要频繁使用迭代器的场景中，CopyOnWriteArrayList 提供了安全的迭代器，不会抛出 ConcurrentModificationException
4.2 [1]常用API
01.常用API
a.构造方法
CopyOnWriteArrayList(): 创建一个空的 CopyOnWriteArrayList
CopyOnWriteArrayList(Collection<? extends E> c): 创建一个包含指定集合元素的 CopyOnWriteArrayList
CopyOnWriteArrayList(E[] toCopyIn): 创建一个包含指定数组元素的 CopyOnWriteArrayList
b.添加元素
boolean add(E e): 将指定的元素添加到列表的末尾
void add(int index, E element): 在列表的指定位置插入元素
c.删除元素
E remove(int index): 移除并返回列表中指定位置的元素
boolean remove(Object o): 移除列表中首次出现的指定元素
d.获取元素
E get(int index): 返回列表中指定位置的元素
e.更新元素
E set(int index, E element): 用指定的元素替换列表中指定位置的元素
f.迭代器
Iterator<E> iterator(): 返回列表的迭代器。迭代器是基于快照的，不会抛出 ConcurrentModificationException
g.其他操作
int size(): 返回列表中的元素数量
boolean isEmpty(): 如果列表不包含元素，则返回 true
boolean contains(Object o): 如果列表包含指定的元素，则返回 true
02.代码示例
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
public class CopyOnWriteArrayListExample {
public static void main(String[] args) {
List<String> list = new CopyOnWriteArrayList<>();
// 添加元素
list.add("A");
list.add("B");
list.add("C");
// 获取元素
System.out.println("Element at index 1: " + list.get(1));
// 更新元素
list.set(1, "D");
System.out.println("Updated element at index 1: " + list.get(1));
// 删除元素
list.remove("A");
System.out.println("List after removal: " + list);
// 迭代元素
for (String element : list) {
System.out.println("Element: " + element);
}
}
}
---------------------------------------------------------------------------------------------------------
在这个示例中，我们创建了一个 CopyOnWriteArrayList 实例，并进行了添加、获取、更新、删除、迭代元素的操作
4.3 [1]线程安全性
00.汇总
1.写时复制
2.读操作无锁
3.原子操作
---------------------------------------------------------------------------------------------------------
1.使用ReentrantLock加锁，保证操作过程中线程安全
2.使用volatile关键字修饰数组，保证当前线程对数组对象重新赋值后，其他线程可以及时感知到
01.三种机制
a.写时复制（Copy-On-Write）
当对列表进行修改操作（如 add、remove、set 等）时，CopyOnWriteArrayList 会创建一个新的底层数组，并在新的数组上进行修改
修改完成后，新的数组会替换旧的数组。由于读操作不会修改底层数组，因此读操作可以在没有锁的情况下安全地进行
b.读操作无锁
由于读操作不会修改底层数组，因此读操作可以在没有锁的情况下安全地进行
读操作直接访问底层数组，不需要进行同步，从而提高了读操作的性能
c.原子操作
修改操作（如 add、remove、set 等）在创建新数组并替换旧数组时，使用了原子操作，确保线程安全性
通过使用 volatile 关键字来确保对底层数组引用的可见性，保证所有线程都能看到最新的数组
02.代码示例
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
public class CopyOnWriteArrayListExample {
public static void main(String[] args) {
List<String> list = new CopyOnWriteArrayList<>();
// 添加元素
list.add("A");
list.add("B");
list.add("C");
// 启动多个线程进行读操作
for (int i = 0; i < 5; i++) {
new Thread(() -> {
for (String element : list) {
System.out.println("Read: " + element);
}
}).start();
}
// 启动多个线程进行写操作
for (int i = 0; i < 5; i++) {
new Thread(() -> {
list.add("D");
System.out.println("Added: D");
}).start();
}
}
}
4.4 [1]线程并发度
01.线程并发度
a.读操作的并发度
由于读操作不会修改底层数组，因此读操作可以在没有锁的情况下安全地并发进行
多个线程可以同时进行读操作，而不会相互干扰
读操作的并发度非常高，理论上可以支持任意数量的线程同时进行读操作
b.写操作的并发度
写操作（如 add、remove、set 等）会创建一个新的底层数组，并在新的数组上进行修改
写操作需要对底层数组进行复制，因此写操作的并发度较低
在进行写操作时，CopyOnWriteArrayList 使用内部锁来确保线程安全性。虽然多个线程可以同时进行写操作，但每个写操作都会创建新的数组，导致性能开销较大
c.读写操作的并发度
读操作和写操作可以同时进行，因为读操作不会修改底层数组
读操作可以在没有锁的情况下并发进行，而写操作需要使用内部锁来确保线程安全性
读操作的并发度非常高，而写操作的并发度较低
02.代码示例
a.代码
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
public class CopyOnWriteArrayListConcurrencyExample {
public static void main(String[] args) {
List<String> list = new CopyOnWriteArrayList<>();
// 添加初始元素
list.add("A");
list.add("B");
list.add("C");
// 启动多个线程进行读操作
for (int i = 0; i < 10; i++) {
new Thread(() -> {
for (String element : list) {
System.out.println("Read: " + element);
}
}).start();
}
// 启动多个线程进行写操作
for (int i = 0; i < 3; i++) {
new Thread(() -> {
list.add("D");
System.out.println("Added: D");
}).start();
}
}
}
b.说明
在这个示例中，我们创建了一个 CopyOnWriteArrayList 实例，并启动了多个线程进行读操作和写操作
读操作的并发度非常高，多个线程可以同时进行读操作
写操作的并发度较低，多个线程进行写操作时，每个写操作都会创建新的数组
4.5 [1]初始容量？初始0
01.CopyOnWriteArrayList初始容量？
0
4.6 [1]扩容机制？加锁、新数组、释放锁
01.CopyOnWriteArrayList是怎么进行扩容的？
1.加锁
2.创建一个新数组，长度原数组长度+1，并把原数组元素拷贝到新数组里面
3.释放锁
4.7 [2]add过程
01.工作过程
a.获取锁
CopyOnWriteArrayList 使用一个内部的重入锁（ReentrantLock）来确保在执行修改操作时只有一个线程能够访问底层数组
add 方法首先会获取这个锁
b.复制数组
一旦获取了锁，add 方法会创建底层数组的一个新副本。这个新副本包含了当前数组中的所有元素
c.添加新元素
在新副本中添加新元素。新元素会被添加到数组的末尾
d.更新引用
将内部引用指向这个新数组。这样，其他线程在读取时会看到一个一致的、未被修改的数组
e.释放锁
最后，add 方法释放锁，使其他线程可以继续执行
02.代码示例
a.代码
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();
}
}
b.说明
lock.lock() 获取锁
getArray() 获取当前的底层数组
Arrays.copyOf(elements, len + 1) 创建一个新数组，并将当前数组的所有元素复制到新数组中
newElements[len] = e 将新元素添加到新数组的末尾
setArray(newElements) 更新内部引用，使其指向新数组
lock.unlock() 释放锁
4.8 [2]add过程：加锁
01.工作过程
a.获取锁
在执行任何修改操作之前，CopyOnWriteArrayList 会首先获取一个重入锁
这确保了在执行修改操作时，只有一个线程能够访问和修改底层数组
b.执行修改操作
在获取锁之后，add 方法会执行实际的修改操作，包括创建数组的新副本并添加新元素
c.释放锁
在修改操作完成后，add 方法会释放锁，使其他线程可以继续执行
02.代码示例
a.代码
import java.util.concurrent.locks.ReentrantLock;
import java.util.Arrays;
public class CopyOnWriteArrayList<E> {
private transient final ReentrantLock lock = new ReentrantLock();
private transient volatile Object[] array;
public CopyOnWriteArrayList() {
array = new Object[0];
}
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(); // 释放锁
}
}
final Object[] getArray() {
return array;
}
final void setArray(Object[] a) {
array = a;
}
}
b.说明
final ReentrantLock lock = this.lock; 获取当前实例的锁
lock.lock(); 获取锁，确保只有当前线程可以执行接下来的代码
try { ... } finally { lock.unlock(); } 确保在执行完修改操作后，无论是否发生异常，都会释放锁
Object[] elements = getArray(); 获取当前的底层数组
Object[] newElements = Arrays.copyOf(elements, len + 1); 创建一个新数组，并将当前数组的所有元素复制到新数组中
newElements[len] = e; 将新元素添加到新数组的末尾
setArray(newElements); 更新内部引用，使其指向新数组
4.9 [2]get过程
01.工作过程
a.获取当前数组
读取操作直接从内部的 array 字段获取当前的数组引用
b.返回元素
根据给定的索引，从数组中返回相应的元素
02.代码示例
a.代码
import java.util.concurrent.locks.ReentrantLock;
public class CopyOnWriteArrayList<E> {
private transient volatile Object[] array;
public CopyOnWriteArrayList() {
array = new Object[0];
}
public E get(int index) {
return get(getArray(), index);
}
final Object[] getArray() {
return array;
}
@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
return (E) a[index];
}
}
b.说明
get(int index) 方法首先调用 getArray() 方法获取当前的数组引用
getArray() 方法返回当前的数组引用
get(Object[] a, int index) 方法从数组 a 中获取指定索引 index 处的元素，并将其返回
4.10 [2]get过程：不加锁
01.回答
不加锁，由于array字段是volatile的，保证了读写操作可见
02.说明
由于每次修改操作都会创建一个新的数组副本，由于array字段是volatile的
这保证了对其的读写操作是可见的，并且读取操作总是能够看到最新的数组副本
4.11 [3]JDK7与8区别
00.回答
在JDK7和JDK 8中的实现【基本一致】
01.内部数组的初始化
a.JDK7中，CopyOnWriteArrayList的内部数组初始化是通过一个静态的空数组来完成的
private static final Object[] EMPTY_ARRAY = new Object[0];
private transient volatile Object[] array;
public CopyOnWriteArrayList() {
setArray(EMPTY_ARRAY);
}
b.在JDK8中，这个初始化过程没有显著变化，仍然使用一个静态的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
private transient volatile Object[] array;
public CopyOnWriteArrayList() {
setArray(EMPTY_ELEMENTDATA);
}
02.addAllAbsent方法的优化
a.JDK7
略
b.JDK8
在JDK8中，addAllAbsent方法进行了优化，以提高性能
这个方法用于将集合中的所有元素添加到列表中，但仅当这些元素在列表中不存在时才添加
03.其他细节优化
在JDK8中，CopyOnWriteArrayList可能还进行了其他一些细节上的优化，例如：
更高效的数组复制和操作
更好的内存管理和垃圾回收
代码的清理和重构，以提高可读性和维护性
4.12 [3]与读写锁区别
01.读写锁
读线程具有实时性，写线程会阻塞
解决了数据不一致的问题，但是读写锁【依然会出现读线程阻塞等待】的情况
02.CopyOnWriteArrayList
读线程具有实时性，写线程会阻塞
不能解决数据不一致的问题。但是CopyOnWriteArrayList【不会出现读线程阻塞等待】的情况
4.13 [4]CopyOnWriteArrayList、SynchronizedList
00.汇总
a.并发性能
由于 CopyOnWriteArrayList 读操作上没有加锁，所以 CopyOnWriteArrayList 读操作性能更好
而 SynchronizedList 由于读写操作都加了锁，所以读写都会受到一定影响
b.内存占用
由于 CopyOnWriteArrayList 写操作会进行数组复制
所以 CopyOnWriteArrayList 在写操作上内存占用开销比 SynchronizedList 要大，所以不适合非常频繁写操作
c.适用场景
CopyOnWriteArrayList 适用于读多写少的场景
SynchronizedList 则适用于读写操作相对均衡或者写操作相对较频繁的场景
01.CopyOnWriteArrayList
a.说明
CopyOnWrite 代表写时复制，在执行写操作（如添加、删除或修改元素）时
会复制一份新数组进行相关的操作，然后在操作完成后将原来的集合指向新的集合
b.说明
由于读操作在原数组上进行，所以读操作不需要加锁，所以读操作比较高效
而写操作内存占用开销比较大，比较适合读多写少的情况
c.源码
public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
//...
/**
* The lock protecting all mutators. (We have a mild preference
* for builtin monitors over ReentrantLock when either will do.)
*/
final transient Object lock = new Object(); //保证不会有多个线程同时复制一个新数组
/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array; //volatile 关键字保证了变量的可见性
/**
* Gets the array. Non-private so as to also be accessible
* from CopyOnWriteArraySet class.
*/
final Object[] getArray() {
return array;
}
/**
* Sets the array.
*/
final void setArray(Object[] a) {
array = a;
}
/**
* Creates an empty list.
*/
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
/**
* Creates a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection of initially held elements
* @throws NullPointerException if the specified collection is null
*/
public CopyOnWriteArrayList(Collection<? extends E> c) {
Object[] es;
if (c.getClass() == CopyOnWriteArrayList.class)
es = ((CopyOnWriteArrayList<?>)c).getArray();
else {
es = c.toArray();
// Android-changed: Defend against c.toArray (incorrectly) not returning Object[]
// (see b/204397945)
// if (c.getClass() != java.util.ArrayList.class)
if (es.getClass() != Object[].class)
es = Arrays.copyOf(es, es.length, Object[].class);
}
setArray(es);
}
//...
/**
* Returns the number of elements in this list.
*
* @return the number of elements in this list
*/
public int size() {
return getArray().length;
}
public E get(int index) {
return elementAt(getArray(), index);
}
/**
* Replaces the element at the specified position in this list with the
* specified element.
*
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
synchronized (lock) {
Object[] es = getArray();
E oldValue = elementAt(es, index);
if (oldValue != element) {
es = es.clone();
es[index] = element;
}
// Ensure volatile write semantics even when oldvalue == element
setArray(es);
return oldValue;
}
}
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
synchronized (lock) {
Object[] es = getArray();
int len = es.length;
es = Arrays.copyOf(es, len + 1);
es[len] = e;
setArray(es);
return true;
}
}
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices). Returns the element that was removed from the list.
*
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
synchronized (lock) {
Object[] es = getArray();
int len = es.length;
E oldValue = elementAt(es, index);
int numMoved = len - index - 1;
Object[] newElements;
if (numMoved == 0)
newElements = Arrays.copyOf(es, len - 1);
else {
newElements = new Object[len - 1];
System.arraycopy(es, 0, newElements, 0, index);
System.arraycopy(es, index + 1, newElements, index,
numMoved);
}
setArray(newElements);
return oldValue;
}
}
/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
public void clear() {
synchronized (lock) {
setArray(new Object[0]);
}
}
/**
* Returns an iterator over the elements in this list in proper sequence.
*
* <p>The returned iterator provides a snapshot of the state of the list
* when the iterator was constructed. No synchronization is needed while
* traversing the iterator. The iterator does <em>NOT</em> support the
* {@code remove} method.
*
* @return an iterator over the elements in this list in proper sequence
*/
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
//...
}
02.Collections$SynchronizedList
a.说明
通过包装一个普通的 List 来实现，大部分的读写操作都用 synchronized 关键字（对象锁）来保证线程安全
而迭代方法没有加，所以在使用迭代方法的时候需要自行处理线程同步问题，由于读操作也被加锁了
所以性能上受到了一定影响
b.说明
常用方法 Collections.synchronizedList 返回一个 SynchronizedList 对象
c.说明
SynchronizedList 比较适合需要简单地将普通非线程安全的 List 转换为线程安全的 List 的情况
d.源码
//java.util.Collections
public static <T> List<T> synchronizedList(List<T> list) {
return (list instanceof RandomAccess ? new SynchronizedRandomAccessList<>(list) : new SynchronizedList<>(list));
}
//Collections 的静态内部类 SynchronizedList
static class SynchronizedList<E> extends SynchronizedCollection<E> implements List<E> {
//...
@SuppressWarnings("serial") // Conditionally serializable
final List<E> list;
SynchronizedList(List<E> list) {
super(list);
this.list = list;
}
//...
public E get(int index) {
synchronized (mutex) {return list.get(index);}
}
public E set(int index, E element) {
synchronized (mutex) {return list.set(index, element);}
}
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
public E remove(int index) {
synchronized (mutex) {return list.remove(index);}
}
//...
public ListIterator<E> listIterator() {
return list.listIterator(); // Must be manually synched by user
}
//...
}
//Collections 的静态内部类 SynchronizedCollection
static class SynchronizedCollection<E> implements Collection<E>, Serializable {
//...
@SuppressWarnings("serial") // Conditionally serializable
final Collection<E> c; // Backing Collection
@SuppressWarnings("serial") // Conditionally serializable
final Object mutex; // Object on which to synchronize
SynchronizedCollection(Collection<E> c) {
this.c = Objects.requireNonNull(c);
mutex = this;
}
//...
public int size() {
synchronized(this.mutex) {
return this.c.size();
}
}
//...
//使用 iterator 遍历的时候仍然需要手动加锁
public Iterator<E> iterator() {
return c.iterator(); // Must be manually synched by user!
}
public boolean add(E e) {
synchronized (mutex) {return c.add(e);}
}
public boolean remove(Object o) {
synchronized (mutex) {return c.remove(o);}
}
//...
public void clear() {
synchronized (mutex) {c.clear();}
}
//...
}
e.使用
List<String> list = Collections.synchronizedList(new ArrayList<>());
//...
//需要自行处理 iterator 方法的线程同步问题
synchronized (list) {
Iterator<String> iterator = list.iterator(); // Must be in synchronized block
while (iterator.hasNext()) {
String str = iterator.next();
Log.e("TAG", "main: str=" + str);
}
}
5 HashMap：哈希映射
5.1 [0]常用API
01.HashMap常见API（包括继承自父类的API）
void clear() 从此映射中移除所有映射关系
Object clone() 返回此HashMap实例的浅表副本
boolean containsKey(Object key) 如果此映射包含指定键的映射关系，则返回true
boolean containsValue(Object value) 如果此映射将一个或多个键映射到指定值，则返回true
Set<Map.Entry<K,V>> entrySet() 返回此映射中包含的映射关系的Set视图
V get(Object key) 返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回null
boolean isEmpty() 如果此映射不包含键-值映射关系，则返回true
Set<K> keySet() 返回此映射中包含的键的Set视图
V put(K key, V value) 将指定的值与此映射中的指定键关联（可选操作）
void putAll(Map<? extends K,? extends V> m) 将指定映射的所有映射关系复制到此映射中（可选操作）
V remove(Object key) 如果存在，则从此映射中移除指定键的映射关系
int size() 返回此映射中的键-值映射关系数
Collection<V> values() 返回此映射中包含的值的Collection视图
V getOrDefault(Object key, V defaultValue) 返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回defaultValue
V putIfAbsent(K key, V value) 如果指定键尚未与值关联（或映射到null），则将其与给定值关联
boolean remove(Object key, Object value) 仅当指定键当前映射到指定值时，才移除该键的映射关系
boolean replace(K key, V oldValue, V newValue) 仅当指定键当前映射到指定值时，才替换该键的映射关系
boolean containsKey(Object key) 如果此映射包含指定键的映射关系，则返回true
boolean containsValue(Object value) 如果此映射将一个或多个键映射到指定值，则返回true
Set<Map.Entry<K,V>> entrySet() 返回此映射中包含的映射关系的Set视图
V get(Object key) 返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回null
boolean isEmpty() 如果此映射不包含键-值映射关系，则返回true
Set<K> keySet() 返回此映射中包含的键的Set视图
V put(K key, V value) 将指定的值与此映射中的指定键关联（可选操作）
void putAll(Map<? extends K,? extends V> m) 将指定映射的所有映射关系复制到此映射中（可选操作）
V remove(Object key) 如果存在，则从此映射中移除指定键的映射关系
int size() 返回此映射中的键-值映射关系数
Collection<V> values() 返回此映射中包含的值的Collection视图
V getOrDefault(Object key, V defaultValue) 返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回defaultValue
V putIfAbsent(K key, V value) 如果指定键尚未与值关联（或映射到null），则将其与给定值关联
boolean remove(Object key, Object value) 仅当指定键当前映射到指定值时，才移除该键的映射关系
boolean replace(K key, V oldValue, V newValue) 仅当指定键当前映射到指定值时，才替换该键的映射关系
V replace(K key, V value) 仅当指定键当前映射到某个值时，才替换该键的映射关系
V replace(K key, V value) 仅当指定键当前映射到某个值时，才替换该键的映射关系
void forEach(BiConsumer<? super K,? super V> action) 对此映射中的每个映射关系执行给定的操作，直到所有条目都被处理或该操作引发异常
void replaceAll(BiFunction<? super K,? super V,? extends V> function) 使用给定的函数替换每个条目的值
V compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) 尝试计算指定键及其当前映射值的映射关系（如果不存在，则为null），并将其输入到此映射中
V computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction) 如果指定键尚未与值关联（或映射到null），则尝试使用给定的映射函数计算其值并将其输入到此映射中
V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) 如果指定键的值存在且非null，则尝试计算给定键及其当前映射值的新映射关系
void forEach(BiConsumer<? super K,? super V> action) 对此映射中的每个映射关系执行给定的操作，直到所有条目都被处理或该操作引发异常
void replaceAll(BiFunction<? super K,? super V,? extends V> function) 使用给定的函数替换每个条目的值
V compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) 尝试计算指定键及其当前映射值的映射关系（如果不存在，则为null），并将其输入到此映射中
V computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction) 如果指定键尚未与值关联（或映射到null），则尝试使用给定的映射函数计算其值并将其输入到此映射中
V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) 如果指定键的值存在且非null，则尝试计算给定键及其当前映射值的新映射关系
02.继承自父类的API（AbstractMap、Map、Object）
boolean equals(Object o) 比较指定对象与此映射的相等性
int hashCode() 返回此映射的哈希码值
String toString() 返回此映射的字符串表示形式
boolean containsKey(Object key) 如果此映射包含指定键的映射关系，则返回true
boolean containsValue(Object value) 如果此映射将一个或多个键映射到指定值，则返回true
Set<Map.Entry<K,V>> entrySet() 返回此映射中包含的映射关系的Set视图
V get(Object key) 返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回null
boolean isEmpty() 如果此映射不包含键-值映射关系，则返回true
Set<K> keySet() 返回此映射中包含的键的Set视图
V put(K key, V value) 将指定的值与此映射中的指定键关联（可选操作）
void putAll(Map<? extends K,? extends V> m) 将指定映射的所有映射关系复制到此映射中（可选操作）
V remove(Object key) 如果存在，则从此映射中移除指定键的映射关系
int size() 返回此映射中的键-值映射关系数
Collection<V> values() 返回此映射中包含的值的Collection视图
V getOrDefault(Object key, V defaultValue) 返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回defaultValue
V putIfAbsent(K key, V value) 如果指定键尚未与值关联（或映射到null），则将其与给定值关联
boolean remove(Object key, Object value) 仅当指定键当前映射到指定值时，才移除该键的映射关系
boolean replace(K key, V oldValue, V newValue) 仅当指定键当前映射到指定值时，才替换该键的映射关系
V replace(K key, V value) 仅当指定键当前映射到某个值时，才替换该键的映射关系
void forEach(BiConsumer<? super K,? super V> action) 对此映射中的每个映射关系执行给定的操作，直到所有条目都被处理或该操作引发异常
void replaceAll(BiFunction<? super K,? super V,? extends V> function) 使用给定的函数替换每个条目的值
V compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) 尝试计算指定键及其当前映射值的映射关系（如果不存在，则为null），并将其输入到此映射中
V computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction) 如果指定键尚未与值关联（或映射到null），则尝试使用给定的映射函数计算其值并将其输入到此映射中
V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) 如果指定键的值存在且非null，则尝试计算给定键及其当前映射值的新映射关系
void forEach(BiConsumer<? super K,? super V> action) 对此映射中的每个映射关系执行给定的操作，直到所有条目都被处理或该操作引发异常
void replaceAll(BiFunction<? super K,? super V,? extends V> function) 使用给定的函数替换每个条目的值
V compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) 尝试计算指定键及其当前映射值的映射关系（如果不存在，则为null），并将其输入到此映射中
V computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction) 如果指定键尚未与值关联（或映射到null），则尝试使用给定的映射函数计算其值并将其输入到此映射中
V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) 如果指定键的值存在且非null，则尝试计算给定键及其当前映射值的新映射关系
5.2 [0]HashMap特性
01.HashMap特性
a.懒加载机制
HashMap在初始化时只初始化变量，并未初始化数组。数组在首次添加元素时才进行初始化
b.存储键值对
HashMap存储键值对，实现快速存取。键（key）值不可重复，若键值重复则覆盖旧值
c.键和值可以为null
HashMap允许键和值都为null，但键位置只能存在唯一一个null
d.非同步，线程不安全
HashMap是非同步的，多个线程同时访问 HashMap 可能会导致数据不一致。
如果需要线程安全的哈希表，可以使用Collections.synchronizedMap(new HashMap<>()) 或者使用 ConcurrentHashMap。
e.底层是哈希表，不保证有序：
HashMap底层是哈希表，不保证元素的顺序（例如插入的顺序）
5.3 [1]HashMap容量限制？8GB
01.HashMap容量限制？
HashMap的最大容量是2^30
容量默认是16，也可以构造时传入，最大值是1<<30，即2^30
5.4 [1]HashMap扩容机制？默认容量16，扩容为2倍，负载因子0.75，阈值16 * 0.75 = 12，扩容时间复杂度为O(n)
01.HashMap扩容机制？
默认容量16，负载因子默认0.75
已用容量 > 总容量*负载因子 时，HashMap扩容规则为【当前容量翻倍】
02.扩容机制
a.JDK7
当 HashMap 中的元素数量超过 容量 * 加载因子（默认 0.75） 时，会触发扩容
扩容时，HashMap 的容量会翻倍，并重新计算所有元素的哈希值，将它们重新分配到新的桶中
在 JDK 1.7 中，扩容时采用 头插法 重新构建链表：
新的节点会被插入到链表的头部。
这种方式会导致链表中的元素顺序与插入顺序相反。
在多线程环境下，可能会导致 死循环（链表节点形成环形结构）
b.JDK8
JDK 1.8 也会在 容量 * 加载因子 超过阈值时触发扩容
扩容时，采用 尾插法 重新构建链表：
新的节点会被插入到链表的尾部
这种方式可以保持链表中元素的顺序一致
同时，扩容过程对并发问题的处理更安全，不会导致死循环
03.扩容示例
a.假设我们有一个默认的 HashMap，初始容量为 16，负载因子为 0.75
初始容量：16
负载因子：0.75
阈值：16 * 0.75 = 12
b.当 HashMap 中的元素数量达到 12 时，HashMap 会进行扩容
新的容量将是 32（即 16 的两倍），新的阈值将是 32 * 0.75 = 24
5.5 [1]HashMap是先插入元素还是先扩容
01.HashMap是先插入元素还是先扩容？
a.情况1
首次插入数据时，则【先扩容再插入数据】
b.情况2
每当插入的数据个数达到阈值时，就会发生扩容，则【先插入数据再扩容】
5.6 [2]HashMap的get方法：O(1)
01.HashMap的get方法
1.对key的hashCode进行哈希运算
2.借助与运算计算下标获取bucket位置
如果在桶的首位上就可以找到就直接返回
否则，在树或者链表中遍历找。如果有hash冲突，则利用equals方法遍历查找节点
5.7 [2]HashMap的put过程
01.Map的put过程
1.基于key的hashcode值计算哈希值（与Key.hashCode的高16位做异或运算）
2.如果散列表为空时，调用resize()初始化散列表
3.如果没有发生哈希碰撞(hash值相同)，直接添加元素到散列表中去
4.如果发生了哈希碰撞，进行三种判断
4.1.若key地址相同或者equals后内容相同，则替换旧值
4.2.如果是红黑树结构，就调用树的插入方法
4.3.链表结构
循环遍历直到链表中某个节点为空，尾插法进行插入，插入之后判断链表是否树化：
当链表长度不小于 8且数组长度不小于64时，链表转换为红黑树。
5.如果桶满了，即元素个数大于阈值，则resize进行扩容
02.说明
hashCode：定位，用于确认数组下标
equals：定性，比较两者是否相等
5.8 [2]HashMap为什么不安全
02.hashmap为什么线程不安全
HashMap在并发执行put操作时，可能会导致形成【循环链表】
5.9 [2]如果不是2的幂会怎么样
01.如果输入值不是2的幂比如10会怎么样
a.回答
输入数据若不是2的幂，HashMap通过一通位移运算和或运算得到的肯定是2的幂次数，并且是离那个数最近的数字
等价于length取模
b.原因
当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，
但是&比%具有更高的效率。位运算的运算效率高于算术运算，原因是算术运算还是会被转化为位运算。
最终目的还是为了让哈希后的结果更均匀的分部，减少哈希碰撞，提升hashmap的运行效率
5.10 [2]为什么槽位数必须使用2^n？
01.为什么槽位数必须使用2^n
a.回答
便于计算索引：(n-1) & hash
散列更均匀，减少哈希碰撞
扩容时重哈希更高效
b.原因
因为确定数组位置使用的位运算，若数据不是2的次幂则会增加哈希碰撞的次数和浪费数组空间
5.11 [2]HashMap解决哈希冲突
00.汇总
在HashMap中，主要通过链地址法（拉链法）来解决哈希冲突，同时结合了红黑树优化性能
01.四种方法
a.开放定址法
这种方法也称为再散列法，它的核心思想是当发生冲突时，寻找一个新的空闲哈希地址
如果初始的哈希地址p出现了冲突，就以p为基础，通过一定的规则生成新的哈希地址p1
如果p1仍然冲突，则继续生成p2，如此循环，直至找到一个不冲突的地址为止
b.链地址法
这种方法将所有哈希到同一地址的记录链接在同一链表中
这样，即使多个记录的哈希值相同，它们也可以通过链表结构进行存储和访问
c.建立公共溢出区
此方法将哈希表分为基本表和溢出表两部分。当发生冲突时，将数据存放在溢出表中，以此来解决冲突问题
d.再散列法
这是一种特殊的开放定址法，它在发生冲突时使用不同的散列函数来计算新的地址，直到找到空位为止
5.12 [2]HashMap不使用对象作为Key
01.对象作为HashMap的键需要满足一些条件
不可变性：对象的属性不能被修改，因为如果属性被修改，那么原有的键值对在哈希表中就会失效
可哈希性：对象必须能够被哈希，即它的哈希码必须是确定的，且在对象被创建后不会改变
02.不建议原因
可变对象可能导致数据的不一致性
使用固定的ID作为键可以避免数据的不一致性
使用弱引用或者弱引用集合可以避免垃圾回收对数据的影响
5.13 [3]HashMap：红黑树
01.红黑树
每个节点非红即黑
根节点总是黑色的
如果节点是红色的，则它的子节点必须是黑色的（反之不一定）
每个叶子节点都是黑色的空节点（NIL节点）
从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）
5.14 [3]HashMap：红黑树引入原因
00.回答
红黑树，哈希冲突优化；利用红黑树的【自平衡性】，将O(n)变成O(log n)
01.JDK7
数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布
当HashMap中有大量的元素发生哈希碰撞时，这些元素都被存放到同一个桶中，
从而形成一条长长的链表，此时HashMap就相当于一个单链表，遍历的时间复杂度会退化到O(n)，完全失去了它的优势
02.JDK8
引入了红黑树，红黑树的好处就是【自平衡性】，n个节点的树的查找时间复杂度只有O(log n)
5.15 [3]HashMap：链表转换为红黑树
01.链表会转换成红黑树，2个条件
1.链表长度不小于8
2.数组长度大于64
02.当链表长度不小于8并且数组长度大于64时，链表会转换成红黑树
1.HashMap【初始化时使用懒加载机制，只初始化变量】，未初始化数组，数组在首次添加元素时初始化
2.存储键值对，实现快速存取。key值不可重复，若key值重复则覆盖
3.键和值位置都可以是null，但是键位置只能存在唯一一个null
4.非同步，线程不安全
5.底层是hash表，不保证有序(比如插入的顺序)
6.链表长度不小于8并且数组长度大于64，才将链表转换成红黑树，变成红黑树的目的是提高搜索速度，高效查询
5.16 [3]HashMap：JDK7与8区别
00.总结
| 特性 | JDK 1.7 | JDK 1.8
|--------------------|---------------------------------|------------------------
| 底层数据结构 | Entry数组+单链表 | Node数组+单链表+红黑树（红黑树，哈希冲突优化）
| 链表处理方式 | 链表处理哈希冲突，查询效率 O(n) | 链表 + 红黑树，查询效率 O(log n)
| 扩容时链表插入方式 | 头插法，可能导致死循环 | 尾插法，避免死循环
| 哈希算法 | 简单取模 | 高位扰动算法，减少哈希冲突
| 线程安全问题 | 存在死循环和数据丢失问题 | 修复了死循环问题，但仍非线程安全
| 性能 | 哈希冲突严重时性能下降 | 引入红黑树后性能更稳定
01.数据结构
a.JDK7
HashMap 的底层是 数组 + 链表 的结构
每个桶（bucket）是一个链表，当发生哈希冲突时，新的键值对会被添加到链表的末尾
如果链表长度过长（如所有键的哈希值都映射到同一个桶），会导致查询效率从 O(1) 降到 O(n)
b.JDK8
HashMap 的底层改为 数组 + 链表 + 红黑树 的结构
红黑树的查询效率是 O(log n)，相比链表的 O(n)，查询效率更高
-----------------------------------------------------------------------------------------------------
当链表长度超过阈值（默认 8）且数组容量大于等于 64 时，链表转换为红黑树，以提高查询效率
如果红黑树的节点数量减少到 6 以下，红黑树会恢复为链表
c总结
JDK7使用 数组 + 链表
JDK8使用 数组 + 链表 + 红黑树，优化了极端情况下的性能
02.扩容机制
a.JDK7
当 HashMap 中的元素数量超过 容量 * 加载因子（默认 0.75） 时，会触发扩容
扩容时，HashMap 的容量会翻倍，并重新计算所有元素的哈希值，将它们重新分配到新的桶中
在JDK7中，扩容时采用 头插法 重新构建链表：
新的节点会被插入到链表的头部。
这种方式会导致链表中的元素顺序与插入顺序相反。
在多线程环境下，可能会导致 死循环（链表节点形成环形结构）
b.JDK8
JDK8也会在 容量 * 加载因子 超过阈值时触发扩容
扩容时，采用 尾插法 重新构建链表：
新的节点会被插入到链表的尾部
这种方式可以保持链表中元素的顺序一致
同时，扩容过程对并发问题的处理更安全，不会导致死循环
03.哈希冲突优化
a.JDK7
采用链表处理哈希冲突，多个哈希值相同的元素会被存储在同一个桶的链表中
链表的查询时间复杂度是 O(n)
b.JDK8
引入了红黑树，当链表长度超过阈值（默认 8）时，会将链表转换为红黑树
红黑树的查询时间复杂度是 O(log n)，极大地提升了性能
如果链表长度小于 6，则红黑树会退化回链表
c.总结：
JDK7使用链表处理哈希冲突，查询效率较低
JDK8引入红黑树优化了哈希冲突，查询效率更高
04.并发环境下的表现
a.JDK7
HashMap在多线程环境下可能会出现问题
死循环问题：在扩容时，如果两个线程同时对 HashMap 进行操作，可能会导致链表形成环形结构，进而导致死循环
数据丢失：由于没有同步机制，多个线程同时操作可能导致数据覆盖或丢失
b.JDK8
JDK8修复JDK7的死循环问题
通过使用 尾插法 替代头插法，避免了扩容时链表结构被破坏的问题
但 HashMap 仍然不是线程安全的。如果需要线程安全的哈希表，可以使用
ConcurrentHashMap：提供线程安全的实现
Collections.synchronizedMap：将 HashMap 包装成线程安全的版本
c.总结：
JDK7存在死循环和数据丢失问题
JDK8修复了死循环问题，但仍然不保证线程安全
05.哈希算法的改进
a.JDK7
使用对象的 hashCode() 方法计算哈希值后，通过简单的取模运算决定元素存储在哪个桶中
高位的哈希值可能对桶的分布产生较大的影响，容易导致哈希冲突
b.JDK8
引入了 高位扰动算法（hash perturbation），对 hashCode() 的结果进行进一步计算
c.总结
JDK8的哈希算法更优化，减少了哈希冲突的发生
06.其他优化
a.遍历效率：
JDK8的HashMap在迭代时效率更高，尤其是当链表被转换为红黑树后，查询和遍历性能提升明显
b.代码实现：
JDK8对HashMap的内部代码结构进行了重构，使代码更简洁易读
6 ConcurrentHashMap：并发哈希映射，读多写少，无锁并发编程
6.1 [1]原理
01.介绍
ConcurrentHashMap是一种线程安全的哈希表实现，适用于高并发场景
它通过【分段锁机制】来实现高效的并发访问，避免了传统Hashtable的全表锁定问题
02.特点
线程安全：ConcurrentHashMap通过【写时复制】机制实现线程安全，适用于【读多写少】的场景
读操作高效：读操作无锁，提供了高效的并发读操作
写操作开销大：写操作需要复制整个数组，开销较大，不适用于写操作频繁的场景
03.主要特性
线程安全：ConcurrentHashMap通过分段锁机制保证线程安全，允许多个线程并发地读取和写入
高性能：相比于 Hashtable，ConcurrentHashMap 提供了更高的并发性能，减少了锁竞争
无锁读操作：大多数【读操作不需要加锁】，进一步提高了性能
04.内部结构
1.数组（Node<K,V>[] table） 存储键值对的数组，每个元素是一个链表或红黑树的头节点
2.链表和红黑树 解决哈希冲突，链表长度超过阈值时转换为红黑树
3.分段锁（synchronized 和 CAS） 通过细粒度的锁机制实现高并发访问
05.工作原理
a.初始化
ConcurrentHashMap在第一次插入元素时进行初始化，创建一个大小为 2 的幂次方的数组
b.插入操作
计算键的哈希值，确定数组索引
如果该位置为空，通过 CAS 操作插入新节点
如果该位置不为空，使用 synchronized 锁定该链表或红黑树，进行插入操作
c.读取操作
计算键的哈希值，确定数组索引
直接读取该位置的链表或红黑树，查找对应的键值对
读取操作大多数情况下不需要加锁
d.扩容
当数组中的元素数量超过一定阈值时，触发扩容操作
创建一个新的、更大的数组，将旧数组中的元素重新分配到新数组中
扩容过程中，使用分段锁机制保证线程安全
6.2 [1]常用API
01.构造函数
ConcurrentHashMap(): 创建一个新的空映射，默认初始容量和负载因子
ConcurrentHashMap(int initialCapacity): 创建具有指定初始容量的映射
ConcurrentHashMap(int initialCapacity, float loadFactor): 创建具有指定初始容量和负载因子的映射
ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel): 创建具有指定初始容量、负载因子和并发级别的映射
02.基本操作
V put(K key, V value): 将指定的值与此映射中的指定键关联
V get(Object key): 返回指定键所映射的值，如果此映射不包含该键的映射，则返回 null
V remove(Object key): 如果存在，则移除指定键的映射
boolean containsKey(Object key): 如果此映射包含指定键的映射，则返回 true
boolean containsValue(Object value): 如果此映射为一个或多个键映射指定值，则返回 true
boolean isEmpty(): 如果此映射不包含键-值映射，则返回 true
int size(): 返回此映射中的键-值映射数
03.高级操作
V putIfAbsent(K key, V value): 如果指定键尚未与值关联，则将其与给定值关联
boolean remove(Object key, Object value): 仅当指定键已与指定值关联时，才移除该键的条目
boolean replace(K key, V oldValue, V newValue): 仅当指定键已与某个值关联时，才替换为新值
V replace(K key, V value): 仅当指定键已与某个值关联时，才替换为新值
04.批量操作
void forEach(long parallelismThreshold, BiConsumer<? super K, ? super V> action): 对每个键-值对执行给定的操作
void replaceAll(BiFunction<? super K, ? super V, ? extends V> function): 使用给定的函数替换每个条目的值
V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction): 尝试计算指定键及其当前映射值的新映射
V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction): 如果指定键尚未与值关联，则尝试使用给定的映射函数计算其值
V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction): 如果指定键的值存在且非 null，则尝试计算新值
05.其他操作
Set<K> keySet(): 返回此映射中包含的键的 Set 视图
Collection<V> values(): 返回此映射中包含的值的 Collection 视图
Set<Map.Entry<K, V>> entrySet(): 返回此映射中包含的映射关系的 Set 视图
6.3 [1]线程安全性
00.汇总
CAS操作和红黑树（JDK8）取代 分段锁机制（JDK7）
红黑树结构
锁粒度
无锁读操作
分段扩容
01.主要机制
a.CAS操作和红黑树（JDK8） 取代 分段锁机制（JDK7）
JDK8中的ConcurrentHashMap使用CAS（Compare-And-Swap）操作和红黑树来替代分段锁机制
当链表长度超过一定阈值（默认8）时，链表会转换为红黑树，以提高查找和插入性能
b.红黑树
ConcurrentHashMap由一个Node数组和链表/红黑树组成
每个Node维护一个键值对，链表用于解决哈希冲突，链表长度超过阈值时转换为红黑树
c.锁粒度
锁粒度更细，通过CAS操作和synchronized锁定单个节点或链表，提高并发性
读操作大多数情况下无锁，提高了读操作的性能
d.无锁读操作
大多数读操作（如 get 方法）在 JDK 8 中是无锁的，通过 volatile 变量和 CAS 操作来保证可见性和一致性
这大大提高了读操作的性能
e.分段扩容
在JDK8中，ConcurrentHashMap使用分段扩容机制，避免全表扩容带来的性能问题
扩容时，多个线程可以同时进行扩容操作，提高扩容效率
02.具体实现
a.插入操作
计算键的哈希值，确定数组索引
如果该位置为空，通过CAS操作插入新节点
如果该位置不为空，使用synchronized锁定该链表或红黑树，进行插入操作
b.读取操作
计算键的哈希值，确定数组索引
直接读取该位置的链表或红黑树，查找对应的键值对
读取操作大多数情况下不需要加锁
c.删除操作
计算键的哈希值，确定数组索引
使用synchronized锁定该链表或红黑树，进行删除操作
6.4 [1]线程并发度：默认16线程
01.并发度
ConcurrentHashMap可以同时进行写操作的线程数
在JDK7中，通过【分段锁】实现并发度
在JDK8中，通过【细粒度锁】和【CAS操作】实现更高的并发度
02.最大线程数，默认为16
程序运行时能够同时更新ConccurentHashMap且不产生锁竞争的最大线程数，默认为16，且可以在构造函数中设置
当用户设置并发度时，ConcurrentHashMap会使用大于等于该值的最小2次幂指数作为实际并发度
（假如用户设置并发度为17，实际并发度则为32）
6.5 [2]并发扩容：存储对象过程
01.ConcurrentHashMap存储对象的过程
1.如果没有初始化，就调用 initTable() 方法来进行初始化
2.如果没有哈希冲突就直接 CAS 无锁插入
3.如果需要扩容，就先进行扩容
4.如果存在哈希冲突，就加锁来保证线程安全，两种情况：一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入
5.如果该链表长度大于阀值 8（且数组中元素数量大于64），就要先转换成红黑树的结构
6.6 [1]并发扩容：分段扩容、扩容戳
01.介绍
ConcurrentHashMap的扩容机制在JDK8中进行了显著改进，以支持【并发扩容】操作
扩容是指当哈希表中的元素数量超过一定阈值时，创建一个更大的数组，并将旧数组中的元素重新分配到新数组中
JDK8中的ConcurrentHashMap通过【分段扩容、扩容戳】来实现高效的并发扩容
02.扩容机制
a.触发扩容
当插入新元素时，如果当前数组的元素数量超过了负载因子（默认0.75）乘以数组长度的阈值，触发扩容操作
b.分段扩容
JDK8中的ConcurrentHashMap采用分段扩容机制，允许多个线程同时进行扩容操作
每个线程负责将旧数组中的一部分元素迁移到新数组中，从而提高扩容效率
c.扩容戳
扩容戳是一个标识符，用于标记当前扩容操作的状态
扩容戳由数组的大小和扩容次数共同决定，确保扩容操作的唯一性和一致性
03.扩容过程
a.初始化扩容
当需要扩容时，首先计算扩容戳，并将其存储在sizeCtl变量中
创建一个新的、更大的数组，并将其引用存储在nextTable变量中
b.迁移元素
每个线程在扩容时，首先检查nextTable是否为空，如果为空则初始化扩容
线程通过CAS操作获取迁移任务，每个任务负责迁移旧数组中的一部分元素
迁移过程中，线程将旧数组中的元素重新哈希并插入到新数组中
c.完成扩容
当所有元素都迁移完成后，线程将新数组引用赋值给table变量，并更新sizeCtl变量，表示扩容完成
04.扩容戳的作用
a.标识扩容状态
扩容戳用于标识当前扩容操作的状态，确保扩容操作的唯一性和一致性
通过扩容戳，可以避免多个线程重复初始化扩容操作
b.协调并发扩容
扩容戳用于协调多个线程的并发扩容操作，确保每个线程都能正确地参与扩容
通过扩容戳，可以确保扩容操作的有序进行，避免数据不一致性
6.7 [2]put过程
01.put过程
a.计算哈希值
计算键的哈希值，确定数组索引
b.检查是否需要初始化
如果数组未初始化，则通过 CAS 操作初始化数组
c.插入元素
如果目标位置为空，通过 CAS 操作插入新节点
如果目标位置不为空，使用 synchronized 锁定该链表或红黑树，进行插入操作
如果链表长度超过阈值（默认 8），转换为红黑树
d.扩容检查
插入元素后，检查是否需要扩容，如果需要则触发扩容操作
6.8 [2]put过程：加锁
01.put过程加锁
JDK7：分段锁
JDK8：CAS操作和synchronized锁
02.put过程及其加锁机制
a.计算哈希值
计算键的哈希值，并确定该键应该放入哪个桶（Bucket）
b.检查桶是否初始化
如果桶未初始化，使用 CAS 操作初始化桶
c.遍历桶中的链表或树
如果桶已经初始化，遍历桶中的链表或树，检查是否存在相同的键
如果找到相同的键，更新其值，并返回旧值
d.插入新节点
如果未找到相同的键，使用 synchronized 锁对桶进行加锁，确保只有一个线程可以插入新节点
插入新节点后，释放锁
e.树化
如果链表长度超过阈值（默认为 8），将链表转换为红黑树，以提高查找效率
f.扩容
如果负载因子超过阈值，触发扩容操作，重新分配桶，并将现有节点重新分配到新的桶中
6.9 [2]get过程
01.get过程
a.计算哈希值
计算键的哈希值，确定数组索引
b.查找元素
直接读取目标位置的链表或红黑树，查找对应的键值对
如果目标位置为空，返回 null
如果目标位置不为空，遍历链表或红黑树，查找匹配的键
6.10 [2]get过程：不加锁
01.get方法不加锁
1.ConcurrentHashMap的get方法大多数情况下不需要加锁
2.通过volatile变量和CAS操作保证可见性和一致性
3.读操作不需要加锁，提高了读操作的性能
02.原因
因为Node的元素value和指针next是用volatile修饰的
在多线程环境下线程A修改节点的value或者新增节点的时候是对线程B可见的
这也是它比其它并发集合比如Hashtable、用Collections.synchronizedMap()包装的HashMap效率高的原因之一
6.11 [3]JDK7与8区别
00.总结
在JDK8中通过引入【CAS操作、红黑树、更细粒度的锁机制】，显著提高了并发性能和扩容效率
01.JDK7中的ConcurrentHashMap
a.分段锁（Segmented Locking）
JDK7中的ConcurrentHashMap使用分段锁机制，将整个哈希表分为多个段（Segment），每个段维护一个独立的哈希表和锁
这种设计允许多个线程同时访问不同段，从而提高并发性
b.结构
ConcurrentHashMap由一个Segment数组和多个HashEntry链表组成
每个Segment维护一个独立的哈希表和锁
c.锁粒度
锁粒度较粗，每个段有一个独立的锁，操作时需要锁定整个段
08.JDK8中的ConcurrentHashMap
a.CAS操作和红黑树（JDK8） 取代 分段锁机制（JDK7）
JDK8中的ConcurrentHashMap使用CAS（Compare-And-Swap）操作和红黑树来替代分段锁机制
当链表长度超过一定阈值（默认8）时，链表会转换为红黑树，以提高查找和插入性能
b.红黑树
ConcurrentHashMap由一个Node数组和链表/红黑树组成
每个Node维护一个键值对，链表用于解决哈希冲突，链表长度超过阈值时转换为红黑树
c.锁粒度
锁粒度更细，通过CAS操作和synchronized锁定单个节点或链表，提高并发性
读操作大多数情况下无锁，提高了读操作的性能
d.无锁读操作
大多数读操作（如 get 方法）在 JDK 8 中是无锁的，通过 volatile 变量和 CAS 操作来保证可见性和一致性
这大大提高了读操作的性能
e.分段扩容
在JDK8中，ConcurrentHashMap使用分段扩容机制，避免全表扩容带来的性能问题
扩容时，多个线程可以同时进行扩容操作，提高扩容效率
6.12 [3]Hashtable锁机制
01.介绍
Hashtable是Java中一种线程安全的哈希表实现
它通过同步机制保证线程安全，但这种同步机制也导致了较高的锁竞争，从而影响性能
Hashtable的锁机制主要依赖于方法级别的同步，即在每个方法上使用synchronized关键字
02.锁机制
a.全表锁
Hashtable 使用全表锁机制，每次读写操作都需要锁定整个哈希表
这意味着每次对Hashtable的操作（如 put、get、remove 等）都需要获取对象级别的锁
这种同步机制确保了线程安全，但也导致了较高的锁竞争，尤其是在高并发环境下
b.方法级别的同步
Hashtable中的所有读写方法都使用synchronized关键字进行同步
这意味着每次操作都需要获取对象级别的锁，其他线程必须等待锁释放后才能进行操作
这种锁机制保证了同一时刻只有一个线程可以对Hashtable进行操作，从而避免了数据不一致的问题
03.性能影响
a.高锁竞争
由于Hashtable使用全表锁机制，每次操作都需要获取对象级别的锁
在高并发环境下，多个线程同时访问Hashtable时，会导致较高的锁竞争，从而影响性能
b.低并发性能
由于每次操作都需要获取锁，Hashtable的并发性能较低
多个线程同时访问Hashtable时，只有一个线程能够获取锁并进行操作，其他线程必须等待锁释放
c.替代方案ConcurrentHashMap
ConcurrentHashMap是Hashtable 的高性能替代方案
它通过分段锁、CAS操作和细粒度锁机制，实现了高效的并发访问
ConcurrentHashMap提供了更高的并发性能，适用于高并发环境
04.代码示例
import java.util.Hashtable;
public class HashtableExample {
public static void main(String[] args) {
Hashtable<String, Integer> hashtable = new Hashtable<>();
// 插入键值对
hashtable.put("one", 1);
hashtable.put("two", 2);
// 获取值
System.out.println("Value for key 'one': " + hashtable.get("one"));
}
}
class SimplifiedHashtable<K, V> {
private final Entry<K, V>[] table;
public synchronized V put(K key, V value) {
// 插入键值对的逻辑
// 获取对象级别的锁
// 插入或更新键值对
return null;
}
public synchronized V get(Object key) {
// 获取值的逻辑
// 获取对象级别的锁
// 查找并返回对应的值
return null;
}
private static class Entry<K, V> {
final K key;
V value;
Entry<K, V> next;
Entry(K key, V value, Entry<K, V> next) {
this.key = key;
this.value = value;
this.next = next;
}
}
}
6.13 [3]比Hashtable效率高
01.ConcurrentHashMap更高效
a.ConcurrentHashMap
1.通过【分段锁、CAS 操作和细粒度锁机制】，实现了高效的并发访问
2.大多数情况下【读操作无锁】，提高了读操作的性能
b.Hashtable
使用【全表锁】，【每次读写操作都需要锁定整个哈希表】，导致锁竞争严重，性能较低
6.14 [3]ConcurrentHashMap锁机制
00.加锁的场景分为两种
1.没有发生hash冲突
2.发生hash冲突
01.场景1：没有发生hash冲突
没有发生hash冲突的时候，添加元素的位置在数组中是空的，使用CAS的方式来加入元素，这里加锁的粒度是数组中的元素
02.场景2：发生hash冲突，使用的是synchronized加锁
如果出现了hash冲突，添加的元素的位置在数组中已经有了值，那么又存在三种情况：
1.key相同，则用新的元素覆盖旧的元素。
2.如果数组中的元素是链表的形式，那么将新的元素挂载在链表尾部。
3.如果数组中的元素是红黑树的形式，那么将新的元素加入到红黑树。
6.15 [4]迭代器是弱一致性
01.迭代器是强一致性还是弱一致性？
a.回答
弱一致性
b.说明
迭代过程中，其他线程对ConcurrentHashMap的修改可能会被迭代器看到，但不会抛出ConcurrentModificationException
迭代器保证在创建时的快照基础上进行迭代，但不保证实时一致性
6.16 [4]为什么不能插入null
01.为什么ConcurrentHashMap不能插入null？
a.回答
因为【源码就是这样设计的】
【在并发编程中。null值容易引来歧义】
当【key或value为null时，会直接抛出空指针异常】
b.说明
在 Java 中，Map 是属于 java.util 包下的一个接口（interface），
所以说“为什么 Map 不能插入 null？”这个问题本身问的不严谨。
所以，这里面试官其实想问的是：为什么 ConcurrentHashMap 不能插入 null？
c.HashMap和ConcurrentHashMap的区别
在 HashMap 中，key 和 value 值都可以为 null。
在 ConcurrentHashMap 中，key 或者是 value 值都不能为 null。
d.为什么不能插入null？
以下是 ConcurrentHashMap 添加元素时的部分核心源码：
// 添加 key 和 value
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
// 如果 key 或 value 为 null 的话直接抛出空指针异常
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
// 忽略其他代码......
}
从上述 ConcurrentHashMap 添加元素的第一行源码就可以看出，
当 key 或 value 为 null 时，会直接抛出空指针异常，这就是 ConcurrentHashMap 之所以不能插入 null 的根本原因了，
因为源码就是这样设计的。
e.更深层次的原因
在 Java 中，ConcurrentHashMap 是用于并发环境中执行的线程安全的容器，
而 HashMap 是用于单线程环境下执行的非线程安全的容器，而并发环境下的运行更复杂，
如果我们允许 ConcurrentHashMap 的 key 或者是 value 为 null 的情况下，就会存在经典的“二义性问题”。
-----------------------------------------------------------------------------------------------------
所谓的二义性问题指的是代码或表达式存在多种理解或解释，导致程序的含义不明确或模糊。
以 ConcurrentHashMap 不允许为 null 的二义性问题来说，null 其实有以下两层含义：
这个值本身设置的是 null，null 在这里表示的是一种具体的“null”值状态。
null 还表示“没有”的意思，因为没有设置，所以啥也没有。
所以，如果 ConcurrentHashMap 允许插入 null 值，那么就会存在二义性问题。
那就有同学会问了，为什么 HashMap 允许插入 null，它就不怕有二义性问题吗？
-----------------------------------------------------------------------------------------------------
可证伪的HashMap
HashMap 之所以不怕二义性问题的原因是，HashMap 的设计是给单线程使用的，
而单线程下的二义性问题是能被证明真伪的，所以也就不存在二义性问题了（能被证明的问题就不是二义性问题）。
例如，当我们给 HashMap 的 key 设置为 null 时，我们可以通过 hashMap.containsKey(key) 的方法来区分
这个 null 值到底是存入的 null？还是压根不存在的 null？这样二义性问题就得到了解决，
所以 HashMap 的二义性问题可被证明真伪，所以就不怕二义性问题，因此也就可以给 key 或者 value 设置 null 了。
-----------------------------------------------------------------------------------------------------
不可证伪的ConcurrentHashMap
而 ConcurrentHashMap 就不一样了，因为 ConcurrentHashMap 是设计在多线程下使用的，
而多线程下的二义性问题是不能被证明真伪的，所以二义性问题是真实存在的。
因为在你在证明二义性问题的同时，可能会有另一个线程影响你的执行结果，所以它的二义性问题就一直存在。
6.17 [4]用显式锁ReentrantLock确保迭代remove的线程安全
01.说明
a.创建显式锁
使用ReentrantLock创建一个显式锁lock
b.在迭代过程中使用显式锁
在迭代过程中，使用lock.lock()获取锁，确保只有一个线程可以进行迭代和remove操作
在try块中进行迭代和remove操作，确保在操作过程中持有锁
在finally块中使用lock.unlock()释放锁，确保锁在操作完成后被释放
c.确保线程安全
通过显式锁，确保在迭代过程中进行remove操作时的线程安全，避免数据不一致性问题
02.代码示例
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class CopyOnWriteArrayListWithLockExample {
public static void main(String[] args) {
List<String> list = new CopyOnWriteArrayList<>();
Lock lock = new ReentrantLock();
// 添加元素
list.add("one");
list.add("two");
list.add("three");
// 读取元素
for (String element : list) {
System.out.println(element);
}
// 修改元素
list.set(1, "two updated");
// 删除元素
list.remove("three");
// 读取元素
for (String element : list) {
System.out.println(element);
}
// 在迭代过程中进行 remove 操作，使用显式锁确保线程安全
lock.lock();
try {
for (String element : list) {
if ("two updated".equals(element)) {
list.remove(element); // 使用显式锁确保线程安全
}
}
} finally {
lock.unlock();
}
// 读取元素
for (String element : list) {
System.out.println(element);
}
}
}
6.18 [4]用内置锁synchronized确保迭代remove的线程安全
01.说明
a.创建ConcurrentHashMap
创建一个ConcurrentHashMap实例，并插入一些键值对
b.使用内置锁synchronized
使用synchronized关键字对map进行同步，确保在迭代过程中只有一个线程可以进行操作
在synchronized块中，使用迭代器遍历map的键集，并在满足条件时调用迭代器的remove方法进行删除操作
c.确保线程安全
通过使用内置锁synchronized，确保在迭代和remove操作过程中只有一个线程可以进行操作，从而避免数据不一致性问题
02.代码示例
import java.util.Iterator;
import java.util.concurrent.ConcurrentHashMap;
public class ConcurrentHashMapWithSynchronizedExample {
public static void main(String[] args) {
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
// 插入键值对
map.put("one", 1);
map.put("two", 2);
map.put("three", 3);
// 读取并打印所有键值对
System.out.println("Initial map:");
for (String key : map.keySet()) {
System.out.println(key + " : " + map.get(key));
}
// 使用内置锁 synchronized 确保迭代过程中 remove 操作的线程安全
synchronized (map) {
Iterator<String> iterator = map.keySet().iterator();
while (iterator.hasNext()) {
String key = iterator.next();
if ("two".equals(key)) {
iterator.remove(); // 使用迭代器的 remove 方法
}
}
}
// 读取并打印所有键值对
System.out.println("Map after removal:");
for (String key : map.keySet()) {
System.out.println(key + " : " + map.get(key));
}
}
}
6.19 [4]JDK8要使用内置锁synchronized来代替重入锁ReentrantLock
01.粒度降低了
每扩容一次，ConcurrentHashMap的并发度就增加一倍
02.获得JVM的支持
在大量的数据操作下，对于 JVM 的内存压力，基于 API 的 可重入锁 ReentrantLock 会开销更多的内存
而且后续的性能优化空间更小。而且JVM 开发团队没有放弃 synchronized，JVM能够在运行时做出更大的优化空间更大
锁粗化、锁消除、锁自旋等等，这就使得synchronized能够随着JDK版本的升级而重构代码的前提下获得性能上的提升
03.减少内存开销
假如使用可重入锁获得同步支持，那么每个节点都需要通过继承AQS来获得同步支持
但并不是每个节点都需要获得同步支持的，只有链表的头结点（红黑树的根节点）需要同步，这无疑造成了巨大的内存开销
6.20 [4]为什么CopyOnWriteArrayList并不是完全意义上的线程安全
00.回答
remove操作会【创建一个新的底层数组，并在新数组上进行删除操作】
如果在迭代过程中进行remove操作，【可能会导致数据不一致性问题】，因为迭代器的快照和实际列表之间存在差异
01.为什么CopyOnWriteArrayList并不是完全意义上的线程安全
a.写时复制机制
CopyOnWriteArrayList 在进行写操作（如 add、set、remove 等）时，会创建一个新的底层数组，并在新数组上进行修改操作
修改完成后，将新数组替换为底层数组。这种机制确保了写操作的线程安全，但也带来了较高的开销
b.迭代器的弱一致性
CopyOnWriteArrayList 的迭代器是弱一致性的，即在迭代过程中，如果有其他线程对列表进行了修改，迭代器不会抛出 ConcurrentModificationException
迭代器会在创建时的快照基础上进行迭代，但不会反映后续的修改
c.remove操作的特殊性
remove操作会【创建一个新的底层数组，并在新数组上进行删除操作】
如果在迭代过程中进行remove操作，【可能会导致数据不一致性问题】，因为迭代器的快照和实际列表之间存在差异
02.使用remove操作时的注意事项
a.避免在迭代过程中进行remove操作
在迭代过程中进行remove操作可能会导致数据不一致性问题，应该尽量避免这种情况
b.使用显式锁
如果必须在迭代过程中进行remove操作，可以使用显式锁来确保线程安全
7 Queue：队列
7.1 [0]非阻塞队列、阻塞队列
01.非阻塞队列
队列类型 中文名 特点 线程 适用场景
ArrayDeque 数组双端队列 基于数组，无界，非阻塞，支持双端操作 线程不安全 需要高效双端队列操作的场景
LinkedList 链表 基于双向链表，无界，非阻塞，支持双端操作 线程不安全 需要双端队列操作的场景
PriorityQueue 优先级队列 基于优先级堆，无界，非阻塞，支持优先级排序 线程不安全 需要优先级排序的场景
ConcurrentLinkedQueue 并发链表队列 基于链表，无界，非阻塞，使用 CAS 操作 线程安全 高并发场景下的队列操作
ConcurrentLinkedDeque 并发链表双端队列 基于链表，无界，非阻塞，支持双端操作 线程安全 高并发场景下需要双端队列操作的场景
ConcurrentSkipListQueue 并发跳表队列 基于跳表，无界，非阻塞，支持元素有序性 线程安全 需要有序性和高并发的场景
02.阻塞队列
队列类型 中文名 特点 线程 适用场景
ArrayBlockingQueue 基于数组的阻塞队列 基于数组，有界，单锁 线程安全 需要有界队列的场景
LinkedBlockingQueue 基于链表的阻塞队列 基于链表，有界或无界，双锁 线程安全 高并发场景
LinkedBlockingDeque 基于链表的阻塞双端队列 基于链表，有界或无界，支持双端操作 线程安全 需要双端队列操作的高并发场景
LinkedTransferQueue 链表传输队列 基于链表，无界，支持生产者等待消费者接收元素 线程安全 需要生产者等待消费者接收元素的场景
PriorityBlockingQueue 优先级阻塞队列 基于优先级堆，无界，支持优先级排序 线程安全 需要优先级排序的场景
SynchronousQueue 同步队列 容量为零，每次插入操作必须等待对应的移除操作 线程安全 需要严格同步的场景
DelayQueue 延迟队列 基于优先级堆，无界，支持延迟获取元素 线程安全 需要延迟处理任务的场景
7.2 [1]ArrayDeque：数组双端队列
01.常用信息1
a.定义
ArrayDeque 是一个基于数组的无界非阻塞双端队列
它实现了 Deque 接口，支持在队列的两端进行插入和删除操作
ArrayDeque 是线程不安全的，需要在多线程环境中使用时进行外部同步
b.原理
ArrayDeque 使用动态数组作为其底层数据结构
数组的容量会根据需要自动扩展，以适应元素的增加
插入和删除操作通过调整数组的索引来实现
ArrayDeque 提供了高效的双端队列操作，插入和删除操作的时间复杂度为 O(1)
-----------------------------------------------------------------------------------------------------
由于 ArrayDeque 是基于数组的，
因此它提供了比链表实现的双端队列更高的缓存局部性，从而在某些情况下具有更高的性能
c.常用API
a.双端队列操作
void addFirst(E e): 将指定的元素插入到队列的头部
void addLast(E e): 将指定的元素插入到队列的尾部
boolean offerFirst(E e): 将指定的元素插入到队列的头部
boolean offerLast(E e): 将指定的元素插入到队列的尾部
E pollFirst(): 获取并移除此队列的头部元素，如果此队列为空，则返回 null
E pollLast(): 获取并移除此队列的尾部元素，如果此队列为空，则返回 null
E peekFirst(): 获取但不移除此队列的头部元素，如果此队列为空，则返回 null
E peekLast(): 获取但不移除此队列的尾部元素，如果此队列为空，则返回 null
b.队列操作
boolean offer(E e): 将指定的元素插入到队列的尾部
E poll(): 获取并移除此队列的头部元素，如果此队列为空，则返回 null
E peek(): 获取但不移除此队列的头部元素，如果此队列为空，则返回 null
c.栈操作
void push(E e): 将元素推入此双端队列表示的栈（即插入到队列的头部）
E pop(): 从此双端队列表示的栈中弹出一个元素（即移除并返回队列的头部元素）
d.详情
a.线程不安全
ArrayDeque 是线程不安全的，如果在多线程环境中使用，需要外部同步
b.动态数组
ArrayDeque 使用动态数组作为其底层数据结构，支持高效的插入和删除操作
c.灵活性
ArrayDeque 实现了 Deque 接口，可以用作双端队列和栈
d.性能
插入和删除操作的时间复杂度为 O(1)，提供了比链表实现的双端队列更高的缓存局部性
02.常用信息2
a.应用场景
a.需要高效双端队列操作
在需要高效双端队列操作的场景中，ArrayDeque 提供了高性能的操作
b.栈操作
在需要栈操作的场景中，ArrayDeque 提供了灵活的操作方式
c.队列操作
在需要队列操作的场景中，ArrayDeque 提供了完整的 Deque 接口实现
b.代码示例
import java.util.ArrayDeque;
import java.util.Deque;
public class ArrayDequeExample {
public static void main(String[] args) {
Deque<Integer> deque = new ArrayDeque<>();
// 作为双端队列使用
deque.addFirst(1);
deque.addLast(2);
deque.addFirst(3);
// 查看头部和尾部元素
System.out.println("Peek First: " + deque.peekFirst());
System.out.println("Peek Last: " + deque.peekLast());
// 移除并打印头部和尾部元素
System.out.println("Poll First: " + deque.pollFirst());
System.out.println("Poll Last: " + deque.pollLast());
// 作为栈使用
deque.push(4);
deque.push(5);
System.out.println("Stack Pop: " + deque.pop());
System.out.println("Stack Pop: " + deque.pop());
}
}
-----------------------------------------------------------------------------------------------------
在这个示例中，我们创建了一个 ArrayDeque 实例，并分别作为双端队列和栈使用
我们向双端队列的头部和尾部添加了一些元素，并依次查看、移除并打印这些元素
然后，我们将 ArrayDeque 作为栈使用，向栈中推入一些元素，并依次弹出并打印这些元素
7.3 [1]LinkedList：链表，列表/队列/双端队列
01.常用信息1
a.定义
LinkedList 是一个基于双向链表的集合类，它实现了 List 接口和 Deque 接口，因此可以用作列表、队列和双端队列
LinkedList 是线程不安全的，需要在多线程环境中使用时进行外部同步
b.原理
LinkedList 使用双向链表作为其底层数据结构
每个节点包含一个元素和两个指向前后节点的引用
链表的头部和尾部分别由两个引用 first 和 last 指向
插入和删除操作通过调整节点的引用来实现
-----------------------------------------------------------------------------------------------------
由于链表的节点是动态分配的，
因此 LinkedList 可以高效地进行插入和删除操作，时间复杂度为 O(1)
但是，链表的随机访问性能较差，查找操作的时间复杂度为 O(n)
c.常用API
a.列表操作
boolean add(E e): 将指定的元素添加到列表的末尾
void add(int index, E element): 在列表的指定位置插入元素
E get(int index): 返回列表中指定位置的元素
E remove(int index): 移除并返回列表中指定位置的元素
boolean remove(Object o): 移除列表中首次出现的指定元素
int size(): 返回列表中的元素数量
b.队列操作
boolean offer(E e): 将指定的元素插入到队列的尾部
E poll(): 获取并移除此队列的头部元素，如果此队列为空，则返回 null
E peek(): 获取但不移除此队列的头部元素，如果此队列为空，则返回 null
c.双端队列操作
void addFirst(E e): 将指定的元素插入到队列的头部
void addLast(E e): 将指定的元素插入到队列的尾部
boolean offerFirst(E e): 将指定的元素插入到队列的头部
boolean offerLast(E e): 将指定的元素插入到队列的尾部
E pollFirst(): 获取并移除此队列的头部元素，如果此队列为空，则返回 null
E pollLast(): 获取并移除此队列的尾部元素，如果此队列为空，则返回 null
E peekFirst(): 获取但不移除此队列的头部元素，如果此队列为空，则返回 null
E peekLast(): 获取但不移除此队列的尾部元素，如果此队列为空，则返回 null
d.详情
a.线程不安全
LinkedList 是线程不安全的，如果在多线程环境中使用，需要外部同步。
b.双向链表
LinkedList 使用双向链表作为其底层数据结构，支持高效的插入和删除操作。
c.灵活性
LinkedList 实现了 List 接口和 Deque 接口，可以用作列表、队列和双端队列。
d.性能
插入和删除操作的时间复杂度为 O(1)，查找操作的时间复杂度为 O(n)。
02.常用信息2
a.应用场景
a.需要频繁插入和删除操作
在需要频繁插入和删除元素的场景中，LinkedList 提供了高效的操作
b.队列和双端队列
在需要队列或双端队列操作的场景中，LinkedList 提供了灵活的操作方式
c.列表操作
在需要列表操作的场景中，LinkedList 提供了完整的 List 接口实现
b.代码示例
import java.util.LinkedList;
import java.util.Queue;
import java.util.Deque;
public class LinkedListExample {
public static void main(String[] args) {
// 作为队列使用
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println("Queue Peek: " + queue.peek());
while (!queue.isEmpty()) {
System.out.println("Queue Poll: " + queue.poll());
}
// 作为双端队列使用
Deque<Integer> deque = new LinkedList<>();
deque.addFirst(1);
deque.addLast(2);
deque.addFirst(3);
System.out.println("Deque Peek First: " + deque.peekFirst());
System.out.println("Deque Peek Last: " + deque.peekLast());
while (!deque.isEmpty()) {
System.out.println("Deque Poll First: " + deque.pollFirst());
}
}
}
-----------------------------------------------------------------------------------------------------
在这个示例中，我们创建了一个 LinkedList 实例，并分别作为队列和双端队列使用
我们向队列和双端队列中添加了一些元素，并依次移除并打印这些元素
7.4 [1]PriorityQueue：优先级队列
01.常用信息1
a.定义
PriorityQueue 是一个基于优先级堆（通常是最小堆）的无界非阻塞队列
它是线程不安全的，元素按照自然顺序或指定的比较器顺序进行排序
PriorityQueue 实现了 Queue 接口，适用于需要优先级排序的场景
b.原理
PriorityQueue 使用堆（Heap）数据结构来实现优先级排序
默认情况下，它是一个最小堆，堆顶元素是队列中优先级最高的元素（即最小的元素）
插入和删除操作的时间复杂度为 O(log n)，查找操作的时间复杂度为 O(1)
-----------------------------------------------------------------------------------------------------
堆是一种完全二叉树，PriorityQueue 使用数组来实现堆结构
插入元素时，新元素会被添加到数组的末尾，然后通过上浮操作（heapify-up）调整堆结构
删除元素时，堆顶元素会被移除，数组末尾的元素会被移动到堆顶，然后通过下沉操作（heapify-down）调整堆结构
c.常用API
PriorityQueue(): 创建一个初始容量为 11 的空优先级队列
PriorityQueue(int initialCapacity): 创建一个具有指定初始容量的空优先级队列
PriorityQueue(int initialCapacity, Comparator<? super E> comparator): 创建一个具有指定初始容量和比较器的空优先级队列
boolean add(E e): 将指定的元素插入到队列中
boolean offer(E e): 将指定的元素插入到队列中
E poll(): 获取并移除此队列的头部元素，如果此队列为空，则返回 null
E peek(): 获取但不移除此队列的头部元素，如果此队列为空，则返回 null
boolean isEmpty(): 如果此队列不包含元素，则返回 true
int size(): 返回此队列中的元素数量
d.详情
a.线程不安全
PriorityQueue 是线程不安全的，如果在多线程环境中使用，需要外部同步
b.无界队列
PriorityQueue 是无界的，因此不会限制队列的大小
c.非阻塞
PriorityQueue 是非阻塞的，操作不会阻塞线程
d.有序性
PriorityQueue 支持元素的有序性，元素按照自然顺序或指定的比较器顺序进行排序
e.性能
插入和删除操作的时间复杂度为 O(log n)，查找操作的时间复杂度为 O(1)
02.常用信息2
a.应用场景
a.任务调度
在任务调度系统中，可以使用 PriorityQueue 来存储和调度任务，确保优先级高的任务优先执行
b.事件处理
在事件处理系统中，可以使用 PriorityQueue 来存储和处理事件，确保优先级高的事件优先处理
c.路径查找算法
在路径查找算法（如 Dijkstra 算法）中，可以使用 PriorityQueue 来存储和选择下一个要处理的节点
d.模拟系统
在模拟系统中，可以使用 PriorityQueue 来管理事件的发生顺序
b.代码示例
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
// 添加元素
queue.offer(5);
queue.offer(1);
queue.offer(3);
// 查看队列头部元素
System.out.println("Peek: " + queue.peek());
// 移除并打印元素
while (!queue.isEmpty()) {
System.out.println("Poll: " + queue.poll());
}
}
}
-----------------------------------------------------------------------------------------------------
在这个示例中，我们创建了一个 PriorityQueue 实例，并向队列中添加了一些元素
然后，我们查看队列头部的元素，并依次移除并打印队列中的元素
7.5 [1]ConcurrentLinkedQueue：并发链表队列
01.常用信息1
a.定义
ConcurrentLinkedQueue 是一个基于链表的无界非阻塞队列
它是线程安全的，使用了无锁的 CAS（Compare-And-Swap）操作来实现高效的并发访问
ConcurrentLinkedQueue 实现了 Queue 接口，适用于高并发场景下的队列操作
b.原理
ConcurrentLinkedQueue 使用了 Michael & Scott 的无锁队列算法
它通过使用 CAS 操作来确保线程安全性，而不是使用传统的锁机制
CAS 操作是一种硬件级别的原子操作，用于比较和交换变量的值，从而避免了线程之间的竞争
-----------------------------------------------------------------------------------------------------
队列中的每个节点包含一个元素和一个指向下一个节点的引用
队列的头部和尾部分别由两个原子引用 head 和 tail 指向
入队操作将新节点添加到队列的尾部，出队操作从队列的头部移除节点
c.常用API
boolean add(E e): 将指定的元素插入到队列的尾部
boolean offer(E e): 将指定的元素插入到队列的尾部
E poll(): 获取并移除此队列的头，如果此队列为空，则返回 null
E peek(): 获取但不移除此队列的头，如果此队列为空，则返回 null
boolean isEmpty(): 如果此队列不包含元素，则返回 true
int size(): 返回此队列中的元素数量
d.详情
a.线程安全
ConcurrentLinkedQueue 是线程安全的，适用于多线程环境
b.无界队列
ConcurrentLinkedQueue 是无界的，因此不会限制队列的大小
c.非阻塞
ConcurrentLinkedQueue 使用无锁的 CAS 操作来实现高效的并发访问，而不是使用传统的锁机制
d.性能
由于使用了无锁的 CAS 操作，ConcurrentLinkedQueue 在高并发场景下具有较高的性能
e.图示
ConcurrentLinkedQueue ConcurrentLinkedDeque
接口实现 Queue Deque
操作端 单端（尾部插入，头部移除） 双端（头部和尾部均可插入和移除）
用途 适用于 FIFO 队列操作 适用于 FIFO 队列和 LIFO 栈操作
灵活性 仅支持队列操作 支持队列和栈操作
线程安全性 使用无锁的 CAS 操作实现线程安全 使用无锁的 CAS 操作实现线程安全
典型应用场景 高并发环境下的队列操作 高并发环境下的双端队列或栈操作
02.常用信息2
a.应用场景
a.高并发环境
在需要高效并发访问的场景中，ConcurrentLinkedQueue 是一个很好的选择
b.生产者-消费者模型
在生产者-消费者模型中，多个生产者和消费者可以安全地并发访问队列
c.任务调度
在任务调度系统中，可以使用 ConcurrentLinkedQueue 来存储和调度任务
d.事件处理
在事件处理系统中，可以使用 ConcurrentLinkedQueue 来存储和处理事件
b.代码示例
import java.util.concurrent.ConcurrentLinkedQueue;
public class ConcurrentLinkedQueueExample {
public static void main(String[] args) {
ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<>();
// Producer
new Thread(() -> {
for (int i = 0; i < 10; i++) {
queue.offer(i);
System.out.println("Produced: " + i);
}
}).start();
// Consumer
new Thread(() -> {
for (int i = 0; i < 10; i++) {
Integer value = queue.poll();
System.out.println("Consumed: " + value);
}
}).start();
}
}
-----------------------------------------------------------------------------------------------------
在这个示例中，我们创建了一个 ConcurrentLinkedQueue 实例，
并启动了两个线程：一个生产者线程和一个消费者线程。
生产者线程将元素添加到队列中，消费者线程从队列中移除元素并打印它们
7.6 [1]ConcurrentLinkedDeque：并发链表双端队列
01.常用信息1
a.定义
ConcurrentLinkedDeque 是一个基于链表的无界非阻塞双端队列
它是线程安全的，使用了无锁的 CAS（Compare-And-Swap）操作来实现高效的并发访问
ConcurrentLinkedDeque 实现了 Deque 接口，支持在队列的两端进行插入和删除操作
b.原理
ConcurrentLinkedDeque 使用了 Michael & Scott 的无锁队列算法，
通过使用 CAS 操作来确保线程安全性，而不是使用传统的锁机制
CAS 操作是一种硬件级别的原子操作，用于比较和交换变量的值，从而避免了线程之间的竞争
-----------------------------------------------------------------------------------------------------
队列中的每个节点包含一个元素和两个指向前后节点的引用
队列的头部和尾部分别由两个原子引用 head 和 tail 指向
入队操作可以在队列的头部或尾部进行，出队操作也可以从队列的头部或尾部进行
c.常用API
void addFirst(E e): 将指定的元素插入到队列的头部
void addLast(E e): 将指定的元素插入到队列的尾部
boolean offerFirst(E e): 将指定的元素插入到队列的头部
boolean offerLast(E e): 将指定的元素插入到队列的尾部
E pollFirst(): 获取并移除此队列的头部元素，如果此队列为空，则返回 null
E pollLast(): 获取并移除此队列的尾部元素，如果此队列为空，则返回 null
E peekFirst(): 获取但不移除此队列的头部元素，如果此队列为空，则返回 null
E peekLast(): 获取但不移除此队列的尾部元素，如果此队列为空，则返回 null
boolean isEmpty(): 如果此队列不包含元素，则返回 true
int size(): 返回此队列中的元素数量
d.详情
a.线程安全
ConcurrentLinkedDeque 是线程安全的，适用于多线程环境
b.无界队列
ConcurrentLinkedDeque 是无界的，因此不会限制队列的大小
c.非阻塞
ConcurrentLinkedDeque 使用无锁的 CAS 操作来实现高效的并发访问，而不是使用传统的锁机制
d.双端操作
支持在队列的头部和尾部进行插入和删除操作，提供了更灵活的队列操作方式
e.性能
由于使用了无锁的 CAS 操作，ConcurrentLinkedDeque 在高并发场景下具有较高的性能
e.图示
ConcurrentLinkedQueue ConcurrentLinkedDeque
接口实现 Queue Deque
操作端 单端（尾部插入，头部移除） 双端（头部和尾部均可插入和移除）
用途 适用于 FIFO 队列操作 适用于 FIFO 队列和 LIFO 栈操作
灵活性 仅支持队列操作 支持队列和栈操作
线程安全性 使用无锁的 CAS 操作实现线程安全 使用无锁的 CAS 操作实现线程安全
典型应用场景 高并发环境下的队列操作 高并发环境下的双端队列或栈操作
02.常用信息2
a.应用场景
a.高并发环境
在需要高效并发访问的场景中，ConcurrentLinkedDeque 是一个很好的选择
b.生产者-消费者模型
在生产者-消费者模型中，多个生产者和消费者可以安全地并发访问队列
c.任务调度
在任务调度系统中，可以使用 ConcurrentLinkedDeque 来存储和调度任务
d.事件处理
在事件处理系统中，可以使用 ConcurrentLinkedDeque 来存储和处理事件
e.双端操作需求
在需要在队列的两端进行插入和删除操作的场景中，ConcurrentLinkedDeque 提供了灵活的操作方式
b.代码示例
import java.util.concurrent.ConcurrentLinkedDeque;
public class ConcurrentLinkedDequeExample {
public static void main(String[] args) {
ConcurrentLinkedDeque<Integer> deque = new ConcurrentLinkedDeque<>();
// Producer
new Thread(() -> {
for (int i = 0; i < 10; i++) {
deque.offerFirst(i);
System.out.println("Produced at first: " + i);
}
}).start();
// Consumer
new Thread(() -> {
for (int i = 0; i < 10; i++) {
Integer value = deque.pollLast();
System.out.println("Consumed from last: " + value);
}
}).start();
}
}
-----------------------------------------------------------------------------------------------------
在这个示例中，我们创建了一个 ConcurrentLinkedDeque 实例，
并启动了两个线程：一个生产者线程和一个消费者线程
生产者线程将元素添加到队列的头部，消费者线程从队列的尾部移除元素并打印它们
7.7 [1]ConcurrentSkipListQueue：并发跳表队列
01.常用信息1
a.定义
ConcurrentSkipListQueue 是一个基于跳表的数据结构的无界非阻塞队列
它是线程安全的，支持元素的有序性
ConcurrentSkipListQueue 实现了 Queue 接口，并且其元素按照自然顺序或指定的比较器顺序进行排序
b.原理
ConcurrentSkipListQueue 使用跳表（Skip List）作为其底层数据结构
跳表是一种分层链表，通过在链表上增加多级索引来加速查找、插入和删除操作
跳表的每一层都是一个有序链表，较高层次的链表是较低层次链表的子集
-----------------------------------------------------------------------------------------------------
ConcurrentSkipListQueue 通过使用无锁的 CAS（Compare-And-Swap）操作来实现线程安全性，而不是使用传统的锁机制
CAS 操作是一种硬件级别的原子操作，用于比较和交换变量的值，从而避免了线程之间的竞争
c.常用API
ConcurrentSkipListQueue(): 创建一个新的空队列
ConcurrentSkipListQueue(Collection<? extends E> c): 创建一个包含指定集合元素的新队列
boolean add(E e): 将指定的元素插入到队列中
boolean offer(E e): 将指定的元素插入到队列中
E poll(): 获取并移除此队列的头部元素，如果此队列为空，则返回 null
E peek(): 获取但不移除此队列的头部元素，如果此队列为空，则返回 null
boolean isEmpty(): 如果此队列不包含元素，则返回 true
int size(): 返回此队列中的元素数量
d.详情
a.线程安全
ConcurrentSkipListQueue 是线程安全的，适用于多线程环境
b.无界队列
ConcurrentSkipListQueue 是无界的，因此不会限制队列的大小
c.非阻塞
ConcurrentSkipListQueue 使用无锁的 CAS 操作来实现高效的并发访问，而不是使用传统的锁机制
d.有序性
ConcurrentSkipListQueue 支持元素的有序性，元素按照自然顺序或指定的比较器顺序进行排序
e.性能
由于使用了无锁的 CAS 操作和跳表数据结构，ConcurrentSkipListQueue 在高并发场景下具有较高的性能
02.常用信息2
a.应用场景
a.高并发环境
在需要高效并发访问的场景中，ConcurrentSkipListQueue 是一个很好的选择
b.需要有序性
在需要元素有序性的场景中，ConcurrentSkipListQueue 提供了自然顺序或指定比较器顺序的排序
c.任务调度
在任务调度系统中，可以使用 ConcurrentSkipListQueue 来存储和调度任务
d.事件处理
在事件处理系统中，可以使用 ConcurrentSkipListQueue 来存储和处理事件
e.优先级队列
在需要优先级排序的场景中，ConcurrentSkipListQueue 可以作为优先级队列使用
b.代码示例
import java.util.concurrent.ConcurrentSkipListQueue;
public class ConcurrentSkipListQueueExample {
public static void main(String[] args) {
ConcurrentSkipListQueue<Integer> queue = new ConcurrentSkipListQueue<>();
// Producer
new Thread(() -> {
for (int i = 10; i > 0; i--) {
queue.offer(i);
System.out.println("Produced: " + i);
}
}).start();
// Consumer
new Thread(() -> {
for (int i = 0; i < 10; i++) {
Integer value = queue.poll();
System.out.println("Consumed: " + value);
}
}).start();
}
}
-----------------------------------------------------------------------------------------------------
在这个示例中，我们创建了一个 ConcurrentSkipListQueue 实例
并启动了两个线程：一个生产者线程和一个消费者线程
生产者线程将元素添加到队列中，消费者线程从队列中移除元素并打印它们
7.8 [2]ArrayBlockingQueue：基于数组的阻塞队列
01.常用信息1
a.定义
ArrayBlockingQueue 是一个基于数组的有界阻塞队列
它是线程安全的，使用单一的锁机制来控制并发访问，并且可以选择使用公平锁或非公平锁
ArrayBlockingQueue 实现了 BlockingQueue 接口，适用于生产者-消费者模型中的有界队列需求
b.原理
ArrayBlockingQueue 使用一个固定大小的数组作为其底层数据结构
队列的容量在创建时指定，并且在队列的生命周期内不会改变
队列中的元素按照 FIFO（先进先出）顺序进行存储和访问
-----------------------------------------------------------------------------------------------------
ArrayBlockingQueue 使用单一的锁和两个条件变量（notEmpty 和 notFull）来控制并发访问
锁用于确保对队列的插入和删除操作是线程安全的。条件变量用于在队列为空时阻塞获取操作，以及在队列已满时阻塞插入操作
c.常用API
a.构造方法
ArrayBlockingQueue(int capacity): 创建一个具有指定容量的 ArrayBlockingQueue
ArrayBlockingQueue(int capacity, boolean fair): 创建一个具有指定容量和公平性设置的 ArrayBlockingQueue
b.插入操作
boolean add(E e): 将指定的元素插入到队列中，如果队列已满，则抛出 IllegalStateException
boolean offer(E e): 将指定的元素插入到队列中，如果队列已满，则返回 false
void put(E e): 将指定的元素插入到队列中，如果队列已满，则等待空间变得可用
c.移除操作
E poll(): 获取并移除此队列的头部元素，如果此队列为空，则返回 null
E take(): 获取并移除此队列的头部元素，如果此队列为空，则等待元素变得可用
E peek(): 获取但不移除此队列的头部元素，如果此队列为空，则返回 null
d.其他操作
boolean isEmpty(): 如果此队列不包含元素，则返回 true
int size(): 返回此队列中的元素数量
int remainingCapacity(): 返回此队列中剩余的可用空间
d.详情
a.线程安全
ArrayBlockingQueue 是线程安全的，适用于多线程环境
b.有界队列
ArrayBlockingQueue 是有界的，容量在创建时指定，并且在队列的生命周期内不会改变
c.阻塞操作
ArrayBlockingQueue 提供了阻塞的插入和移除操作，适用于生产者-消费者模型
d.公平性
可以选择使用公平锁或非公平锁。公平锁确保线程按照请求的顺序访问队列，而非公平锁可能会导致线程饥饿
02.常用信息2
a.应用场景
a.生产者-消费者模型
在生产者-消费者模型中，多个生产者和消费者可以安全地并发访问队列
b.有界队列需求
在需要限制队列容量的场景中，ArrayBlockingQueue 提供了有界队列的实现
c.多线程环境
在多线程环境中，需要线程安全的队列来协调线程之间的工作
b.代码示例
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
public class ArrayBlockingQueueExample {
public static void main(String[] args) throws InterruptedException {
BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(10);
// Producer
new Thread(() -> {
try {
for (int i = 0; i < 10; i++) {
queue.put(i);
System.out.println("Produced: " + i);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}).start();
// Consumer
new Thread(() -> {
try {
for (int i = 0; i < 10; i++) {
Integer value = queue.take();
System.out.println("Consumed: " + value);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}).start();
}
}
-----------------------------------------------------------------------------------------------------
在这个示例中，我们创建了一个 ArrayBlockingQueue 实例
并启动了两个线程：一个生产者线程和一个消费者线程
生产者线程将元素添加到队列中，消费者线程从队列中移除元素并打印它们
7.9 [2]LinkedBlockingQueue：基于链表的阻塞队列
01.常用信息1
a.定义
LinkedBlockingQueue 是一个基于链表的阻塞队列
它是线程安全的，使用两个独立的锁来控制并发访问，分别用于入队和出队操作
LinkedBlockingQueue 实现了 BlockingQueue 接口，可以是有界的或无界的
适用于生产者-消费者模型中的高并发场景
b.原理
LinkedBlockingQueue 使用链表作为其底层数据结构
队列中的每个节点包含一个元素和一个指向下一个节点的引用
队列的头部和尾部分别由两个引用 head 和 last 指向
入队操作将新节点添加到队列的尾部，出队操作从队列的头部移除节点
-----------------------------------------------------------------------------------------------------
LinkedBlockingQueue 使用两个独立的锁和两个条件变量（notEmpty 和 notFull）来控制并发访问
一个锁用于入队操作，另一个锁用于出队操作，从而允许入队和出队操作并行进行，提高了并发性能
c.常用API
a.构造方法
LinkedBlockingQueue(): 创建一个容量为 Integer.MAX_VALUE 的无界队列
LinkedBlockingQueue(int capacity): 创建一个具有指定容量的有界队列
b.插入操作
boolean add(E e): 将指定的元素插入到队列中，如果队列已满，则抛出 IllegalStateException
boolean offer(E e): 将指定的元素插入到队列中，如果队列已满，则返回 false
void put(E e): 将指定的元素插入到队列中，如果队列已满，则等待空间变得可用
c.移除操作
E poll(): 获取并移除此队列的头部元素，如果此队列为空，则返回 null
E take(): 获取并移除此队列的头部元素，如果此队列为空，则等待元素变得可用
E peek(): 获取但不移除此队列的头部元素，如果此队列为空，则返回 null
d.其他操作
boolean isEmpty(): 如果此队列不包含元素，则返回 true
int size(): 返回此队列中的元素数量
int remainingCapacity(): 返回此队列中剩余的可用空间
d.详情
a.线程安全
LinkedBlockingQueue 是线程安全的，适用于多线程环境
b.有界或无界
LinkedBlockingQueue 可以是有界的或无界的，容量在创建时指定
c.阻塞操作
LinkedBlockingQueue 提供了阻塞的插入和移除操作，适用于生产者-消费者模型
d.高并发性能
使用两个独立的锁来控制入队和出队操作，允许并行进行，提高了并发性能
02.常用信息2
a.应用场景
a.生产者-消费者模型
在生产者-消费者模型中，多个生产者和消费者可以安全地并发访问队列
b.高并发环境
在需要高效并发访问的场景中，LinkedBlockingQueue 是一个很好的选择
c.有界队列需求
在需要限制队列容量的场景中，LinkedBlockingQueue 提供了有界队列的实现
b.代码示例
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.BlockingQueue;
public class LinkedBlockingQueueExample {
public static void main(String[] args) throws InterruptedException {
BlockingQueue<Integer> queue = new LinkedBlockingQueue<>(10);
// Producer
new Thread(() -> {
try {
for (int i = 0; i < 10; i++) {
queue.put(i);
System.out.println("Produced: " + i);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}).start();
// Consumer
new Thread(() -> {
try {
for (int i = 0; i < 10; i++) {
Integer value = queue.take();
System.out.println("Consumed: " + value);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}).start();
}
}
-----------------------------------------------------------------------------------------------------
在这个示例中，我们创建了一个 LinkedBlockingQueue 实例
并启动了两个线程：一个生产者线程和一个消费者线程
生产者线程将元素添加到队列中，消费者线程从队列中移除元素并打印它们
7.10 [2]LinkedBlockingDeque：基于链表的阻塞双端队列
01.常用信息1
a.定义
LinkedBlockingDeque 是一个基于链表的阻塞双端队列
它是线程安全的，支持在队列的两端进行插入和删除操作
LinkedBlockingDeque 实现了 BlockingDeque 接口，可以是有界的或无界的，适用于生产者-消费者模型中的高并发场景
b.原理
LinkedBlockingDeque 使用链表作为其底层数据结构
队列中的每个节点包含一个元素和两个指向前后节点的引用
队列的头部和尾部分别由两个引用 first 和 last 指向
入队操作可以在队列的头部或尾部进行，出队操作也可以从队列的头部或尾部进行
-----------------------------------------------------------------------------------------------------
LinkedBlockingDeque 使用两个独立的锁和两个条件变量（notEmpty 和 notFull）来控制并发访问
一个锁用于头部操作，另一个锁用于尾部操作，从而允许头部和尾部操作并行进行，提高了并发性能
c.常用API
a.构造方法
LinkedBlockingDeque(): 创建一个容量为 Integer.MAX_VALUE 的无界双端队列
LinkedBlockingDeque(int capacity): 创建一个具有指定容量的有界双端队列
b.插入操作
void addFirst(E e): 将指定的元素插入到队列的头部
void addLast(E e): 将指定的元素插入到队列的尾部
boolean offerFirst(E e): 将指定的元素插入到队列的头部
boolean offerLast(E e): 将指定的元素插入到队列的尾部
void putFirst(E e): 将指定的元素插入到队列的头部，如果队列已满，则等待空间变得可用
void putLast(E e): 将指定的元素插入到队列的尾部，如果队列已满，则等待空间变得可用
c.移除操作
E pollFirst(): 获取并移除此队列的头部元素，如果此队列为空，则返回 null
E pollLast(): 获取并移除此队列的尾部元素，如果此队列为空，则返回 null
E takeFirst(): 获取并移除此队列的头部元素，如果此队列为空，则等待元素变得可用
E takeLast(): 获取并移除此队列的尾部元素，如果此队列为空，则等待元素变得可用
d.其他操作
boolean isEmpty(): 如果此队列不包含元素，则返回 true
int size(): 返回此队列中的元素数量
int remainingCapacity(): 返回此队列中剩余的可用空间
d.详情
a.线程安全
LinkedBlockingDeque 是线程安全的，适用于多线程环境
b.有界或无界
LinkedBlockingDeque 可以是有界的或无界的，容量在创建时指定
c.阻塞操作
LinkedBlockingDeque 提供了阻塞的插入和移除操作，适用于生产者-消费者模型
d.双端操作
支持在队列的头部和尾部进行插入和删除操作，提供了更灵活的队列操作方式
e.高并发性能
使用两个独立的锁来控制头部和尾部操作，允许并行进行，提高了并发性能
02.常用信息2
a.应用场景
a.生产者-消费者模型
在生产者-消费者模型中，多个生产者和消费者可以安全地并发访问队列
b.高并发环境
在需要高效并发访问的场景中，LinkedBlockingDeque 是一个很好的选择
c.双端队列需求
在需要在队列的两端进行插入和删除操作的场景中，LinkedBlockingDeque 提供了灵活的操作方式
d.任务调度
在任务调度系统中，可以使用 LinkedBlockingDeque 来存储和调度任务
b.代码示例
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.BlockingDeque;
public class LinkedBlockingDequeExample {
public static void main(String[] args) throws InterruptedException {
BlockingDeque<Integer> deque = new LinkedBlockingDeque<>(10);
// Producer
new Thread(() -> {
try {
for (int i = 0; i < 10; i++) {
deque.putFirst(i);
System.out.println("Produced at first: " + i);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}).start();
// Consumer
new Thread(() -> {
try {
for (int i = 0; i < 10; i++) {
Integer value = deque.takeLast();
System.out.println("Consumed from last: " + value);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}).start();
}
}
-----------------------------------------------------------------------------------------------------
在这个示例中，我们创建了一个 LinkedBlockingDeque 实例，并启动了两个线程
一个生产者线程和一个消费者线程
生产者线程将元素添加到队列的头部，消费者线程从队列的尾部移除元素并打印它们
7.11 [2]LinkedTransferQueue：链表传输队列
01.常用信息1
a.定义
LinkedTransferQueue 是一个基于链表的无界阻塞队列
它是线程安全的，支持生产者等待消费者接收元素的操作
LinkedTransferQueue 实现了 TransferQueue 接口，适用于高并发场景中的任务传递和工作队列
b.原理
LinkedTransferQueue 使用链表作为其底层数据结构
队列中的每个节点包含一个元素和一个指向下一个节点的引用
队列的头部和尾部分别由两个引用 head 和 tail 指向
入队操作将新节点添加到队列的尾部，出队操作从队列的头部移除节点
-----------------------------------------------------------------------------------------------------
LinkedTransferQueue 提供了 transfer 方法，允许生产者等待消费者接收元素
它使用无锁的 CAS（Compare-And-Swap）操作来实现高效的并发访问，而不是使用传统的锁机制
CAS 操作是一种硬件级别的原子操作，用于比较和交换变量的值，从而避免了线程之间的竞争
c.常用API
a.构造方法
LinkedTransferQueue(): 创建一个空的 LinkedTransferQueue
LinkedTransferQueue(Collection<? extends E> c): 创建一个包含指定集合元素的 LinkedTransferQueue
b.插入操作
boolean add(E e): 将指定的元素插入到队列中
boolean offer(E e): 将指定的元素插入到队列中
void put(E e): 将指定的元素插入到队列中
boolean offer(E e, long timeout, TimeUnit unit): 将指定的元素插入到队列中，如果在指定的时间内没有可用空间，则返回 false
void transfer(E e): 将指定的元素插入到队列中，并等待消费者接收该元素
c.移除操作
E poll(): 获取并移除此队列的头部元素，如果此队列为空，则返回 null
E take(): 获取并移除此队列的头部元素，如果此队列为空，则等待元素变得可用
E poll(long timeout, TimeUnit unit): 获取并移除此队列的头部元素，如果在指定的时间内没有可用元素，则返回 null
E peek(): 获取但不移除此队列的头部元素，如果此队列为空，则返回 null
d.其他操作
boolean tryTransfer(E e): 尝试将指定的元素插入到队列中，如果没有等待的消费者，则返回 false
boolean tryTransfer(E e, long timeout, TimeUnit unit): 尝试将指定的元素插入到队列中，并等待指定的时间，如果没有等待的消费者，则返回 false
boolean hasWaitingConsumer(): 如果有等待的消费者，则返回 true
int getWaitingConsumerCount(): 返回等待消费者的数量
boolean isEmpty(): 如果此队列不包含元素，则返回 true
int size(): 返回此队列中的元素数量
d.详情
a.线程安全
LinkedTransferQueue 是线程安全的，适用于多线程环境
b.无界队列
LinkedTransferQueue 是无界的，因此不会限制队列的大小
c.阻塞操作
LinkedTransferQueue 提供了阻塞的插入和移除操作，适用于生产者-消费者模型
d.传输操作
LinkedTransferQueue 支持生产者等待消费者接收元素的操作，提供了灵活的任务传递机制
e.高并发性能
使用无锁的 CAS 操作来实现高效的并发访问，提高了并发性能
02.常用信息2
a.应用场景
a.高并发环境
在需要高效并发访问的场景中，LinkedTransferQueue 是一个很好的选择
b.任务传递
在任务传递系统中，可以使用 LinkedTransferQueue 来传递任务，确保任务在生产者和消费者之间直接传递
c.生产者-消费者模型
在生产者-消费者模型中，多个生产者和消费者可以安全地并发访问队列
d.工作队列
在工作队列系统中，可以使用 LinkedTransferQueue 来管理和调度任务
b.代码示例
import java.util.concurrent.LinkedTransferQueue;
import java.util.concurrent.TransferQueue;
public class LinkedTransferQueueExample {
public static void main(String[] args) throws InterruptedException {
TransferQueue<Integer> queue = new LinkedTransferQueue<>();
// Producer
new Thread(() -> {
try {
for (int i = 0; i < 10; i++) {
queue.transfer(i);
System.out.println("Produced: " + i);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}).start();
// Consumer
new Thread(() -> {
try {
for (int i = 0; i < 10; i++) {
Integer value = queue.take();
System.out.println("Consumed: " + value);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}).start();
}
}
-----------------------------------------------------------------------------------------------------
在这个示例中，我们创建了一个 LinkedTransferQueue 实例，并启动了两个线程
一个生产者线程和一个消费者线程。生产者线程使用 transfer 方法将元素添加到队列中，并等待消费者接收这些元素
消费者线程从队列中移除元素并打印它们
7.12 [2]PriorityBlockingQueue：优先级阻塞队列
01.常用信息1
a.定义
PriorityBlockingQueue 是一个支持优先级排序的无界阻塞队列
它是线程安全的，使用优先级堆（通常是最小堆）作为其底层数据结构
PriorityBlockingQueue 实现了 BlockingQueue 接口，适用于需要优先级排序的场景
b.原理
PriorityBlockingQueue 使用堆（Heap）数据结构来实现优先级排序
默认情况下，它是一个最小堆，堆顶元素是队列中优先级最高的元素（即最小的元素）
插入和删除操作的时间复杂度为 O(log n)，查找操作的时间复杂度为 O(1)
-----------------------------------------------------------------------------------------------------
PriorityBlockingQueue 是无界的，因此不会限制队列的大小
它使用锁和条件变量来控制并发访问，确保线程安全性
插入操作会将新元素添加到堆中，并通过上浮操作（heapify-up）调整堆结构
删除操作会移除堆顶元素，并通过下沉操作（heapify-down）调整堆结构
c.常用API
a.构造方法
PriorityBlockingQueue(): 创建一个初始容量为 11 的空优先级队列
PriorityBlockingQueue(int initialCapacity): 创建一个具有指定初始容量的空优先级队列
PriorityBlockingQueue(int initialCapacity, Comparator<? super E> comparator): 创建一个具有指定初始容量和比较器的空优先级队列
b.插入操作
boolean add(E e): 将指定的元素插入到队列中
boolean offer(E e): 将指定的元素插入到队列中
void put(E e): 将指定的元素插入到队列中
c.移除操作
E poll(): 获取并移除此队列的头部元素，如果此队列为空，则返回 null
E take(): 获取并移除此队列的头部元素，如果此队列为空，则等待元素变得可用
E peek(): 获取但不移除此队列的头部元素，如果此队列为空，则返回 null
d.其他操作
boolean isEmpty(): 如果此队列不包含元素，则返回 true
int size(): 返回此队列中的元素数量
int remainingCapacity(): 返回此队列中剩余的可用空间（对于无界队列，返回 Integer.MAX_VALUE）
d.详情
a.线程安全
PriorityBlockingQueue 是线程安全的，适用于多线程环境
b.无界队列
PriorityBlockingQueue 是无界的，因此不会限制队列的大小
c.阻塞操作
PriorityBlockingQueue 提供了阻塞的插入和移除操作，适用于生产者-消费者模型
d.优先级排序
PriorityBlockingQueue 支持元素的优先级排序，元素按照自然顺序或指定的比较器顺序进行排序
e.性能
插入和删除操作的时间复杂度为 O(log n)，查找操作的时间复杂度为 O(1)
02.常用信息2
a.应用场景
a.任务调度
在任务调度系统中，可以使用 PriorityBlockingQueue 来存储和调度任务，确保优先级高的任务优先执行
b.事件处理
在事件处理系统中，可以使用 PriorityBlockingQueue 来存储和处理事件，确保优先级高的事件优先处理
c.路径查找算法
在路径查找算法（如 Dijkstra 算法）中，可以使用 PriorityBlockingQueue 来存储和选择下一个要处理的节点
d.模拟系统
在模拟系统中，可以使用 PriorityBlockingQueue 来管理事件的发生顺序
b.代码示例
import java.util.concurrent.PriorityBlockingQueue;
import java.util.concurrent.BlockingQueue;
public class PriorityBlockingQueueExample {
public static void main(String[] args) throws InterruptedException {
BlockingQueue<Integer> queue = new PriorityBlockingQueue<>();
// Producer
new Thread(() -> {
try {
for (int i = 10; i > 0; i--) {
queue.put(i);
System.out.println("Produced: " + i);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}).start();
// Consumer
new Thread(() -> {
try {
for (int i = 0; i < 10; i++) {
Integer value = queue.take();
System.out.println("Consumed: " + value);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}).start();
}
}
-----------------------------------------------------------------------------------------------------
在这个示例中，我们创建了一个 PriorityBlockingQueue 实例
并启动了两个线程：一个生产者线程和一个消费者线程
生产者线程将元素添加到队列中，消费者线程从队列中移除元素并打印它们
7.13 [2]SynchronousQueue：同步队列
01.常用信息1
a.定义
SynchronousQueue 是一个容量为零的阻塞队列
它是线程安全的，每次插入操作必须等待对应的移除操作，反之亦然
SynchronousQueue 实现了 BlockingQueue 接口，适用于需要严格同步的场景
b.原理
a.介绍
SynchronousQueue 不存储任何元素
每个插入操作必须等待一个对应的移除操作，反之亦然
它可以看作是一个传递元素的通道，而不是一个真正的队列
SynchronousQueue 提供了两种模式：公平模式和非公平模式
b.公平模式
使用公平锁，确保线程按照请求的顺序访问队列
c.非公平模式
使用非公平锁，可能会导致线程饥饿，但通常具有更高的吞吐量
SynchronousQueue 使用内部的两个独立队列来管理插入和移除操作的线程
插入操作将线程放入插入队列中，等待对应的移除操作
移除操作将线程放入移除队列中，等待对应的插入操作
c.常用API
a.构造方法
SynchronousQueue(): 创建一个非公平的 SynchronousQueue
SynchronousQueue(boolean fair): 创建一个指定公平性的 SynchronousQueue
b.插入操作
boolean add(E e): 将指定的元素插入到队列中，如果没有等待的移除操作，则抛出 IllegalStateException
boolean offer(E e): 将指定的元素插入到队列中，如果没有等待的移除操作，则返回 false
void put(E e): 将指定的元素插入到队列中，如果没有等待的移除操作，则等待
c.移除操作
E poll(): 获取并移除此队列的头部元素，如果没有等待的插入操作，则返回 null
E take(): 获取并移除此队列的头部元素，如果没有等待的插入操作，则等待
E peek(): SynchronousQueue 不支持此操作，调用此方法将始终返回 null
d.其他操作
boolean isEmpty(): SynchronousQueue 始终为空，因此此方法始终返回 true
int size(): SynchronousQueue 始终为空，因此此方法始终返回 0
int remainingCapacity(): SynchronousQueue 没有容量，因此此方法始终返回 0
d.详情
a.线程安全
SynchronousQueue 是线程安全的，适用于多线程环境
b.容量为零
SynchronousQueue 没有容量，每次插入操作必须等待对应的移除操作，反之亦然
c.阻塞操作
SynchronousQueue 提供了阻塞的插入和移除操作，适用于需要严格同步的场景
d.公平性
可以选择使用公平锁或非公平锁。公平锁确保线程按照请求的顺序访问队列，而非公平锁可能会导致线程饥饿，但通常具有更高的吞吐量
02.常用信息2
a.应用场景
a.严格同步
在需要严格同步的场景中，SynchronousQueue 提供了高效的同步机制
b.任务传递
在任务传递系统中，可以使用 SynchronousQueue 来传递任务，确保任务在生产者和消费者之间直接传递
c.线程池
在线程池实现中，SynchronousQueue 可以用作工作队列，确保任务在工作线程之间直接传递
b.代码示例
import java.util.concurrent.SynchronousQueue;
import java.util.concurrent.BlockingQueue;
public class SynchronousQueueExample {
public static void main(String[] args) throws InterruptedException {
BlockingQueue<Integer> queue = new SynchronousQueue<>();
// Producer
new Thread(() -> {
try {
for (int i = 0; i < 10; i++) {
queue.put(i);
System.out.println("Produced: " + i);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}).start();
// Consumer
new Thread(() -> {
try {
for (int i = 0; i < 10; i++) {
Integer value = queue.take();
System.out.println("Consumed: " + value);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}).start();
}
}
-----------------------------------------------------------------------------------------------------
在这个示例中，我们创建了一个 SynchronousQueue 实例，并启动了两个线程
一个生产者线程和一个消费者线程。生产者线程将元素添加到队列中
消费者线程从队列中移除元素并打印它们。由于 SynchronousQueue 的容量为零
每次插入操作必须等待对应的移除操作，反之亦然
7.14 [2]DelayQueue：延迟队列
01.常用信息1
a.定义
DelayQueue 是一个支持延迟获取元素的无界阻塞队列
它是线程安全的，使用优先级堆（通常是最小堆）作为其底层数据结构
DelayQueue 实现了 BlockingQueue 接口，适用于需要延迟处理任务的场景
b.原理
DelayQueue 使用堆（Heap）数据结构来实现延迟获取元素
队列中的元素必须实现 Delayed 接口，该接口要求实现 getDelay(TimeUnit unit) 方法，用于指定元素的延迟时间
元素按照延迟时间的顺序进行排序，延迟时间最短的元素位于堆顶
-----------------------------------------------------------------------------------------------------
DelayQueue 是无界的，因此不会限制队列的大小
它使用锁和条件变量来控制并发访问，确保线程安全性
插入操作会将新元素添加到堆中，并通过上浮操作（heapify-up）调整堆结构
删除操作会移除堆顶元素，并通过下沉操作（heapify-down）调整堆结构
c.常用API
a.构造方法
DelayQueue(): 创建一个空的 DelayQueue
DelayQueue(Collection<? extends E> c): 创建一个包含指定集合元素的 DelayQueue
b.插入操作
boolean add(E e): 将指定的元素插入到队列中
boolean offer(E e): 将指定的元素插入到队列中
void put(E e): 将指定的元素插入到队列中
c.移除操作
E poll(): 获取并移除此队列的头部元素，如果此队列为空，则返回 null
E take(): 获取并移除此队列的头部元素，如果此队列为空，则等待元素变得可用
E peek(): 获取但不移除此队列的头部元素，如果此队列为空，则返回 null
d.其他操作
boolean isEmpty(): 如果此队列不包含元素，则返回 true
int size(): 返回此队列中的元素数量
int remainingCapacity(): 返回此队列中剩余的可用空间（对于无界队列，返回 Integer.MAX_VALUE）
d.详情
a.线程安全
DelayQueue 是线程安全的，适用于多线程环境
b.无界队列
DelayQueue 是无界的，因此不会限制队列的大小
c.阻塞操作
DelayQueue 提供了阻塞的插入和移除操作，适用于生产者-消费者模型
d.延迟处理
DelayQueue 支持元素的延迟处理，元素只有在其延迟期满时才能被取出
e.性能
插入和删除操作的时间复杂度为 O(log n)，查找操作的时间复杂度为 O(1)
02.常用信息2
a.应用场景
a.任务调度
在任务调度系统中，可以使用 DelayQueue 来存储和调度任务，确保任务在指定的延迟时间后执行
b.延迟处理
在需要延迟处理任务的场景中，DelayQueue 提供了灵活的延迟处理机制
c.缓存过期
在缓存系统中，可以使用 DelayQueue 来管理缓存项的过期时间，确保缓存项在过期后自动移除
d.定时任务
在定时任务系统中，可以使用 DelayQueue 来管理和执行定时任务
n.代码示例
import java.util.concurrent.DelayQueue;
import java.util.concurrent.Delayed;
import java.util.concurrent.TimeUnit;
public class DelayQueueExample {
public static void main(String[] args) throws InterruptedException {
DelayQueue<DelayedElement> queue = new DelayQueue<>();
// Producer
new Thread(() -> {
try {
queue.put(new DelayedElement("Task1", 5000));
System.out.println("Produced: Task1");
queue.put(new DelayedElement("Task2", 10000));
System.out.println("Produced: Task2");
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}).start();
// Consumer
new Thread(() -> {
try {
while (true) {
DelayedElement element = queue.take();
System.out.println("Consumed: " + element.getName());
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}).start();
}
static class DelayedElement implements Delayed {
private final String name;
private final long startTime;
public DelayedElement(String name, long delay) {
this.name = name;
this.startTime = System.currentTimeMillis() + delay;
}
public String getName() {
return name;
}
@Override
public long getDelay(TimeUnit unit) {
long diff = startTime - System.currentTimeMillis();
return unit.convert(diff, TimeUnit.MILLISECONDS);
}
@Override
public int compareTo(Delayed o) {
if (this.startTime < ((DelayedElement) o).startTime) {
return -1;
}
if (this.startTime > ((DelayedElement) o).startTime) {
return 1;
}
return 0;
}
}
}
-----------------------------------------------------------------------------------------------------
在这个示例中，我们创建了一个 DelayQueue 实例
并启动了两个线程：一个生产者线程和一个消费者线程
生产者线程将带有延迟时间的任务添加到队列中，消费者线程从队列中移除并处理这些任务