高清图解 28 个高并发之数据结构 / 数据结构场景匹配技巧分析 (高并发精通篇一)
Java 集合以 ArrayList、LinkedList、HashSet、TreeSet 和 HashMap 等组件为核心,构筑了强大而灵活的数据结构体系。这些组件精心设计以满足不同的性能和功能需求,如 ArrayList 的动态数组支持快速随机访问,而 LinkedList 的双向链表结构则擅长于频繁的插入和删除操作。HashSet 基于哈希表提供高效的元素查找,TreeSet 则通过红黑树维持元素排序。对于多线程环境,CopyOnWriteArraySet 和 ConcurrentHashMap 等并发集合保证了线程安全,同时优化了读写性能。这些设计精妙的组件,不仅提升了数据处理的效率,也简化了复杂问题的解决方案,了解他的设计就掌握了他的原理,本篇注重设计。
肖哥弹架构 跟大家“弹弹” 高并发锁, 关注公号回复 'mvcc' 获得手写数据库事务代码
欢迎 点赞,关注,评论。
关注公号 Solomon 肖哥弹架构获取更多精彩内容 SS
历史热点文章
1、JDK 集合数据结构范围
1.1. 列表(List)
ArrayList: 基于动态数组实现,支持快速随机访问。
LinkedList: 基于双向链表实现,适合频繁的插入和删除操作。
CopyOnWriteArrayList: 线程安全的变体,写操作时复制数组。
1.2. 集合(Set)
HashSet: 基于 HashMap 实现,保证元素唯一性。
LinkedHashSet: 哈希表和链表实现,维护元素插入顺序。
TreeSet: 基于红黑树,元素处于排序状态。
CopyOnWriteArraySet: 线程安全的变体,写操作时复制数组。
1.3. 队列(Queue)
LinkedListQueue (作为队列使用时): 支持先进先出(FIFO)。
ArrayDeque: 双端队列,支持快速插入和删除。
PriorityQueue: 支持优先级排序的队列。
ConcurrentLinkedQueue: 线程安全的无界队列。
BlockingQueue: 支持阻塞操作的队列接口,具体实现包括:
ArrayBlockingQueue: 有界阻塞队列。
LinkedBlockingQueue: 基于链表结构的阻塞队列。
PriorityBlockingQueue: 具有优先级的阻塞队列。
SynchronousQueue: 不存储元素的阻塞队列,主要用于任务窃取。
1.4. 双端队列(Deque)
ArrayDeque: 基于动态数组,实现双向队列。
LinkedList (作为双端队列使用时): 基于链表,实现双向队列。
1.5. 映射(Map)
HashMap: 基于哈希表,存储键值对。
LinkedHashMap: 哈希表加链表,维护插入顺序。
TreeMap: 基于红黑树,键处于排序状态。
Hashtable: 古老的 Map 实现,线程安全。
ConcurrentHashMap: 线程安全的 HashMap 实现。
ConcurrentSkipListMap: 线程安全的 TreeMap 实现。
IdentityHashMap: 使用 == 比较键的身份,而不是使用 equals() 方法。
WeakHashMap: 键是弱引用,适合缓存使用。
1.6. 其他
Vector: 古老的动态数组实现,线程安全。
Stack: 古老的栈实现,可以使用
Vector
或Deque
实现。Properties: 用于处理配置文件的集合类。
2、集合数据结构设计与分析
2.1 ArrayList
ArrayList
是 Java 集合框架中的一个非常核心的类,实现了 List
接口。以下是 ArrayList
的设计:
设计思考:
需求场景:
在许多编程任务中,需要一个能够动态增长和收缩的数组。例如,在实现数据集合、缓冲区管理、实现其他数据结构(如栈、队列)等场景中,动态数组是非常有用的。
现有技术局限性:
传统的数组类型在 Java 中是固定长度的,一旦创建,其大小不能改变,这限制了其在需要动态大小管理时的使用。
技术融合:
ArrayList
融合了动态数组的概念,提供了一个能够根据需要自动调整大小的数组。设计理念:
ArrayList
提供了一个能够根据添加元素的数量动态增长的数组,同时保持了随机访问的能力,使其在执行索引位置的查找时非常高效。实现方式:
ArrayList
内部使用一个可变大小的数组(默认为空,随着元素添加自动扩容)来存储元素,当数组容量不足以容纳更多元素时,会自动创建一个更大的新数组,并将旧数组中的元素复制到新数组中。
2.1.1 数据结构
图说明:
ArrayList:
Java 集合框架中的一个类,实现了
List
接口。Object[] elementData:
ArrayList
内部使用一个动态数组来存储元素,这个数组的类型是Object[]
,可以存储任何类型的对象。当数组容量不足以存储更多元素时,
ArrayList
会自动进行扩容,通常是将数组大小增加到原来的 1.5 倍。int size:
表示
ArrayList
中实际存储的元素数量。size
与elementData
数组的length
属性不同,length
表示数组的总容量,而size
表示当前存储的元素个数。
2.1.2 执行流程
图说明:
初始化 ArrayList:
创建一个空的
ArrayList
或指定初始容量的ArrayList
。检查容量:
在添加元素前,检查当前数组容量是否足够。
添加元素:
尝试将新元素添加到
ArrayList
。容量不足:
如果当前容量不足以容纳新元素,进入扩容流程。
扩容:
创建一个新的数组,容量通常是原数组的 1.5 倍。
复制旧数组到新数组:
将旧数组中的所有元素复制到新数组中。
增加新元素:
在新数组中插入新元素。
获取元素:
根据索引获取元素。
索引检查:
检查索引是否在有效范围内。
返回元素:
返回指定索引处的元素。
删除元素:
删除
ArrayList
中的指定元素。移除指定索引元素:
将指定索引处的元素移除。
数组元素向前移动:
将移除元素之后的元素向前移动一位,填补空位。
2.2 LinkedList
LinkedList
在 Java 中是基于双向链表实现的,它包含多个节点,每个节点都包含数据和两个引用,分别指向前一个节点和后一个节点。以下是 LinkedList
的设计:
设计思考:
需求场景:
在许多编程任务中,需要一个可以快速进行插入和删除操作的动态数组。例如,在实现栈、队列、双向队列等数据结构时,这些操作非常常见。
现有技术局限性:
ArrayList
提供了快速的随机访问能力,但在进行插入和删除操作时,可能需要移动数组中的大量元素,导致效率低下。Vector
类似于ArrayList
,但它是线程安全的,但使用synchronized
进行同步,导致并发性能较差。技术融合:
LinkedList
结合了链表的插入和删除效率高的特点,并提供了双向链表的实现,允许从两端快速地添加或移除元素。设计理念:
LinkedList
通过使用链表结构,可以有效地进行插入和删除操作,因为这些操作仅需要改变节点的指针,而不需要移动整个数组。它还实现了
List
接口,提供了与ArrayList
相同的接口,但具有不同的性能特性。实现方式:
LinkedList
由一系列Node
对象组成,每个Node
包含数据和两个引用(previous
和next
),分别指向前一个和后一个节点。
2.2.1 数据结构
以下是 LinkedList
数据结构的主要特点:
链式存储:元素在内存中不是连续存储的,而是通过指针(引用)连接起来的。
节点结构:每个节点至少包含两部分信息,一个是存储数据的元素,另一个是指向同链表中下一个节点的引用。在双向链表中,还会有一个指向前一个节点的引用。
动态大小:
LinkedList
的大小是动态的,可以根据需要随时插入或删除节点。允许空链表:可以创建一个不包含任何节点的空链表。
插入和删除效率高:在链表的任意位置插入或删除节点的操作时间复杂度为 O(1),因为这些操作只涉及到节点的引用的改动。
访问元素效率低:访问特定索引位置的元素需要从头节点开始遍历链表,时间复杂度为 O(n)。
没有空间浪费:与数组不同,链表不需要预先分配固定大小的存储空间。
有序性:链表中的节点按照它们被插入的顺序保持有序。
可以实现为双向或循环链表:标准的
LinkedList
实现可以是双向的,也可以是循环的(尾节点指向头节点)。
2.2.1 执行流程
图说明:
初始化 LinkedList:
创建一个空的
LinkedList
实例。添加元素:
将新元素添加到
LinkedList
。删除元素:
从
LinkedList
删除指定的元素。访问元素:
根据索引访问
LinkedList
中的元素。遍历 LinkedList:
通过节点间的链接顺序遍历整个
LinkedList
。检查边界条件:
在执行索引相关操作前,检查索引是否在有效范围内。
获取节点:
获取指定索引处的节点。
更新节点指针:
在添加或删除元素时,更新节点间的指针。
返回节点数据:
返回指定节点的数据。
LinkedList 节点:
LinkedList
由一系列节点组成,每个节点包含前一个节点、后一个节点和节点数据。Node prev:
节点中保存的对前一个节点的引用。
Node next:
节点中保存的对后一个节点的引用。
Node data:
节点中保存的数据。
2.3 CopyOnWriteArrayList
CopyOnWriteArrayList
在 Java 中是一个线程安全的变体数组列表,其特点是在修改(写操作)时通过复制整个底层数组来实现,以此保证读操作的线程安全和高性能。以下是 CopyOnWriteArrayList
的设计:
设计思考:
需求场景:
在多线程环境中,读操作远比写操作频繁,且对数据的实时性要求不是非常高的场景。例如,缓存系统、实时数据的订阅发布模型等。
现有技术局限性:
传统的线程安全实现,如
Vector
或通过synchronized
同步代码块或方法,可能会因为写操作导致的线程阻塞,严重影响并发性能。技术融合:
CopyOnWriteArrayList
采用了写时复制(Copy-On-Write)的策略,当进行写操作(添加、删除等)时,先复制整个数组,然后在新数组上进行操作,而读操作则直接作用于原数组,从而提高了读操作的性能。设计理念:
利用了读操作远多于写操作的特性,通过分离读和写操作,使得读操作无需加锁,从而提高了并发读的性能。
实现方式:
内部使用一个数组来存储元素,所有写操作都会创建一个新的数组,并将修改应用于新数组,然后原子性地将内部数组引用指向新数组。
2.3.1 数据结构
图说明:
CopyOnWriteArrayList:
表示
CopyOnWriteArrayList
的实例。Object[] array:
CopyOnWriteArrayList
内部使用的一个数组array
来存储元素。这是原始数组,所有读操作都访问这个数组。Object[] newArray:
写操作时创建的新数组。当写操作发生时,这个数组是原始数组的一个深拷贝。
写操作:
包括添加、删除或修改元素。写操作不是在原始数组上进行,而是在新数组上进行。
工作原理:
读操作:
多个读线程可以同时访问和遍历
array
,因为数组是不可变的。写操作:
当写操作发生时(如添加、删除或修改元素),写线程首先会创建原始
array
的一个副本newArray
。写线程在
newArray
上进行添加、删除或修改操作。写操作完成后,写线程会原子性地将
CopyOnWriteArrayList
的内部数组引用指向newArray
。数据一致性:
在写操作进行时,读线程仍然可以访问旧的内部数组
array
,从而保证了数据的一致性。
2.3.2 执行流程
图说明:
初始化 CopyOnWriteArrayList:
创建一个空的
CopyOnWriteArrayList
实例。内部数组 array:
CopyOnWriteArrayList
内部使用一个数组来存储元素。读操作:
直接读取内部数组的元素,是线程安全的,因为内部数组不可变。
写操作:
包括添加、删除和修改元素,需要创建内部数组的一个新副本。
复制数组:
在执行写操作前,复制内部数组,以保证新元素的添加不会影响读操作。
添加元素:
向
CopyOnWriteArrayList
添加新元素。删除元素:
从
CopyOnWriteArrayList
删除元素。修改元素:
修改
CopyOnWriteArrayList
中的元素。数组拷贝:
创建内部数组的一个新副本,并在新副本上执行写操作。
2.4 HashSet
HashSet
是 Java 集合框架中的一个基本成员,它是 java.util
包下的一个非常常用的集合类。以下是 HashSet
的设计:
设计思考:
需求场景:
在很多应用场景中,需要存储不重复的元素,并且需要快速地添加、删除和查找元素。
例如,在处理配置选项、用户权限、邮件地址列表等场景时,确保元素的唯一性是非常重要的。
现有技术局限性:
ArrayList
和LinkedList
虽然可以存储元素,但它们需要线性时间来查找元素,且不保证元素的唯一性。技术融合:
HashSet
基于HashMap
实现,它结合了哈希表的快速查找特性来提供常数时间复杂度的添加、删除和查找操作,同时保证了元素的唯一性。设计理念:
HashSet
提供了一个不允许重复元素的数据结构,它使用哈希表的键来存储元素,而不关心值。这种设计使得
HashSet
在保证元素唯一性的同时,提供了高效的操作性能。实现方式:
HashSet
的每个元素都作为HashMap
的一个键存储,而对应的值是一个固定的对象(通常是一个名为PRESENT
的私有静态对象)。
2.4.1 数据结构
图说明:
HashSet:
表示
HashSet
类的实例,用于存储不重复的元素。HashMap:
HashSet
的内部实现基于HashMap
。数组 (Buckets) :
HashMap
使用一个数组来存储桶(Buckets),桶是用于存储Entry
对象的容器。索引 1, 索引 2, 索引 3:
表示数组中的具体索引位置,每个索引对应一个桶。
Entry (链表/红黑树) :
每个桶可以包含多个
Entry
对象,它们通过链表或红黑树形式连接。链表 Entry:
在哈希冲突较少的情况下,
Entry
对象通过链表连接。红黑树 Entry:
当链表长度超过阈值时,链表可能会被转换成红黑树以提高搜索效率。
2.4.2 执行流程
图说明:
创建 HashSet 实例:
初始化
HashSet
对象。添加元素:
将元素添加到
HashSet
。计算元素的 hashCode:
调用元素的
hashCode()
方法计算其哈希码。确定数组索引位置:
根据哈希码和数组长度确定数组索引位置。
处理哈希冲突:
如果索引位置已有元素,处理哈希冲突。
元素添加至链表/红黑树:
将新元素添加至对应索引的链表或红黑树中。
删除元素:
从
HashSet
删除元素。计算元素的 hashCode:
调用元素的
hashCode()
方法计算其哈希码。确定数组索引位置:
根据哈希码和数组长度确定数组索引位置。
找到对应的哈希桶:
定位到数组中对应的哈希桶。
从链表/红黑树中删除元素:
从对应索引的链表或红黑树中删除元素。
遍历 HashSet:
遍历
HashSet
中的所有元素。获取数组:
获取
HashSet
内部的数组。遍历每个桶:
遍历数组的每个桶。
遍历链表/红黑树:
遍历桶内的链表或红黑树中的所有元素。
2.5 LinkedHashSet
LinkedHashSet
是 Java 集合框架中的一个成员,它结合了 HashSet
的快速查找特性和 LinkedList
的插入顺序保持功能。以下是 LinkedHashSet
的设计:
设计思考:
需求场景:
在很多应用场景中,需要快速地插入、删除和查找元素,同时也需要保持元素的插入顺序。
例如,在处理用户会话、缓存实现、任务调度等场景时,保持元素的添加顺序是非常重要的。
现有技术局限性:
HashSet
提供了常数时间的添加、删除和查找性能,但它不保持元素的插入顺序。TreeSet
保持了元素的排序顺序,但不是插入顺序,且它的性能不如HashSet
。ArrayList
和LinkedList
保持了插入顺序,但它们的查找性能为线性时间复杂度。技术融合:
为了结合
HashSet
的快速查找能力和LinkedList
的插入顺序保持能力,LinkedHashSet
应运而生。设计理念:
LinkedHashSet
底层使用HashMap
来存储元素,保证了快速的查找性能。同时,它在每个
HashMap
的条目上使用一个双向链表来维护元素的插入顺序。实现方式:
LinkedHashSet
继承自HashSet
,但重写了add
、iterator
等方法,以维护插入顺序。它在内部维护了与
HashMap
条目关联的双向链表的节点,这些节点链接了具有相同哈希值但插入顺序不同的元素。
2.5.1 数据结构
图说明:
LinkedHashSet:
表示
LinkedHashSet
类的实例,它继承自HashSet
并维护元素的插入顺序。HashMap:
LinkedHashSet
的实现基于HashMap
,用来存储集合中的元素。数组 (Buckets) :
HashMap
使用一个数组来存储桶(Buckets),桶是用于存储Entry
对象的容器。哈希桶:
每个桶内部使用链表来解决哈希冲突。
链表 Entry:
每个桶包含多个
Entry
对象,它们通过链表连接。红黑树 Entry:
当链表长度超过阈值时,链表可能会被转换成红黑树以提高搜索效率。
链表 节点 1 和 链表 节点 2:
表示链表中的节点,每个节点存储着集合中的一个元素,并指向前一个和后一个节点,形成双向链表。
元素:
存储在
LinkedHashSet
中的最终数据。
2.5.2 执行流程
图说明:
创建 LinkedHashSet 实例:
初始化
LinkedHashSet
对象。添加元素:
将元素添加到
LinkedHashSet
。计算元素的 hashCode:
调用元素的
hashCode()
方法计算其哈希码。确定数组索引位置:
根据哈希码和数组长度确定数组索引位置。
找到对应的哈希桶:
定位到数组中对应的哈希桶。
检查哈希桶中的链表/红黑树:
检查哈希桶中是否已有链表或红黑树结构。
处理哈希冲突:
如果桶中已有元素,处理哈希冲突。
元素添加至链表/红黑树:
将新元素添加至对应索引的链表或红黑树中。
删除元素:
从
LinkedHashSet
删除元素。重新计算元素的 hashCode:
调用元素的
hashCode()
方法计算其哈希码。确定删除元素的数组索引位置:
根据哈希码和数组长度确定数组索引位置。
找到删除元素的哈希桶:
定位到数组中对应的哈希桶。
从链表/红黑树中删除元素:
从对应索引的链表或红黑树中删除元素。
遍历 LinkedHashSet:
遍历
LinkedHashSet
中的所有元素。获取数组:
获取
LinkedHashSet
内部的数组。遍历每个桶:
遍历数组的每个桶。
遍历链表/红黑树:
遍历桶内的链表或红黑树中的所有元素。
读取元素:
读取链表或红黑树中的元素。
2.6 TreeSet
TreeSet
是 Java 集合框架中的一个有序集合类,实现了 Set
接口。以下是 TreeSet
的设计:
设计思考:
需求场景:
在许多编程任务中,需要存储不重复的元素,并且这些元素需要保持一定的顺序,例如,自然排序或自定义排序顺序。
例如,在处理需要排序的配置选项、用户权限、需要按顺序处理的任务列表等场景时,元素的排序顺序是非常重要的。
现有技术局限性:
HashSet
提供了非常快的查找、添加和删除操作,但它不保证元素的任何特定顺序。ArrayList
和LinkedList
可以保持插入顺序,但查找操作需要线性时间。技术融合:
TreeSet
结合了HashSet
的快速查找特性和ArrayList
/LinkedList
的元素顺序保持功能,但通过使用红黑树(一种自平衡的二叉搜索树)实现,提供了有序的元素集合。设计理念:
TreeSet
提供了一个不允许重复元素的数据结构,同时保证了元素处于排序状态,可以进行有效的范围查询和排序操作。实现方式:
TreeSet
内部使用TreeMap
的实例来存储元素,其中元素作为键,值是一个固定的虚拟对象(如PRESENT
),从而保证了元素的唯一性。
2.6.1 数据结构
图说明:
TreeSet:
表示
TreeSet
类的实例,它实现了Set
接口,并保证元素处于排序状态。TreeMap:
TreeSet
基于TreeMap
实现,其中元素作为键存储,而不关心值。红黑树:
TreeMap
的底层数据结构是一个红黑树,它是一个自平衡的二叉搜索树。根节点:
红黑树的根节点,是树的入口。
左子节点和右子节点:
表示红黑树节点的子节点。
元素 A, 元素 B, 元素 C:
实际存储在
TreeSet
中的数据。
2.6.2 执行流程
图说明:
添加元素:
计算元素的自然排序:根据元素的自然顺序或提供的 Comparator 计算排序。
构建红黑树:TreeSet 基于红黑树数据结构,确保元素处于排序状态。
确定插入位置:在红黑树中找到元素的插入位置。
插入元素到红黑树:将元素插入到红黑树中。
删除元素:
计算元素的自然排序:根据元素的自然顺序或提供的 Comparator 计算排序。
查找红黑树:在红黑树中查找要删除的元素。
删除元素从红黑树:从红黑树中删除元素。
遍历 TreeSet:
获取红黑树根节点:获取红黑树的根节点,开始遍历。
遍历红黑树节点:遍历红黑树的每个节点。
读取元素:从红黑树的节点中读取元素。
2.7 CopyOnWriteArraySet
CopyOnWriteArraySet
是 Java 并发包 java.util.concurrent
中的一个集合类,它是 CopyOnWriteArrayList
的一个变体,用于维护一个线程安全的、动态的元素集合。以下是 CopyOnWriteArraySet
的设计:
设计思考:
需求场景:
在多线程环境中,读操作频繁而写操作相对较少的场景,如缓存、实时数据集、事件监听器集合等。
现有技术局限性:
传统的线程安全集合,如
Collections.synchronizedSet
或Hashtable
,在读多写少的场景下可能因为写操作导致的线程阻塞,影响性能。技术融合:
CopyOnWriteArraySet
采用了写时复制(Copy-On-Write)的策略,在读操作远多于写操作的情况下,提高了读操作的性能。设计理念:
CopyOnWriteArraySet
利用了读操作远多于写操作的特点,在读操作时不需要加锁,从而提高了并发读的性能。实现方式:
内部使用
CopyOnWriteArrayList
存储元素,所有写操作(添加、删除等)都会创建一个新的数组副本,然后对新数组进行修改,最后原子性地将内部数组引用指向新数组。
2.7.1 数据结构
图说明
CopyOnWriteArraySet:表示 CopyOnWriteArraySet 类的实例,它提供了线程安全的 Set 集合功能。
CopyOnWriteArrayList:CopyOnWriteArraySet 基于 CopyOnWriteArrayList 实现,后者是线程安全的 ArrayList 实现。
内部数组:CopyOnWriteArrayList 初始的内部数组,用于存储集合中的元素。
内部数组副本:当执行写操作(如添加、删除)时,CopyOnWriteArrayList 创建内部数组的一个副本。
新内部数组:写操作完成后,CopyOnWriteArrayList 将内部数组引用指向新的数组副本。
元素 1、元素 2、元素 n:表示存储在 CopyOnWriteArraySet 中的实际数据。
2.7.1 执行流程
编辑
图说明
创建 CopyOnWriteArraySet 实例:初始化 CopyOnWriteArraySet 对象。
添加元素:将元素添加到 CopyOnWriteArraySet。
复制旧内部数组:为了添加元素,先复制当前的内部数组。
修改新内部数组副本:在数组的副本上添加元素。
将新内部数组副本设置为当前:将修改后的数组副本设置为当前数组,完成添加操作。
删除元素:从 CopyOnWriteArraySet 删除元素。
复制旧内部数组:为了删除元素,先复制当前的内部数组。
修改新内部数组副本:在数组的副本上删除元素。
将新内部数组副本设置为当前:将修改后的数组副本设置为当前数组,完成删除操作。
遍历 CopyOnWriteArraySet:遍历 CopyOnWriteArraySet 中的所有元素。
读取当前内部数组:读取当前的内部数组,进行遍历操作。
其他内容在第二篇文章《高清图解 28 个高并发之数据结构/数据结构场景匹配技巧分析(高并发精通篇二)》中。。。
版权声明: 本文为 InfoQ 作者【肖哥弹架构】的原创文章。
原文链接:【http://xie.infoq.cn/article/bd76f0a5838cb5daa17581c12】。文章转载请联系作者。
评论