首页  思维导图  详情

Java集合|容器大全

2021-02-02 17:17:31   75  举报





AI智能生成

Java集合|容器大全

Java集合

java容器

JUC 并发

AQS

ReentrantLock

学习总结

后端开发

软件开发

读书笔记

作者其他创作

大纲/内容

图

Collection

Map

普通容器

Collection

List

ArrayList

结构构成

int modCount

记录更改次数，应用于fast-fail

int size

当前数组元素个数

int DEFAULT_CAPACITY = 10

Object[] elementData

Object[] EMPTY_ELEMENTDATA = {}

Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}

方法

构造

ArrayList()

数据数组初始化指向内部默认的空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA

ArrayList(int initialCapacity)

长度＞0，数据数组初始化对应长度

长度=0，数据数组初始化指向内部默认的空数组EMPTY_ELEMENTDATA

长度＜0，异常

ArrayList(Collection<? extends E> c)

增

add(E e)

add(int index, E element)

从指定位置元素后挪一位（复制实现），然后设值

add(E e, Object[] elementData, int s)

如果发现超过数组长度，则先调用grow()扩容

grow()

grow(int minCapacity)

初始化时调用的默认无参构造函数

数组长度直接变为DEFAULT_CAPACITY

否则

数组长度变为1.5倍

不能超过Integer.MAX_VALUE - 8

删

remove(int index)

remove(Object o)

若o为null，遍历，移除第一个null

若o不为null，遍历，移除第一个equals的

fastRemove(Object[] es, int i)

若在末尾，直接置为null

否则复制移动

改

set(int index, E element)

查

contains(Object o)

indexOfRange(Object o, int start, int end)

若o为null，遍历，找到第一个null

若o不为null，遍历，找到第一个equals的

其他

iterator()

hasNext()

next()

检查modCount，不一致则fast-fail抛出ConcurrentModificationException

获取数组后再次检查下标，越界了同样抛出ConcurrentModificationException

remove()

检查modCount，不一致则fast-fail抛出ConcurrentModificationException

若越界、删除失败说明有并发操作，抛出ConcurrentModificationException

forEachRemaining(Consumer<? super E> action)

sort(Comparator<? super E> c)

LinkedList

结构构成

int size = 0

Node<E> first

Node<E> last

方法

构造

LinkedList()

LinkedList(Collection<? extends E> c)

增

linkLast(E e)

add(E e)

offer(E e)

删

unlinkFirst(Node<E> f)

remove(Object o)

改

set(int index, E element)

从近的一端开始遍历

查

get(int index)

从近的一端开始遍历

indexOf(Object o)

从近的一端开始遍历

Vector

结构构成

Object[] elementData

int elementCount

int capacityIncrement

扩容时的默认大小

方法

构造

Vector()

默认大小10

Vector(int initialCapacity)

Vector(int initialCapacity, int capacityIncrement)

默认capacityIncrement=0

增

grow(int minCapacity)

默认扩容到2倍

如果capacityIncrement更大，则扩容到oldCapacity+capacityIncrement

不推荐原因

性能差

子类

Stack

方法

push(E item)

pop()

peek()

不推荐原因

继承了Vector

可以修改栈中元素，破坏了封装。应该为组合关系

Set

Hashset

结构构成

HashMap<E,Object> map

Object PRESENT = new Object()

作为所有key的val

方法

构造

HashSet()

HashSet(int initialCapacity, float loadFactor)

HashSet(int initialCapacity, float loadFactor, boolean dummy)

包可见

为子类构造方法服务，构造出LinkedHashMap

增

add(E e)

删

remove(Object o)

查

contains(Object o)

子类

LinkedHashset

方法

构造

LinkedHashSet()

LinkedHashSet(int initialCapacity, float loadFactor)

Treeset

结构构成

NavigableMap<E,Object> m

Object PRESENT = new Object()

作为所有key的val

方法

构造

TreeSet()

TreeSet(NavigableMap<E,Object> m)

Queue

Deque

ArrayDeque

结构构成

Object[] elements

int head

初始0

int tail

初始0

