首页  思维导图  详情

Java集合体系

2020-09-29 15:50:35   0  举报





AI智能生成

Java集合体系脑图

Java集合体系

作者其他创作

大纲/内容

并发容器

CopyOnWriteArrayList

特性

通过可变数组实现

场景

List 大小通常保持很小，只读操作远多于可变操作，需要在遍历期间防止线程间的冲突

线程安全

因为通常需要复制整个基础数组，所以可变操作（add()、set() 和 remove() 等等）的开销很大

迭代器支持hasNext(), next()等不可变操作，但不支持可变 remove()等操作

使用迭代器进行遍历的速度很快，并且不会与其他线程发生冲突。在构造迭代器时，迭代器依赖于不变的数组快照

原理

动态数组机制

它内部有个“volatile数组”(array)来保持数据。在“添加/修改/删除”数据时，都会新建一个数组，并将更新后的数据拷贝到新建的数组中，最后再将该数组赋值给“volatile数组”。这就是它叫做CopyOnWriteArrayList的原因！CopyOnWriteArrayList就是通过这种方式实现的动态数组；不过正由于它在“添加/修改/删除”数据时，都会新建数组，所以涉及到修改数据的操作，CopyOnWriteArrayList效率很低；但是单单只是进行遍历查找的话，效率比较高。

线程安全机制

是通过volatile和互斥锁来实现的。 (01) CopyOnWriteArrayList是通过“volatile数组”来保存数据的。一个线程读取volatile数组时，总能看到其它线程对该volatile变量最后的写入；就这样，通过volatile提供了“读取到的数据总是最新的”这个机制的保证。 (02) CopyOnWriteArrayList通过互斥锁来保护数据。在“添加/修改/删除”数据时，会先“获取互斥锁”，再修改完毕之后，先将数据更新到“volatile数组”中，然后再“释放互斥锁”；这样，就达到了保护数据的目的。

字段

ReentrantLock

主要对添加、修改、删除操作加锁

Volatile Object[]

存储数据，并保证了可见性

方法

get

获取数组的引用并根据索引获取数据，该过程不需要添加锁，因为修改操作都是通过创建新数组（新内存）并赋予array数组，但其旧的内存数据是没有改变的，所以获取方法不需要加锁，但同事带来的问题是数据时效问题。

add

首先获取锁，然后通过Arrays.copyOf()方法创建新的数组，再把新数组的引用替换掉旧的array数组引用。

CopyOnWriteArraySet

通过CopyOnWriteArrayList实现

ConcurrentHashMap

通过锁的颗粒化实现，jdk1.7通过锁分段，jdk1.8通过在桶的首个元素节点加锁

key-value不能为空

jdk1.8

CAS + synchronized保证并发安全，底层通过数组+链表+红黑树实现

字段

table

默认为null，初始化发生在第一次插入操作，默认大小为16的数组，用来存储Node节点数据，扩容时大小总是2的幂次方

nextTable

默认为null，扩容时新生成的数组，其大小为原数组的两倍。

sizeCtl

默认为0，用来控制table的初始化和扩容操作，具体应用在后续会体现出来。 -1 代表table正在初始化 -N 表示有N-1个线程正在进行扩容操作其余情况： 1、如果table未初始化，表示table需要初始化的大小。 2、如果table初始化完成，表示table的容量，默认是table大小的0.75倍，居然用这个公式算0.75（n - (n >>> 2)）。

Node

保存key，value及key的hash值的数据结构

ForwardingNode

一个特殊的Node节点，hash值为-1，其中存储nextTable的引用。只有table发生扩容的时候，ForwardingNode才会发挥作用，作为一个占位符放在table中表示当前节点为null或则已经被移动

方法

put

通过CAS+synchronized实现并发插入或更新操作

1、若table为空，则先初始化table

2、通过key找到桶，如果当前桶为空时，通过CAS操作，将Node放入对应的bucket中

3、倘若当前map正在扩容f.hash == MOVED，则跟其他线程一起进行扩容

4、则采用synchronized关键字。倘若当前hash对应的节点是链表的头节点，遍历链表，若找到对应的node节点，则修改node节点的val，否则在链表末尾添加node节点；倘若当前节点是红黑树的根节点，在树结构上遍历元素，更新或增加节点。

5、是否需要扩容

get

1. 空tab，直接返回null

