朱继鹏的博客

天道酬勤，全栈不停

0%

container

发表于 更新于 分类于
java容器篇

Container

Type

不推荐的类：Vector、Stack、Hashtable

普通容器类（线程不安全）

  • Array：T[]
  • List
    • ArrayList：基于数组实现
    • LinkedList：基于链表实现
  • Set
    • HashSet：最常用的Set
    • LinkedHashSet：支持按照插入顺序（默认）或者访问顺序迭代
    • SortedSet
      • NavigableSet
        • TreeSet：支持排序
  • Map
    • HashMap：最常用的Map
    • LinkedHashMap：支持按照插入顺序（默认）或者访问顺序迭代
    • SortedMap
      • NavigableMap
        • TreeMap：支持排序，基于堆实现
  • Queue
    • Deque
      • ArrayDeque：基于数组实现
      • LinkedList：基于链表实现
    • PriorityQueue：支持优先级
  • Stack：LinkedList

Set是基于Map实现的

同步容器类（线程安全）

  • List：Vector
  • Map：Hashtable
  • Stack：Stack

Collections.synchronizedXXX的优势是可以包装任何类型的容器并返回安全的容器
Collections.synchronizedXXX包装类返回的迭代器没有保证安全，需要使用者自己保证

并发容器类（线程安全）

  • List
    • CopyOnWriteArrayList：写时复制
  • Set
    • CopyOnWriteArraySet：写时复制
    • SortedSet
      • NavigableSet
        • ConcurrentSkipListSet：安全版TreeSet
  • Map
    • ConcurrentHashMap：Segment + Lock （java7）、CAS + synchronized（java8）
    • SortedMap
      • NavigableMap
        • ConcurrentSkipListMap：安全版TreeMap
  • Queue：
    • BlockingQueue：
      • ArrayBlockingQueue：有界
      • LinkedBlockingQueue：默认无界，但边界可配
      • SynchronousQueue：有界，容量为0，不存储元素直接交付（handoff）的阻塞队列
      • TransferQueue
        • LinkedTransferQueue：无界，支持Transfer操作
      • PriorityBlockingQueue：无界，支持优先级
      • DelayQueue：无界，支持延时，是延时消息队列
      • DelayedWorkQueue：无界，支持延时，是延时任务队列
    • BlockingDeque：
      • LinkedBlockingDeque：默认无界，但边界可配
    • ConcurrentLinkedQueue：无界
    • ConcurrentLinkedDeque：无界

Ops

  • List
    • 排序：List.sort Collections.sort Stream.sorted
    • 去重：Set Stream.distinct
    • 分页：List.subList 工具包的partition操作
  • Set
    • 排序：TreeSet Stream.sorted
    • 去重：天生自带去重属性
    • 分页：需转list后分页
  • Map
    • 排序：TreeMap
    • 去重：天生自带去重属性
    • 分页：需转list后分页

ps：LinkedHashSet和LinkedHashMap可以按照 插入时间 或者 访问时间 排序

有序容器常见操作

基础操作

  • 添加：add（tail）
  • 移除：remove（head）
  • 插入：insert（with pos）
  • 删除：delete（with pos）
  • 设值：set（with pos）
  • 取值：get（with pos）
  • 查询：contains
  • 查找：indexOf、lastlndexOf
  • 大小：size
  • 判空：isEmpty
  • 判满：isFull

进阶操作

  • 拼接：concat（addAll）
  • 截取：slice、range（subList）
  • 分区：partition
  • 合并：merge
  • 遍历：iterate
  • 排序：sort
  • 去重：distinct
  • 分页：pagination

高级操作

  • 并集：union（addAll）
  • 交集：intersection（retainAll）
  • 差集：difference（removeAll）

无序容器常见操作

基础操作

  • 添加：add
  • 移除：remove
  • 查询：contains
  • 大小：size
  • 判空：isEmpty
  • 判满：isFull

进阶操作

  • 拼接：concat（addAll）
  • 遍历：iterate
  • 排序：sort

高级操作

  • 并集：union（addAll）
  • 交集：intersection（retainAll）
  • 差集：difference（removeAll）

键值容器常见操作