int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8

方法

构造

ArrayDeque()

默认大小16/17

ArrayDeque(int numElements)

旧版大小为2的n次幂

ArrayDeque(Collection<? extends E> c)

增

int inc(int i, int modulus)

int dec(int i, int modulus)

addFirst(E e)

放入--head的地方

从大端开始向左延伸

addLast(E e)

放入tail++的地方

从小端开始向右延伸

offer

同add

grow(int needed)

增长长度为Math.max(needed,0.5倍)

如果长度<64则扩大到两倍

如果之前head有元素，还需要后挪

删

pollFirst()

空队列返回null

pollLast()

空队列返回null

removeFirst()

空队列抛出异常

removeLast()

空队列抛出异常

removeFirstOccurrence(Object o)

delete(int i)

包可见性

删除数组中间某一位数

查

peekFirst()

空队列返回null

peekLast()

空队列返回null

getFirst()

空队列抛出异常

getLast()

空队列抛出异常

LinkedList

PriorityQueue

结构构成

int DEFAULT_INITIAL_CAPACITY = 11

Object[] queue

Comparator<? super E> comparator

int modCount

int size

当前队列元素个数

方法

构造

PriorityQueue()

默认大小DEFAULT_INITIAL_CAPACITY

默认无比较器

PriorityQueue(int initialCapacity,Comparator<? super E> comparator)

增

offer(E e)

先检查扩容

再插入

siftUp(int k, E x)

若初始化时传入了Comparator则使用

否则调用compareTo方法

grow(int minCapacity)

长度<64？

扩大到2倍

否则

扩大到1.5倍

删

poll()

空队列返回null

重新建堆

将队列最后一个元素值赋值给队首

从指定的位置开始，逐层向下与当前点的较小的孩子交换，直到比两个孩子都小

查

indexOf(Object o)

Map

分类

HashMap

结构构成

常量

int DEFAULT_INITIAL_CAPACITY = 16

默认初始容量

int MAXIMUM_CAPACITY = 1 << 30

最大容量

float DEFAULT_LOAD_FACTOR = 0.75f

默认负载因子

int TREEIFY_THRESHOLD = 8

链表长度的树化阈值

MIN_TREEIFY_CAPACITY = 64

树化容量阈值

UNTREEIFY_THRESHOLD = 6

逆树化阈值

变量

Node<K,V>[] table

jdk7

空

jkd8

延迟初始化到第一次put

Set<Map.Entry<K,V>> entrySet

int size

int modCount

int threshold

初始时的默认容量

开始扩容的阈值

float loadFactor

内部类Node<K,V>

int hash

K key

V value

Node<K,V> next

指示哈希冲突时同一个位置的下一个节点

内部类TreeNode<K,V>

TreeNode<K,V> parent

TreeNode<K,V> left

TreeNode<K,V> right

TreeNode<K,V> prev

为链表化服务

boolean red

方法

构造

HashMap()

全属性默认值

HashMap(int initialCapacity)

threshold值设为2的n次幂

服务于hash掩码

HashMap(int initialCapacity, float loadFactor)

threshold值设为2的n次幂

服务于hash掩码

增

JDK1.7

put(K key, V value)

addEntry(int hash, K key, V value, int bucketIndex)

createEntry(int hash, K key, V value, int bucketIndex)

头插法

如果下次get会很快取到

JDK1.8

put(K key, V value)

putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

若未初始化则先初始化

若hash位置上为null，说明之前没放过这个key也没有哈希冲突，直接新建节点放上去

否则

如果hash相同，且key相同或者满足equals

直接替换节点value

返回旧value

如果是树节点

如果是链表节点

遍历如果找到相同key

否则在链表结尾新建节点

如果链表长度达到TREEIFY_THRESHOLD=8

如果数组长度没超过MIN_TREEIFY_CAPACITY，说明主要原因是长度不够的问题，选择resize（）

否则树化当前位置

如果链表长度＞threshold，调用resize

删

remove(Object key)

removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)

从哈希位置上找到对应的节点

树节点

单节点或者是链表的头节点