2. 计算hash值，找到相应的bucket位置，为node节点直接返回，否则返回null

size

ConcurrentHashMap的元素个数等于baseCounter和数组里每个CounterCell的值之和，这样做的原因是，当多个线程同时执行CAS修改baseCount值，失败的线程会将值放到CounterCell中。所以统计元素个数时，要把baseCount和counterCells数组都考虑。

扩容

触发扩容

1、当前容量超过阈值

2、当链表中元素个数超过默认设定（8个），当数组的大小还未超过64的时候，此时进行数组的扩容，如果超过则将链表转化成红黑树

3、当发现其他线程扩容时，帮其扩容

扩容分析（transfer实现）

1、根据当前数组长度n，新建一个两倍长度的数组nextTable

2、初始化ForwardingNode节点（占位符），其中保存了新数组nextTable的引用，当某个桶为空或列表元素迁移完成后设置该节点作为占位符，表示该桶位已经处理过了其它线程帮助扩容时不再处理该桶了，转而处理其它桶

3、通过for自循环处理每个桶位中的链表元素

3.1、若桶位中链表为空，设置占位符（ForwardingNode），提醒其它线程该桶位已经迁移完数据

3.2、若桶位中存在链表，为首节点加锁并遍历链表将链表迁移到新的数组（nextTable）中，迁移完成后设置占位符（ForwardingNode）。提醒其它线程该桶位已经迁移完成

jdk1.7

同步机制

分段锁，每个segment继承ReentrantLock

存储结构

数组+链表

概念图

字段

Segment

锁分段数组，每个分段中包含数组+链表，分段对象继承自ReentrentLock

方法

put

1、扩容

2、通过key找到对应的锁段位

3、根据数组+链表结构添加数据

4、全程加锁

get

不需要加锁，

与HashMap的区别

ConcurrentHashMap是HashMap的高并发版本

ConcurrentHashMap是否能完全替代HashTable

1、Hashtable的任何操作都会把整个表锁住，是阻塞的。好处是总能获取最实时的更新

2、ConcurrentHashMap 是设计为非阻塞的。在更新时会局部锁住某部分数据，但不会把整个表都锁住。同步读取操作则是完全非阻塞的。好处是在保证合理的同步前提下，效率很高

ConcurrentSkipListMap

通过跳表实现，有序，key-value不为空

数据结构

ConcurrentSkipListMap在原始链表的基础上增加了跳表的结构，所以需要两个额外的内部类来封装链表的节点，以及跳表的节点——Node和Index

同ConcurrentHashMap的Node节点一样，key为final，是不可变的，value和next通过volatile修饰保证内存可见性。

Index封装了跳表需要的结构，首先node包装了链表的节点，down指向下一层的节点（不是Node，而是Index），right指向同层右边的节点。 node和down都是final的，说明跳表的节点一旦创建，其中的值以及所处的层就不会发生变化（因为down不会变化，所以其下层的down都不会变化，那他的层显然不会变化）。 Node和Index内部都提供了用于CAS原子更新的AtomicReferenceFieldUpdater对象，至于该对象的原理下面是不会深入研究的。

方法

put

1、通过方法findPredecessor找到待插入位置的前继节点和后继节点

2、判断链表结构是否被破坏，如果是则循环执行。

3、通过CAS更新链表

4、更新索引节点，首先生成level，然后向level及以下每一层级添加索引

get

从头索引开始向右查找并比较，否则向下索引，如果能匹配上则校验该过程中是否有其他线程修改了该值，没有则返回，否则重新获取。

ConcurrentSkipListSet

通过ConcurrentSkipListMap实现

ArrayBlockingQueue

数组实现的线程安全的有界的阻塞队列、元素不为空，因只有一个锁，索引增删改互斥

线程安全是指，ArrayBlockingQueue内部通过“互斥锁”保护竞争资源，实现了多线程对竞争资源的互斥访问。而有界，则是指ArrayBlockingQueue对应的数组是有界限的。阻塞队列，是指多线程访问竞争资源时，当竞争资源已被某线程获取时，其它要获取该资源的线程需要阻塞等待；而且，ArrayBlockingQueue是按 FIFO（先进先出）原则对元素进行排序，元素都是从尾部插入到队列，从头部开始返回。

原理

1、ArrayBlockingQueue继承于AbstractQueue，并且它实现了BlockingQueue接口。