基础操作

  • 设值：set（with key）（put）
  • 取值：get（with key）（get）
  • 查询：contains
  • 大小：size
  • 判空：isEmpty
  • 判满：isFull

进阶操作

  • 拼接：concat（putAll）
  • 遍历：iterate
  • 排序：sort

高级操作

  • 不存在时设值：setIfAbsent（putIfAbsent）
  • 存在时设值：setIfPresent（putIfPresent）

Array

Basic

List

Basic

Question

Array和ArrayList的区别

  • Array的占用空间是固定的，ArrayList的占用空间是动态的
  • Array支持原始类型，ArrayList只支持对象类型
  • Array的元素可以直接使用子类，ArrayList的元素需要使用类型通配符才能使用子类
  • Array获取大小是通过length属性，ArrayList获取大小是通过size方法
  • Array没有删除元素的方法，ArrayList有删除元素的方法

ArrayList和LinkedList的区别

  • 结构：
    • ArrayList是基于数组实现的
    • LinkedList是基于链表实现的
  • 性能：
    • ArrayList读取时使用索引直接定位，所以读取（随机访问）较快，写入时需要移动元素，所以写入（插入和删除）较慢
    • LinkedList读取时需从头开始遍历，所以读取（随机访问）较慢，写入时不需要移动元素，所以写入（插入和删除）较快
  • 空间：
    • LinkedList使用Node结构还需要存储前指针和后指针，比ArrayList更占内存

ArrayList和Vector的区别

Collections.synchronizedList和Vector的区别

CopyOnWriteArrayList和Vector的区别

CopyOnWriteArrayList和Collections.synchronizedList的区别

  • 结构：
    • CopyOnWriteArrayList是基于写时拷贝技术保证安全的
    • Collections.synchronizedList返回的包装类是基于synchronized锁机制保证安全的
  • 性能：
    • CopyOnWriteArrayList适合读多写少的安全场景
    • Collections.synchronizedList适合常规读写的安全场景
  • 空间：
    • CopyOnWriteArrayList修改时需要拷贝一份数据，比Collections.synchronizedList更占内存

为什么ArrayList实现了RandomAccess接口而LinkedList却没有

Set

Basic

Map

Basic

Question

HashMap和ConcurrentHashMap的区别

HashMap和Hashtable的区别

Collections.synchronizedMap和Hashtable的区别

ConcurrentHashMap和Hashtable的区别

ConcurrentHashMap和Collections.synchronizedMap的区别

Queue

Basic

Disruptor是高效的无锁并发内存队列，可用来替代BlockingQueue

Question

Queue方法的区别

按照操作分

  • add/offer/put：添加尾部元素
  • remove/poll/take：移除头部元素
  • element/peek：查询头部元素

按照结果分

  • add/remove/element：操作元素失败的时候抛出异常
  • offer/poll/peek：操作元素失败的时候会返回值
  • put/take：操作元素失败的时候会阻塞

ps：put/take是BlockingQueue接口特有的阻塞方法，Queue接口里没有

双端队列的使用场景

  • 模拟栈
  • 实现消息消费失败时回退的功能

ArrayDeque和LinkedList的区别

  • 结构：
    • ArrayDeque是基于数组实现的
    • LinkedList是基于链表实现的
  • 性能：
    • ArrayDeque读取时使用索引直接定位，所以读取（随机访问）较快，写入时需要移动元素，所以写入（插入和删除）较慢
    • LinkedList读取时需从头开始遍历，所以读取（随机访问）较慢，写入时不需要移动元素，所以写入（插入和删除）较快
  • 空间：
    • LinkedList使用Node结构还需要存储前指针和后指针，比ArrayDeque更占内存

ArrayBlockingQueue和LinkedBlockingQueue的区别

  • 结构：
    • ArrayBlockingQueue是基于循环数组实现的，LinkedBlockingQueue基于链表实现的
    • ArrayBlockingQueue必须设置边界，LinkedBlockingQueue默认无界，但边界可配
  • 性能：
    • ArrayBlockingQueue出队和入队使用同一把锁，LinkedBlockingQueue出队和入队使用不同的锁，因此LinkedBlockingQueue的并发支持更高
  • 空间：
    • ArrayBlockingQueue因为使用循环数组会分配固定的内存，LinkedBlockingQueue按需使用内存，因此ArrayBlockingQueue在滞留元素较少时容易浪费空间
    • LinkedBlockingQueue使用Node结构还需要存储指针，比ArrayBlockingQueue更占内存
    • LinkedBlockingQueue会频繁的创建和销毁额外的Node对象，对GC存在较大影响