直接替换成next节点

链表节点

更换next节点，挖出

Node#removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable)

改

treeifyBin(Node<K,V>[] tab, int hash)

首先形成一个树节点的列表，完成next指针

然后以根节点开始树化

TreeNode#treeify(Node<K,V>[] tab)

从头结点开始遍历处理

如果是第一个节点，则标记为根节点，直接标为黑色

否则依次插入树中并调整

根据hash值比较，小于走左子树，大于走右子树，直到当前节点为null，插入到当前位置

从这个新节点x开始平衡新树，调整颜色、进行必要的旋转，返回计算出的新的root

x先定为red

如果x无父节点，说明x是根直接返回x，调整结束

如果x父节点是black，直接返回原root，调整结束

否则x父节点为red

如果x的叔节点也为red

x的爷节点变为red，x的父节点和叔节点都变为black

x变为x的爷节点，递归处理

否则

旋转

重复变色

根据上一步计算出的新root，调整根节点

直接把新root从链表中间挖出来，插入到链表头即可，处理相关next和prev指针

查

get(Object key)

其他

hash(Object key)

JDK7

4次位运算+5次异或

JDK8

右移16位扰动

1次位运算+1次异或

resize()

JDK7

依次复制

复制的时候会翻转链表

JDK8

未初始化

指定了初始化容量

数组大小指定

新threshold值变为newCap * loadFactor

未指定

数组大小取默认值16

新threshold值变为newCap * loadFactor

已初始化

数组扩容2倍

新threshold值变为2倍（数组大小比默认值大之后）

遍历复制

单点

计算新的hash值直接复制

树点

链表点

JDK1.7

JDK1.8

保持原有链表顺序

利用两个链表分别储存同样位置的节点、位置增加一倍的节点

只需要看hash值的n+1位是0还是1

遍历形成两个链表，复制到新数组相应位置上

问题

重写equals和hashCode方法

并发问题

1.7

resize时并发造成循环链表，get时发生死循环

1.8

数据丢失

当多线程put的时候，当index相同而又同时达到链表的末尾时，
另一个线程put的数据会把之前线程put的数据覆盖掉

子类

LinkedHashMap

结构构成

Entry<K,V> head

Entry<K,V> tail

boolean accessOrder

true

access-order

get一个元素后，这个元素被加到最后

false

insertion-order

内部类Entry<K,V>

extends HashMap.Node<K,V>

Entry<K,V> before, after

方法

构造

LinkedHashMap()

默认为插入顺序

LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

增

同父类

newNode(int hash, K key, V value, Node<K,V> e)

newTreeNode(int hash, K key, V value, Node<K,V> next)

linkNodeLast(LinkedHashMap.Entry<K,V> p)

删

同父类

afterNodeRemoval(Node<K,V> e)

查

同父类

WeakHashMap

结构构成

ReferenceQueue<Object> queue = new ReferenceQueue<>()

内部类Entry<K,V>

extends WeakReference<Object>

构造

方法

同1.7HashMap

问题

key为Integer时，-128-127的Integer会被一直缓存，不会被释放

TreeMap

结构构成

Comparator<? super K> comparator

Entry<K,V> root

int size = 0

内部类Entry

K key

V value

Entry<K,V> left

Entry<K,V> right

Entry<K,V> parent

boolean color = BLACK

方法

构造

TreeMap()

TreeMap(Comparator<? super K> comparator)

增

put(K key, V value)

检查key是否为null

计算得到插入的位置，若已有key则替换val，否则新建节点插入

平衡红黑树

删

remove(Object key)

deleteEntry(Entry<K,V> p)

查

get(Object key)

getEntry(Object key)

HashTable

结构构成

同HashMap

方法

构造

默认大小11，每次扩容到2n+1

同步的JDK1.7HashMap

问题

hash索引计算方法为取余，因为数组长度没有定位2的次幂

父类Dictionary被废弃

子类

Properties

结构构成

volatile Properties defaults

volatile ConcurrentHashMap<Object, Object> map

同步容器

Collections.synchronizedXxx（）

List