2. ArrayBlockingQueue内部是通过Object[]数组保存数据的，也就是说ArrayBlockingQueue本质上是通过数组实现的。ArrayBlockingQueue的大小，即数组的容量是创建ArrayBlockingQueue时指定的。

3. ArrayBlockingQueue与ReentrantLock是组合关系，ArrayBlockingQueue中包含一个ReentrantLock对象(lock)。 ReentrantLock是可重入的互斥锁，ArrayBlockingQueue就是根据该互斥锁实现“多线程对竞争资源的互斥访问”。而且，ReentrantLock分为公平锁和非公平锁，关于具体使用公平锁还是非公平锁，在创建ArrayBlockingQueue时可以指定；而且，ArrayBlockingQueue默认会使用非公平锁。

4. ArrayBlockingQueue与Condition是组合关系，ArrayBlockingQueue中包含两个Condition对象(notEmpty和notFull)。而且，Condition又依赖于ArrayBlockingQueue而存在，通过Condition可以实现对ArrayBlockingQueue的更精确的访问 -- (01)若某线程(线程A)要取数据时，数组正好为空，则该线程会执行notEmpty.await()进行等待；当其它某个线程(线程B)向数组中插入了数据之后，会调用notEmpty.signal()唤醒“notEmpty上的等待线程”。此时，线程A会被唤醒从而得以继续运行。 (02)若某线程(线程H)要插入数据时，数组已满，则该线程会执行notFull.await()进行等待；当其它某个线程(线程I)取出数据之后，会调用notFull.signal()唤醒“notFull上的等待线程”。此时，线程H就会被唤醒从而得以继续运行。

LinkedBlockingQueue

通过链表实现

LinkedBlockingQueue

1. LinkedBlockingQueue继承于AbstractQueue，它本质上是一个FIFO(先进先出)的队列。

2. LinkedBlockingQueue实现了BlockingQueue接口，它支持多线程并发。当多线程竞争同一个资源时，某线程获取到该资源之后，其它线程需要阻塞等待。

3. LinkedBlockingQueue是通过单链表实现的。 (01) head是链表的表头。取出数据时，都是从表头head处取出。 (02) last是链表的表尾。新增数据时，都是从表尾last处插入。 (03) count是链表的实际大小，即当前链表中包含的节点个数。 (04) capacity是列表的容量，它是在创建链表时指定的。 (05) putLock是插入锁，takeLock是取出锁；notEmpty是“非空条件”，notFull是“未满条件”。通过它们对链表进行并发控制。 LinkedBlockingQueue在实现“多线程对竞争资源的互斥访问”时，对于“插入”和“取出(删除)”操作分别使用了不同的锁。对于插入操作，通过“插入锁putLock”进行同步；对于取出操作，通过“取出锁takeLock”进行同步。此外，插入锁putLock和“非满条件notFull”相关联，取出锁takeLock和“非空条件notEmpty”相关联。通过notFull和notEmpty更细腻的控制锁。

LinkedBlockingDeque

ConcurrentLinkedQueue

集合辅助类

Collections

排序

自然排序或按照自定义比较器排序

搜索

二分搜索binarySearch

返回比较器

返回线程安全的结合

Collections.synchronizedxxx

Arrays

搜索

二分搜索binarySearch

判断

判断两个指定类型的数组是否相等

返回List

asList()

Collection接口

List接口（元素有序可重复）

子类

ArrayList

通过动态数组实现，每次扩容都是原来的3/2倍，数组是存储在一块连续的内存中

增删元素时,会创建新的数组,效率很低,不适合做大量的增删操作

可以通过索引的方式来访问元素,所以查找元素很方便

线程不安全

元素可为空且可重复

fail-fast

ConcurrentModificationException

默认容量：10

jdk1.6和jdk1.8的区别

主要区别在于1.6版本的在实例化时就把数组进行初始化了，而1.8版本的是在添加时进行初始化数组大小的

LinkedList

通过双向链表实现，头结点header,前指针，后指针，添加元素时在链表头添加，因为链表是通过指针方式查找元素故在内存中是不连续的内存块

双向循环链表,每一个元素都采用引用的方式来记住前后的元素

克服ArrayList增删元素效率低的问题而出现的，因为只需要改变引用即可，而数组则需要移动元素

线程不安全

元素可为空且可重复

fail-fast

Vector

通过数组实现

线程安全，通过关键字synchronize实现

元素可为空且可重复