LinkedBlockingQueue和ConcurrentLinkedQueue的区别

  • LinkedBlockingQueue是阻塞队列
  • ConcurrentLinkedQueue是非阻塞队列

SynchronousQueue和TransferQueue的区别

  • SynchronousQueue并发控制时使用的是锁，性能相对较低（会被阻塞）
  • TransferQueue并发控制时使用的是CAS，性能相对较高（不会阻塞）

PriorityBlockingQueue和DelayQueue的区别

  • PriorityBlockingQueue：队列不为空时取元素时可以立即获取
  • DelayQueue：队列不为空时获取元素需要等待延时到达后才可以获取

ps：PriorityBlockingQueue和DelayQueue都是基于PriorityQueue实现的，都会在队列为空或者为满时支持阻塞

DelayQueue和DelayedWorkQueue的区别

  • DelayQueue是通用的延时消息队列（基于PriorityQueue实现的），支持的元素的类型是 Delayed
  • DelayedWorkQueue是专用的延时任务队列（是ScheduledThreadPoolExecutor的内部类），支持的元素类型是 RunnableScheduledFuture

Stack

Basic

More

Range

Table

Traverse

Traverse：遍历

Basic

遍历方式主要分为两种

  • for遍历
  • iterator遍历

For

  • fori：按下标遍历元素
    • Array：支持（有下标）
    • List：支持（有下标）
    • Set：不支持（无下标），需转list
    • Map：不支持（无下标），需转list（Map.values、Map.entrySet、Map.keySet）
  • for in：按键值遍历元素
    • Array：不支持（无键值）
    • List：不支持（无键值）
    • Set：不支持（无键值）
    • Map：支持（有键值）（Map.entrySet、Map.keySet）
  • forEach（for of）：直接遍历元素
    • Array：支持
    • List：支持
    • Set：支持
    • Map：支持（Map.values、Map.entrySet）
  • forEach（Container）：直接遍历元素
    • Array：不支持，需转list
    • List：支持（List.forEach）
    • Set：支持（Set.forEach）
    • Map：支持（Map.forEach）
  • forEach（Stream）：直接遍历元素
    • Array：支持（Arrays. Stream.forEach）
    • List：支持（List. Stream.forEach）
    • Set：支持（Set. Stream.forEach）
    • Map：支持（Map. Stream.forEach）

ps： Map.stream.forEach 遍历的是 Map.Entry

Iterator

Fail

  • util包是fail-fast的（抛出ConcurrentModificationException异常）
  • concurrent包是fail-safe的

Question

Iterator和Itreable的区别

  • Iterator：迭代器，负责进行遍历
  • Itreable：可迭代，负责返回Iterator

Iterator和ListIterator的区别

  • Iterator只能向后遍历
  • ListIterator还可以向前遍历

如何高效的遍历容器

  • List使用fori的遍历方式最高效
  • Set和Map使用size + fori + iterator.next的遍历方式效率比foreach更高

List遍历时调用list.remove删除元素会有什么问题

  • 迭代器会检查到迭代器的expectedModCount和list的modCount不一致而抛出ConcurrentModificationException异常

List遍历时怎么安全的删除元素

  • 使用for遍历时需要从后向前遍历并可以删除当前及当前之后的元素
  • 使用迭代器遍历时需要使用迭代器的删除方法
  • 任何方式遍历时可以将不需要删除的元素添加到新的列表中去

Sorting

Sorting：排序

Basic

Comparator

Comparable

Collation

Question

Comparator和Comparable的区别

  • Comparator：比较器，负责对任意两个对象进行比较
  • Comparable：可比较，负责比较当前对象和其他对象

Collections.sort和Arrays.sort的区别

Collections.sort调用了容器的sort方法，容器的sort方法又调用了Arrays.sort