SynchronizedList

结构构成

Collection<E> c

List<E> list

Object mutex

锁对象

方法

构造

SynchronizedList(List<E> list)

SynchronizedList(List<E> list, Object mutex)

全部方法需要同步

SynchronizedRandomAccessList

Map

SynchronizedMap

结构构成

final Map<K,V> m

Object mutex

方法

构造

SynchronizedMap(Map<K,V> m)

SynchronizedMap(Map<K,V> m, Object mutex)

全部方法需要同步

Set

SynchronizedSet

问题

通过Iterator、Spliterator或Stream遍历时，需要手动在外部做好同步

并发容器

List

CopyOnWriteArrayList

原理

写时复制快照，之后用新数组替换原数组

结构构成

Object lock = new Object()

JDK8？之后改ReentrantLock为synchronized（lock）

volatile Object[] array

accessed only via getArray/setArray

方法

构造

CopyOnWriteArrayList()

增

add(E e)

进入同步

复制一个新数组，长度为旧数组长度+1

设置数组末尾的新值

替换成新数组

删

remove(int index)

复制剩余值到新数组中

改

set(int index, E element)

如果新值与旧值不同，克隆出新数组，在新数组上修改再替换

如果相同，也要再写一遍保证volatile语义

查

get(int index)

elementAt(Object[] a, int index)

其他

iterator

保存着原数组的引用，因此迭代过程中原数组发生的改变不影响此次迭代

弱一致性

Map

ConcurrentHashMap

原理

1.7

Segment+ HashEntry

基于currentLevel（默认16）划分出了多个Segment来对key-value进行存储

put、remove会加锁，get和containsKey不会加锁

get到的值为null时会加锁

#size

在不加锁的情况下遍历所有的段，读取其count以及modCount，
这两个属性都是volatile类型的，并进行统计，再遍历一次所有的段，比较modCount是否有改变。
如有改变，则再尝试两次。

如执行了三次上述动作，仍然有问题，则遍历所有段，分别进行加锁，然后进行计算。
计算完毕后释放所有锁，从而完成计算动作。

1.8

CAS+synchronized

每个bin的第一个Node插入、删除、替换使用CAS

#size

累加各个bin中Node的个数计算得到，而且这一过程不加锁，即得到的size值不一定是最新的

结构构成

常量

同HashMap

int MIN_TRANSFER_STRIDE = 16

int RESIZE_STAMP_BITS = 16

int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1

int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS

变量

volatile Node<K,V>[] table

延迟初始化到第一次put

volatile Node<K,V>[] nextTable

volatile long baseCount

volatile int sizeCtl

指示表初始化和扩容，默认值为0

当在初始化的时候指定了大小，这会将这个大小保存在sizeCtl中，大小为数组的0.75

当为负的时候，说明表正在初始化或扩张

-1表示初始化

-N 表示有N-1个线程正在进行扩容操作

如果table未初始化，表示table需要初始化的大小

如果table初始化完成，表示table的扩容阈值，默认是table大小的0.75倍

volatile int transferIndex

volatile int cellsBusy

volatile CounterCell[] counterCells

Unsafe U = Unsafe.getUnsafe()

内部类

Node<K,V>

int hash

K key

volatile V val

volatile Node<K,V> next

TreeNode<K,V>

同HashMap

TreeBin<K,V>

TreeNode<K,V> root

volatile TreeNode<K,V> first

volatile Thread waiter

volatile int lockState

树化后当作整棵树储存在数组中

ForwardingNode<K,V>

Node<K,V>[] nextTable

在转移的时候放在头部的节点，是一个空节点

ReservationNode<K,V>

方法

构造

ConcurrentHashMap()

ConcurrentHashMap(int initialCapacity， float loadFactor, int concurrencyLevel)

初始化sizeCtl

增

put(K key, V value)

putVal(K key, V value, boolean onlyIfAbsent)

数组为null或长度为0，先初始化

如果哈希位置上没有节点，新建节点CAS插入即可。如果插入失败进入下一步

否则有节点

否则

同步这个节点