Collections.sort和Stream.sorted的区别

  • Collections.sort时原地排序，不会返回新的容器
  • Stream.sorted是非原地排序，会返回新的容器

Nullable

Nullable：可空

Basic

空值支持情况总结如下：

  1. list都允许空值
  2. 除了CopyOnWriteArraySet的set都是基于map实现的，所以和map一样
  3. 其他安全容器、支持排序、支持优先级的容器不允许空值

Question

ConcurrentHashMap为什么key和value不能为null

  • 如果允许value为null，当get返回null时无法区分value是不存在还是value为null
  • 这时候就存在了存在二义性
  • 需要用containsKey来判断value是否存在
  • 如果value本来是不存在，当其他线程在当前线程的get和containsKey操作之间put了一个key相同的value，会导致当前线程判断value为存在，和实际情况不符而出现了bug
  • 如果value本来是存在的，当其他线程在当前线程的get和containsKey操作之间remove了一个key相同的value，会导致当前线程判断value为不存在，和实际情况不符而出现了bug

Stream

Basic

Usage

Paradigm

FP（Functional Programming 函数式编程）

SP（Stream Programming 流式编程）

计算核心：Map（映射和转换）、Reduce（归并和聚合）、Filter（过滤和筛选）
并行核心：Parallelism（并行度）、Partition（分区）、Merge（合并）

java

spark

RP（Reactive Programming 响应式编程）

RxJava

Rxjava链式调用原理

基于观察者模式实现的，并运用了责任链模式和装饰器模式

数据流转的实现
  1. Rxjava的Observable. OnSubscribe的作用类似于Producer（生产者）
  2. Rxjava的Subscriber的作用类似于Consumer（消费者）
  3. Rxjava的Observable. OnSubscribe（Producer）会通过lift操作或者subcribe操作生成Subscriber（Consumer）并在调用Observable. OnSubscribe的call方法时将Subscriber传递给Observable. OnSubscribe
  4. 当Observable. OnSubscribe的call方法执行时，Subscriber就会被调用
  5. 这样生产者和消费者模型就形成了，数据的流转就实现了
生产链的建立
  1. Observable会通过create操作创建第一个Observable. OnSubscribe
  2. 之后调用操作符函数时会通过lift操作创建一个新的Observable和Observable. OnSubscribe
  3. 新的Observable. OnSubscribe（通过内部类的方式）引用了上一个Observable. OnSubscribe
  4. 这样Observable. OnSubscribe通过Observable的创建从前到后的建立了依赖关系
  5. 生产链依赖就形成了
生产链的触发
  1. 当Observable.subcribe方法调用时，最后那个Observable. OnSubscribe的call方法就会被调用
  2. 当每个Observable. OnSubscribe的call方法调用时，都会触发上一个Observable. OnSubscribe的call方法被调用
  3. 这样Observable. OnSubscribe通过从后到前的递归调用，生产链调用就触发了
消费链的建立
  1. Observable会通过subcribe操作创建最后一个Subscriber
  2. 之后subcribe操作触发Observable. OnSubscribe的call方法执行时会创建一个新的Subscriber
  3. 新的Subscriber引用了当前Observable使用的Subscriber，并被传递给了上一个Observable使用
  4. 这样Subscriber通过Observable的执行从后到前建立了依赖关系
  5. 消费链依赖就形成了
消费链的触发
  1. 当Observable. OnSubscribe的call方法执行时，Subscriber的onNext方法就会执行
  2. 映射操作时Subscriber的onNext方法执行时会直接触发下一个Subscriber的onNext方法，聚合操作时Subscriber的onNext方法执行时会将数据缓存起来等到onCompleted方法执行时再依次触发下一个Subscriber的onNext方法
  3. 这样Subscriber通过从前到后的顺序执行，消费链执行就触发了

Safe

Basic

Solution

安全容器的实现方案

  • 悲观锁（LOCK）：适合 低并发 、 常规读写 、 强一致性 的场景，比如Blocking系列中的BlockingQueue、BlockingDeque
  • 乐观锁（CAS ）：适合 高并发 、 读多写少 、 弱一致性 的场景，比如Concurrent系列中的ConcurrentHashMap，ConcurrentLinkedQueue、ConcurrentLinkedDeque
  • 写时复制（COW）：适合 高并发 、 读多写少 、 弱一致性 的场景，比如CopyOnWrite系列中的CopyOnWriteArrayList、CopyOnWriteArraySet