如果取出来的节点的hash值是MOVED(-1)的话，则表示当前正在对这个数组进行扩容并复制到新的数组，则当前线程也去帮助复制，之后再继续插入的工作

如果是链表(hash大于0)，进行更新或者插入，并统计链表长度

如果是TreeBin，说明是树，调用TreeBin#putTreeVal添加到树中

如果链表长度大于阈值了，调用#treeifyBin，树化或扩容

链表长度+1

addCount(long x, int check)

删

remove(Object key)

改

casTabAt(Node<K,V>[] tab, int i，Node<K,V> c, Node<K,V> v)

cas原子操作，在指定位置设定值

setTabAt(Node<K,V>[] tab, int i, Node<K,V> v)

原子操作，在指定位置设定值

treeifyBin(Node<K,V>[] tab, int index)

如果数组长度<64,则选择扩容2倍

否则

同步头结点

先遍历链表，处理TreeNode的next指针

新建TreeBin，构造了红黑树

调用#setTabAt，将此处节点换成TreeBin

hash为-2

tryPresize(int size)

查

tabAt(Node<K,V>[] tab, int i)

Unsafe

返回节点数组的指定位置的节点的原子操作

get(Object key)

其他

initTable()

循环判断当前数组是否为null或长度为0，当否时就返回，否则进入循环

如果sizeCtl<0，说明有线程正在初始化，yield当前线程

否则尝试将sizeCtl CAS为 -1，表示当前线程要开始初始化，失败了就回到上一步

否则CAS成功

新建数组，若初始化时指定了长度（保存在sizeCtl）则使用，否则默认长度16

sizeCtl长度变为数组长度的3/4

Queue

ConcurrentLinkedQueue

结构

volatile Node<E> head,tail = new Node<E>()

默认头、尾节点都是指向 item 为 null 的哨兵节点。新元素会被插入队列末尾，出队时从队列头部获取一个元素

tail结点不总是最后一个结点

减少volatile变量的写开销

内部类Node

volatile E item

volatile Node<E> next

使用 UnSafe(现在改为VarHandle) 的 CAS 算法来保证出入队时操作链表的原子性。

方法

增

#offer(E e)

新建Node

从tail节点开始一直向后找到last Node

CAS插入

若失败重新循环

CAS更新tail

失败也没关系

如果发现遍历到的节点next指向自身

说明该节点已被删除，不在队列上

只能从head重新开始遍历

删

#poll

查

其他

#size

并发环境下不一定准确

Set

CopyOnWriteArraySet

AbstractQueuedSynchronizer

依赖工具类

LockSupport

作用

调用Unsafe类方法挂起、唤醒线程

结构构成

Unsafe unsafe = Unsafe.getUnsafe()

方法

#park()

=Unsafe#park(false, 0L);

如果调用 park 方法的线程已经拿到了与 LockSupport 关联的许可证，则马上返回

否则调用线程被持续阻塞挂起

#park(Object blocker）

当钱程在没有持有许可证的情况下调用 park 方法而被阻塞挂起时，这个 blocker 对象会被记录到该线程内部。

使用诊断工具可以观察线程被阻塞的原因，所以 JDK 推荐我们使用带有 blocker 参数的 park 方法，
并且blocker被设置为 this ,这样当在打印线程堆栈排查问题时就能知道是哪个类被阻塞了

诊断工具是通过调用 getBlocker(Thread) 方法来获取 blocker 对象的，

线程被激活后清除blocker

#parkNanos(long nanos ，Object blocker）

#unpark(Thread thread ）

调用 park方法而被阻塞的线程会返回

当一个线程调用 unpark 时，如果参数 thread 线程没有持有 thread 与 LockSupport 类关联的许可证，则让 thread 线程持有。

所以一个线程不会park两次

如果 thread 之前因调用 park （）而被挂起，则调用unpark 后，该线程会被唤醒。

结构构成

Thread exclusiveOwnerThread

当前拥有此排他锁的线程

volatile int state

状态信息，实现类定义具体意义

ReentrantLock

当前线程获取锁的可重入次数

ReentrantReadWriteLock

高16位表示读状态，也就是获取该读锁的次数

低 16 位表示获取到写锁的线程的可重入次数

semaphore

当前可用信号的个数

CountDownlatch

表示计数器当前的值

FutureTask

当前任务的状态

内部类Node

static Node SHARED = new Node()

当做参数，标记该Node的线程是获取共享资源时被阻塞挂起后放入 AQS 队列的

static Node EXCLUSIVE = null

当做参数，标记该Node的线程是获取独占资源时被挂起后放入AQS 队列的

volatile int waitStatus

记录当前线程等待状态

CANCELLED （线程被取消了）

线程超时或响应了中断

SIGNAL （线程需要被唤醒）

-1

每次都由SIGNAL节点唤醒下一个节点，充当闹钟

CONDITION （线程在条件队列里面等待〉

-2

PROPAGATE （释放共享资源时需要通知其他节点〕

-3

volatile Node prev

volatile Node next

volatile Thread thread

对应进入AQS队列里面的一个线程

Node nextWaiter

队列中下一个节点的类型

volatile Node head

固定是一个dummy node，因为它的thread成员固定为null

volatile Node tail

尾节点，请求锁失败的线程，会包装成node，放到队尾

内部类 ConditionObject

Node firstWaiter

条件队列的头

Node lastWaiter

条件队列的尾

可以直接访问 AQS 对象内部的变量，比如 state 状态值和 AQS 队列

ConditionObject 是条件变量，每个条件变量对应一个条件队列（单向链表队列），其用来存放调用条件变量的await方法后被阻塞的线程

方法

基础

#isHeldExclusively

子类重写用来判断当前锁是独占还是共享

#enq(Node node)

给定节点，入队

当一个线程获取锁失败后该线程会被转换为Node节点，然后将该节点插入到AQS的阻塞队列。

若未初始化则先初始化，head和tail节点均指向一个空节点

CAS操作先替换tail节点，然后更改next指针

返回旧tail

#addWaiter(Node mode)

给定节点类型，添加新的等待线程节点，入队

返回新tail

操作资源

独占资源

#acquire(int arg)

当前线程调用tryAcquire 方法尝试获取资源

具体为设置状态变量 state 的值，成功则直接返回

失败则将当前线程封装为类型为 Node. EXCLUSIVE 的 Node 节点后插入到 AQS 阻塞队列的尾部

调用LockSupport#park( this ）方法挂起自己

如果循环过程中发生了中断，要重新设置好中断标志

#acquireQueued(final Node node, int arg)

用一个死循环不断去执行tryAcquire，直到获取锁

每次循环都会判断是否可以尝试获取锁（p == head），如果可以，那么尝试（tryAcquire(arg)）。
如果尝试获取锁成功，那么函数的使命就达到了，执行完相应收尾工作，然后返回。
如果不可以尝试或者尝试获取锁却失败了，那么阻塞当前线程（parkAndCheckInterrupt）。
如果当前线程被唤醒了，又会重新走这个流程。被唤醒时，是从parkAndCheckInterrupt处唤醒，然后从这里继续往下执行。

把node的有效前驱（node类型不是CANCELLED的）找到，并且将有效前驱的状态设置为SIGNAL，之后便返回true代表马上可以阻塞了

因为存在去除CANCELLED节点的操作，至少要循环两次才能阻塞自己。第一次设置前驱节点状态，第二次阻塞自己

返回interrupted标志

#acquirelnterruptibly(int arg）

获取资源或挂起时会响应中断，将对应Node状态标记为CANCELLED,之后移除该节点

#tryAcquireNanos(int arg, long nanosTimeout)

LockSupport.parkNanos(this, nanosTimeout);

#release(int arg）

当前线程尝试调用 tryRelease 方法释放资源

head状态不为0即唤醒head后继

共享资源

#acquireShared(int arg)

当前线程尝试调用tryAcquireShared方法尝试获取资源

设置状态变量 state 的值，成功则直接返回

失败则调用doAcquireShared将当前线程封装为类型为 Node.SHARED 的 Node 节点后插入到 AQS 阻塞队列的尾部