ps：CAS如果写多的话，竞争激烈时大量的失败导致cpu做了很多无用功从而占用和浪费cpu资源
ps：COW如果写多的话，频繁分配内存时来不及回收会造成内存占用过高
ps：CAS比COW的效率更高，但CAS支持设置操作却不支持插入和删除的操作

安全Map的演化过程

  • Hashtable：对整个Map进行加锁
  • ConcurrentHashMap（Segment）：对分段进行加锁
  • ConcurrentHashMap（cas + lock）：对链表头部的元素进行加锁（元素为null时则使用cas）

Consistency

按照数据分

  • 强一致性（strict consistency）：每次读都能读到最新写入的数据
  • 弱一致性（weak consistency）：可能永远读不到或者稍后才能读到最新写入的数据
  • 最终一致性（eventual consistency）：之后的某个时间一定能读到最新写入的数据

ps：弱一致性可能永远读不到最新写入的数据，而最终一致性在之后的某个时间一定能读到最新写入的数据

按照事件分

  • 顺序一致性（sequential consistency）：保证同一对象的事件先后顺序，不同对象的事件无顺序要求
  • 线性一致性（linear consistency）：保证同一对象的事件先后顺序，也保证不同对象的事件先后顺序

ConcurrentHashMap

CopyOnWriteArrayList

Theory

容器用到的数据结构和算法可以参考这里（原创） dsa

优先级队列实现：堆
可排序字典实现：红黑树或者跳表

List

Basic

ArrayList

LinkedList

CopyOnWriteArrayList

Question

ArrayList

ArrayList是如何扩容的
  • 初始容量：10（可通过initialCapacity设置）
  • 负载因子：1
  • 扩容时机：存入数据前
  • 扩容条件： size + 1 > capacity
  • 扩容计算： capacity + capacity >> 1
  • 扩容迁移：不需要迁移
ArrayList为什么按大约1.5倍扩容
  • 小于1.5倍时太小，会导致频繁扩容
  • 大于1.5倍时太大，会导致内存浪费

Set

Basic

HashSet

HashSet基于HashMap实现

LinkedHashSet

LinkedHashSet基于LinkedHashMap实现

TreeSet

TreeSet基于TreeMap实现

CopyOnWriteArraySet

CopyOnWriteArraySet基于CopyOnWriteArrayList实现

ConcurrentSkipListSet

ConcurrentSkipListSet基于ConcurrentSkipListMap实现

Map

Map的核心逻辑

  • constructor：构造过程
    • initialCapacity：初始容量
    • loadFactor：负载因子
    • threshold：扩容阈值
  • operation
    • put：写入元素过程
      • locate
        • hash：求哈希（高低位进行与操作减少hash碰撞）
        • index：求下标（容量为2的n次方时可以使用按位与运算代替求余运算来加快运算速度）
      • resize：扩容
        • reindex：重新求下标（通过hash的第n位来快速确定新位置是原位置还是原位置加原容量的长度）
        • transfer：移动元素（如果位置有变化的话）
      • store
        • update：遍历链表并用key的equals方法判断Node是否已存在，存在则更新value，不存在则创建并插入
        • create：创建并插入（头插法和尾插法）
    • get：获取元素过程
    • size：获取大小过程
  • safe
    • put：java7使用Reentrantlock锁住segment，java8使用CAS + synchronized锁住头结点
    • get：java7使用Reentrantlock锁住segment，java8使用volatile
    • size：java7无锁最多计算3次，java8使用baseCount和CounterCell数组

Basic

Map

HashMap

LinkedHashMap

TreeMap

ConcurrentHashMap

ConcurrentSkipListMap

Question

Map

为什么重写equals时要重写hashCode
  • 为了避免equals相等而hashCode不相等时导致map可以将两个相等的key存在不同的槽位而违背了key不重复的原则
  • 为了避免用另一个和A对象相等的B对象去map中找A时由于hashCode不相等而找不到A的情况