调用LockSupport#park( this ）方法挂起自己

#releaseShared(int arg）

当前线程尝试调用 tryReleaseShared 方法释放资源

调用 LockSupport.unpark(thread ）方法激活 AQS 队列里面被阻塞的一个线程（thread）

被激活的线程则使用 tryAcquireShared 尝试，看当前状态变量 state的值是否能满足自己的需要，满足则该线程被激活，然后继续向下运行

否则还是会被放入 AQS 队列并被挂起

条件变量

Condition#await

当线程调用条件变量的await()方法时，在内部会构造一个类型为Node.CONDITION的node节点，
然后将该节点插入条件队列末尾，之后当前线程会释放获取的锁(也就是会操作锁对应的state变量的值),
并被阻塞挂起。

这时候如果有其他线程调用lock.lock()尝试获取锁，就会有一个线程获取
到锁，如果获取到锁的线程调用了条件变量的await ()方法，则该线程也会被放入条件
变量的阻塞队列，然后释放获取到的锁，在await()方法处阻塞。

Condition#signal

当另外一个线程调用条件变量的signal方法时，在内部会把条件队列里面队头的一个线程节点
从条件队列里面移除并放入AQS的阻塞队列里面，然后调用unpark激活线程。

实现类

Lock

ReentrantLock

结构构成

state

当前线程获取锁的可重入次数

Sync sync

内部类

Sync extends AbstractQueuedSynchronizer

#nonfairTryAcquire(int acquires)

#tryRelease(int releases)

FairSync extends Sync

#tryAcquire(int acquires)

如果state=0且队列中前驱只有head节点，CAS尝试获取锁

如果重入，state+1

方法

构造

ReentrantLock()

默认非公平锁

ReentrantLock(boolean fair)

锁

#lock()

#lockInterruptibly()

ReentrantReadWriteLock

结构构成

Sync sync

state

高16bit作为读锁的计数范围

低16bit作为写锁的计数范围

ReadLock readerLock = new ReadLock(this)

WriteLock writerLock = new WriteLock(this)

内部类

Sync extends AbstractQueuedSynchronizer

NonfairSync extends Sync

FairSync extends Sync

ReadLock implements Lock

WriteLock implements Lock

HoldCounter

记录各个线程分别拿走了多少读锁

int count = 0

long tid = getThreadId(Thread.currentThread())

防止垃圾不被回收

ThreadLocalHoldCounter extends ThreadLocal<HoldCounter>

方法

Queue

ArrayBlockingQueue

结构

items 数组：存放队列元素

int putindex ：入队元素下标

int takelndex ：出队下标

int count ：队列元素个数

ReentrantLock lock

Condition notEmpty

Condition notFull

方法

同下，不过只用了一个全局锁，管理进和出

LinkedBlockingQueue

结构

单向无界链表

Node<E> head，Node<E>last

默认都是指向 item 为 null 的哨兵节点

AtomicInteger count

记录队列元素个数

ReentrantLock putLock

控制同时只能有一个线程可以获取锁，在队列尾部添加元素

Condition notFull = putLock.newCondition();

当队列满时，执行put的线程会被放入这个条件队列进行等待

ReentrantLock takeLock

控制同时只有一个线程可以从队列头获取元素

Condition notEmpty = takeLock.newCondition();

当队列为空时，执行take的线程会被放入这个条件队列进行等待

方法

构造

LinkedBlockingQueue()

默认大小Integer.MAX_VALUE

LinkedBlockingQueue(int capacity)

增

#put(E e)

加锁入队

如果队列满阻塞当前线程，加入notfull等待唤醒

阻塞时可被中断抛出异常

一定条件下唤醒notempty、notfull

#offer(E e)

如果队列满直接返回false

#add(E e)

如果队列满抛出异常

取

#take

从队列头部获取并移除一个元素

如果队列为空则阻塞当前线程直到队列不为空
如果在阻塞时被其他线程设置了中断标志，则被阻塞线程会抛出异常返回

#poll

从队列头部获取并移除一个元素

空队列直接返回null

#peek

从队列头部获取一个元素

空队列直接返回null

#remove(Object o)

删除队列里面指定的元素，有则删除并返回true，没有则返回false。

加双重锁

#size

PriorityBlockingQueue

结构

queue 数组：存放队列元素

默认长度11

平衡二叉树实现优先排序

int size ：队列元素个数

ReentrantLock lock

Condition notEmpty

队列空时，出队线程将阻塞在这里

无notnull，因为是无界队列，因此put操作非阻塞

volatile int allocationSpinLock

标识当前是否正在扩容

相当于AQS的state，持有这个state才可以准备新数组以扩容

方法

同上

#tryGrow(Object[] array, int oldCap)

如果oldCap < 64, 新容量等于2(oldCap + 1)

如果oldCap >=64, 新容量等于1.5oldCap

#size

加锁获取

DelayQueue

结构

PriorityQueue<E> q：存放队列元素

元素需要实现Delayed接口

只有元素到期后才能将其出队

到期时间短的Delayed元素排在队列前面

ReentrantLock lock

Condition available = lock.newCondition();

Thread leader

Leader- Follower 模式的变体，减少不必要的线程等待

它总是等待获取队首

方法

存

#offer(E e)

如果添加的元素是最先过期的

leader = null;

available.signal();

取

#poll

获取并移除队头过期元素

如果没有过期元素则返回 null

#take

#size

other

CountDownLatch

方法

#await

主线程调用后阻塞直到计数器为0

#countDown

子线程任务调用，计数减一

CyclicBarrier

方法

#await

某一线程调用后，计数器减一

若此时计数器不为0，调用线程阻塞直到计数器为0

否则当前线程执行构造函数里传入的任务，之后唤醒其他阻塞线程

可重用

Semaphore

方法

#release

某一线程调用后，计数器加一

#acquire(int n)

某一线程调用后，阻塞直到信号量为n

Executor

线程池

ThreadPoolExecutor

构成

AtomicInteger ctl

高3位用来表示线程池状态

低29位用来表示线程个数

初始值ctlOf(RUNNING, 0)

线程池状态

RUNNING

接受新任务并且处理阻塞队列里的任务

SHUTDOWN

拒绝新任务但是处理阻塞队列里的任务

STOP

拒绝新任务并且抛弃阻塞队列里的任务，同时会中断正在处理的任务

TIDYING

所有任务都执行完（包含阻塞队列里面的任务）后当前线程池活动线程
数为 0 ，将要调用 terminated 方法

TERMINATED

终止状态。 terminated 方法调用完成以后的状态

CAPACITY

线程最大个数（低29位） 00011111111111111111111111111111

runStateOf(int c) { return c &~CAPACITY ; )

获取高3位（运行状态）

workerCountOf(int c) { return c & CAPACITY ; )

获取低29位（线程个数）

ctlOf (int rs , int we) { return rs I we; )

计算ctl 新值（线程状态与线程个数）

ReentrantLock mainLock

控制新增 Worker线程操作的原子性

Condition termination = mainLock.newCondition();

线程调用 awaitTermination 时用来存放阻塞的线程

方法

ThreadPoolExecutor (
int corePoolSize,
int maximumPoolSize,
long keepAliveTime,
TimeUnit unit,
BlockingQueue <Runnable> workQueue ,
ThreadFactory threadFactory,
RejectedExecutionHandler handler
)

corePoolSize ：线程池核心线程个数

没有任务执行时线程池的大小

只有阻塞队列满时才会创建超出这个数量的线程

maximunPoolSize ：线程池最大线程数量。

keeyAliveTime ：存活时间

如果当前线程池中的线程数量比核心线程数量多，并且
是闲置状态，则这些闲置的线程能存活的最大时间

workQueue ：用于保存等待执行的任务的阻塞队列

基于数组的有界ArrayBlockingQueue

基于链表的无界 LinkedBlockingQueue

最多只有一个元素的同步队列 SynchronousQueue

优先级队列 PriorityBlockingQueue

RejectedExecutionHandler ：饱和策略