重写equals和hashCode的设计原则
  • equals相等，hashCode一定相等
  • equals不相等，hashCode不一定不相等
  • hashCode相等，equals不一定相等
  • hashCode不相等，equals一定不相等
hash冲突如何解决
  • 开放定址法：冲突后寻找下一个空位置插入，查找时会顺着冲突位置往下查找
    • 线性探测法
    • 平方探测法
    • 再哈希探测法
  • 链地址法：冲突的部分在同一个位置用链表链接起来，查找时会在链表中查找
  • 公共溢出区：冲突的部分都放到另一个列表中，找不到时会在溢出表中顺序查找
hash方法为何要进行位移后异或

是为了让hash值更加分散，减少hash冲突

Map的容量大小为什么必须是2的幂次方
  1. 加快索引计算：计算索引位时可以使用按位与运算代替求余运算来加快运算速度
  2. 加快索引计算：扩容后重新计算索引位时可以通过hash的第n位来快速确定新位置
  3. 减少哈希冲突：按位与运算时其中一个数都是1，增大了hash分布范围，减少了hash冲突
Map是如何扩容的

HashMap

java7和java8的HashMap区别
区别点 jdk7 jdk8
存储结构 数组 + 链表 数组 + 链表 + 红黑树
逻辑结构 Entry Node
结点插法 头插法 尾插法
哈希（hash）算法 较复杂 较简单（冲突了可以树化）
下标（index）算法 较复杂 较简单（使用了按位与运算代替求余运算）
扩容时机 存入数据前判断 存入数据后判断
扩容条件 大小超过阈值且存在hash冲突 大小超过阈值 或者 链表大小大于8且桶个数小于64
扩容迁移 所有元素重新求槽位 用新容量的最高有效位与hash中的相同位进行异或来快速确定新槽位

ps：大小超过阈值 =》 size > threshold

ps：hash冲突 =》 entry != null

java8的HashMap为什么要用红黑树

红黑树是查找树，可以使用二分查找，查找次数比链表少

  • 跳表需要数据有序
    • HashMap中查找使用的hashcode是散列无序的
  • 跳表占用的空间比红黑树多
    • 跳表需要维护额外的多层链表，需要占用额外的空间
    • 红黑树不需要占用额外的空间
java8的HashMap中的红黑树是排序规则
  • 实现了Comparable接口则用Comparable接口排序
  • 否则用类的名字的自然顺序排序
  • 类名相同的使用对象的hashcode的自然顺序排序
java8的HashMap中链表和红黑树的转换条件

树化：链表大小大于8，且桶个数大于或等于64（小于64时会扩容而不会树化）
链化：链表大小小于或等于6

HashMap是如何扩容的
  • 初始容量：16（可通过initialCapacity设置）
  • 负载因子：0.75
  • 扩容时机：
    • java7：存入数据前
    • java8：存入数据后
  • 扩容条件
    • java7：大小超过阈值且存在hash冲突
    • java8：大小超过阈值 或者 链表大小大于8且桶个数小于64
  • 扩容计算：
    • java7：扩容到原来的2倍
    • java8：扩容到原来的2倍
  • 扩容迁移：
    • java7：所有元素重新求槽位
    • java8：用新容量的最高有效位与hash中的相同位进行异或来快速确定新槽位
HashMap有哪些并发问题
  • 并发更新时导致更新丢失
  • 并发扩容时导致链表插入死循环（java8时已通过尾插法解决）
HashMap使用时如何保证线程安全

ConcurrentHashMap

java7和java8的ConcurrentHashMap区别
区别点 jdk7 jdk8
存储结构 数组 + 链表 数组 + 链表 + 红黑树
逻辑结构 Segment + HashEntry + lock（segment） Node + cas + synchronized（head）
结点插法 头插法 尾插法
哈希（hash）算法 和HashMap一样 和HashMap一样
下标（index）算法 需要index两次 只需要index一次
扩容时机 和HashMap一样 和HashMap一样
扩容条件 和HashMap一样 和HashMap一样
扩容迁移 单线程扩容迁移 多线程扩容迁移
大小计算 先无锁计算三次，如果结果一样则返回计算结果，否则就会锁住所有的Segment求和 通过baseCount和遍历CounterCell数组计算出size
java7的ConcurrentHashMap的并发度是什么

ConcurrentHashMap的并发度是指ConcurrentHashMap支持同时读写的线程数

java8的ConcurrentHashMap为什么放弃了分段锁
ConcurrentHashMap是如何计算size的

java7通过比较前后两次的所有Segment的size之和，如果结果一样则返回计算结果，如果不一样则继续计算并比较最多计算3次后还不一样，就会锁住所有的Segment求和
java8通过baseCount和遍历CounterCell数组计算出size

ConcurrentHashMap是如何扩容的

整体流程和HashMap一样，并支持多线程扩容和分桶迁移

  • 写入和迁移的流程
    • 读取头结点并判断是否为null，为null则cas
      • 写入时cas的新值是新结点
      • 迁移时cas的新值是fwd结点
    • 头结点不为null时，判断是否是迁移中(头结点的hash等于MOVED代表迁移中)
      • 写入时如果是迁移中就帮助迁移（helpTransfer）
      • 迁移时如果是迁移中就什么也不做
    • 否则就锁住头结点进行操作

ps：迁移时是按照桶为单位分配给线程进行迁移的
ps：迁移中是指整个表还在迁移中，而不是某个桶还在迁移中
ps：头结点不为null且头结点的hash等于MOVED代表迁移中

  • 写入时的迁移操作
    • 写入时如果桶为空，由于CAS写入时是原子操作，则迁移操作会在写入完成之后执行
    • 写入时如果桶不为空，由于写入时会锁住头结点，则迁移操作获取头结点的锁时会被阻塞
  • 迁移时的读操作
    • 如果桶的头结点是fwd结点，则表示迁移完成，可以通过fwd结点的nextTable找到新表进行读取
    • 如果检测到正在迁移中，由于迁移时是复制结点的引用而不是删除，所以在原表中还可以读到结点
  • 迁移时的写操作
    • 如果桶的头结点是fwd结点，则表示迁移完成，可以通过fwd结点的nextTable找到新表进行写入
    • 如果检测到正在迁移中，则先放弃写入操作并帮助扩容迁移，扩容迁移完后再写入

扩容相关的属性

  • table：当前表（旧表）
  • nextTable: 新表
  • sizeCtl: 表状态
    • sizeCtl = 0：表示没有指定初始容量
    • sizeCtl > 0：表示初始容量(可以使用阶段)
    • sizeCtl = -1, 标记作用，告知其他线程，正在初始化
    • sizeCtl = 0.75n , 扩容阈值
    • sizeCtl < 0 : 表示有其他线程正在执行扩容or初始化(不能使用阶段)
    • sizeCtl = (resizeStamp(n) << RESIZE_STAMP_SHIFT) + 2 : 表示此时只有一个线程在执行扩容
  • transferIndex: 正在迁移的桶索引
  • ForwardingNode结点: fwd结点，标记此结点的数据已经迁移完毕
ConcurrentHashMap是如何保证线程安全的

cas（槽位值为null） + synchronized（锁链表头部）

ConcurrentHashMap还有并发问题吗

有，单个操作是安全的，复合操作不是安全的

Queue

Basic

ArrayDeque

LinkedList

参考List部分的LinkedList

PriorityQueue

ArrayBlockingQueue

LinkedBlockingQueue

SynchronousQueue

LinkedTransferQueue

PriorityBlockingQueue

DelayQueue

DelayedWorkQueue

LinkedBlockingDeque

ConcurrentLinkedQueue

ConcurrentLinkedDeque

Question

ArrayBlockingQueue是如何实现阻塞功能的

使用了ReentrantLock的Condition来实现阻塞和唤醒的

  • notEmptyCondition：入队时signal，出队时如果为空则await
  • notFullCondition：出队时signal，入队时如果为满则await

Stack

Basic

LinkedList

参考List部分的LinkedList

Other

为什么没有ConcurrentArrayList

为什么没有ConcurrentHashSet

Utils

Java

Arrays、Collections、Comparator

Apache Commons

ArrayUtils、CollectionUtils、ListUtils、SetUtils、MapUtils、ComparatorUtils

Google Guava

Lists、Sets、Maps、Ordering、Range、RangeSet、RangeMap、Table、Tables

只想买包辣条