【Java基础巩固系列】Java数据集合，List、Map、Set、JUC，应有尽有

亦凉 2023-06-27 11:19 8阅读 0赞

# 热门系列： #

*  ### [【Java基础巩固系列】Java内存溢出和内存泄漏][Java_Java] ###
 *  ### [【Java基础巩固系列】Java类初始化执行顺序][Java_Java 1] ###
 *  ### [【Java基础巩固系列】高级Java进阶之最全面技术架构思维导图][Java_Java 2] ###
 *  ### [【Java基础巩固系列】Java双亲委派机制理解][Java_Java 3] ###
 *  ###   [程序人生，精彩抢先看][Link 1] ###

--------------------

# **目录** #

1.前言

2.集合框架

3.集合接口

3.1Set和List的区别

4.常用集合实现类

4.1 ArrayList

4.2 LinkedList

4.3 HashMap

4.4 HashTable

4.5 ConcurrentHashMap

4.6 TreeMap

4.7 HashSet

5.常用的五种并发包

5.1 ConcurrentHashMap

5.2 CopyOnWriteArrayList

5.3 CopyOnWriteArraySet

5.4 ArrayBlockingQueue

5.5 LinkedBlockingQueue

6.总结

--------------------

# 1.前言 #

数据的存储，包含多种数据结构。但总体可分为四大类：线性表，散列，树以及图四大类。而我们java其实也有自己常用的“数据结构”，那就是集合。但java中的集合，底层实现也是有数组，链表，树等等数据结构来实现的。下面我们将针对常用的一些集合，进行一定深度的说明。

--------------------

# 2.集合框架 #

作为java开发，常用的集合肯定都了解一下。下面通过一张图，来列举一下java中的集合到底有哪些。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5_size_16_color_FFFFFF_t_70][]

Java 集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。

Collection是一个接口，是高度抽象出来的集合，它包含了集合的基本操作和属性。

Collection接口又有 3 种子类型，List、Set 和 Queue。

尽管 Map 不是集合，但是它们完全整合在集合中。Map 里存储的是键/值对。

--------------------

# 3.集合接口 #

<table> 
 <tbody> 
 <tr> 
 <th style="width:54px;"> 序号 </th> 
 <th>接口描述</th> 
 </tr> 
 <tr> 
 <td style="width:54px;">1</td> 
 <td>Collection 接口 Collection 是最基本的集合接口，一个 Collection 代表一组 Object，即 Collection 的元素, Java不提供直接继承自Collection的类，只提供继承于的子接口(如List和set)。 Collection 接口存储一组不唯一，无序的对象。 </td> 
 </tr> 
 <tr> 
 <td style="width:54px;">2</td> 
 <td>List 接口 List接口是一个有序的 Collection，使用此接口能够精确的控制每个元素插入的位置，能够通过索引(元素在List中位置，类似于数组的下标)来访问List中的元素，第一个元素的索引为 0，而且允许有相同的元素。 List 接口存储一组不唯一，有序（插入顺序）的对象。 </td> 
 </tr> 
 <tr> 
 <td style="width:54px;">3</td> 
 <td>Set Set 具有与 Collection 完全一样的接口，只是行为上不同，Set 不保存重复的元素。 Set 接口存储一组唯一，无序的对象。 </td> 
 </tr> 
 <tr> 
 <td style="width:54px;">4</td> 
 <td>SortedSet 继承于Set保存有序的集合。</td> 
 </tr> 
 <tr> 
 <td style="width:54px;">5</td> 
 <td>Map Map 接口存储一组键值对象，提供key（键）到value（值）的映射。 </td> 
 </tr> 
 <tr> 
 <td style="width:54px;">6</td> 
 <td>Map.Entry 描述在一个Map中的一个元素（键/值对）。是一个Map的内部类。</td> 
 </tr> 
 <tr> 
 <td style="width:54px;">7</td> 
 <td>SortedMap 继承于 Map，使 Key 保持在升序排列。</td> 
 </tr> 
 <tr> 
 <td style="width:54px;">8</td> 
 <td>Enumeration 这是一个传统的接口和定义的方法，通过它可以枚举（一次获得一个）对象集合中的元素。这个传统接口已被迭代器取代。</td> 
 </tr> 
 </tbody> 
</table>

## 3.1Set和List的区别 ##

*  1. Set 接口实例存储的是无序的，不重复的数据。List 接口实例存储的是有序的，可以重复的元素。
 *  2. Set检索效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
 *  3. List和数组类似，可以动态增长，根据实际存储的数据的长度自动增长List的长度。查找元素效率高，插入删除效率低，因为会引起其他元素位置改变 。

--------------------

# 4.常用集合实现类 #

## 4.1 ArrayList ##

ArrayList是List接口的可变数组的实现，底层是数组保存数据的。

数据结构如下：

![20200106154956251.png][]

特点：

*  **查询快（时间是01）， 增删改慢**
 *  **有序的，可重复，可为null**
 *  **线程不安全**

实现原理：

通过数组，增的时候要将数组扩容，复制一个新的数组然后在末尾添加一个新的元素；默认初始长度是10 扩容1.5倍+1。

在添加大量元素前，应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量，这可以减少递增式再分配的数量。

## 4.2 LinkedList ##

linkedList 是一个双向链表，没有初始化大小，也没有扩容的机制。 里面主要有head表头（包含Entry） 和size长度。

Entry该类是一个实体类、用来表示链表中的一个节点、他包括连接上一个节点的引用、连接下一个节点的引用、和节点的属性。

数据结构如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5_size_16_color_FFFFFF_t_70 1][]

每个节点Entry结构如下：

![20200106155231864.png][]

特点：

*  查询慢，增删改快
 *  线程不安全
 *  可以被当作堆栈、队列或双端队列进行操作（通过addFirst()，getFirst()，removeFirst()，removeLast()方法封装进出栈）

## 4.3 HashMap ##

在JDK1.8之前，HashMap采用数组+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

数据结构：

1.8之前：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5_size_16_color_FFFFFF_t_70 2][]

1.8之后：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5_size_16_color_FFFFFF_t_70 3][]

特点：

*  key和value都可以为null（key有且只有一个null值）
 *  线程不安全

底层原理：hashMap通过hashCode算法，将每个K-V的key值计算得到一个hash值，通过不同的hash值存放每一个键值对；而hash值相同时，则在数组当前节点通过链表，或是红黑树的形式存放hash值相同的键值对。hashMap初始化大小是 16 ，扩容因子默认0.75（可以指定初始化大小，和扩容因子） 。

扩容机制.(当前大小 和 当前容量 的比例超过了 扩容因子，就会扩容，扩容后大小为 一倍。例如：初始大小为 16 ，扩容因子 0.75 ，当容量为12的时候，比例已经是0.75 。触发扩容，扩容后的大小为 32。

为什么hashMap是非线程安全的？因为当hashmap扩容resize的时候在高并发的情况下reHash有可能会出现死循环（线程不安全，在并发插入元素的时候，有可能出现带环链表，让下一次操作出现死循环）

## 4.4 HashTable ##

Hashtable是基于哈希表的Map接口的同步实现，不允许使用null值和null键。底层使用数组实现，数组中每一项是个单链表，即数组和链表的结合体。

数据结构同hashMap的1.8之前的结构图一致，此处就不重复贴出了。

特点：

*  key和value都不能为null
 *  线程安全

底层原理：hashTable的存储原理同hashMap相似。而不同点在于hashTable的起始容量为11，而在扩容时，为原始容量\*2+1。

## 4.5 ConcurrentHashMap ##

ConcurrentHashMap是Java中的一个**线程安全且高效的HashMap实现**。所以其数据结构和内部实现原理，同HashMap大同小异，主要就是通过锁做了线程安全的实现。

而1.8之前，主要是使用的是Segment数组和分段锁技术实现线程安全处理。其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。主要内部结构如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5_size_16_color_FFFFFF_t_70 4][]

在1.8之后，锁的实现上做了很大改动。内部结构如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5_size_16_color_FFFFFF_t_70 5][]

其中抛弃了原有的 Segment 分段锁，而采用了 `CAS + synchronized` 来保证并发安全性。也将 1.7 中存放数据的 HashEntry 改为 Node，但作用都是相同的。

## 4.6 TreeMap ##

Map接口另一个重要的实现类TreeMap，TreeMap可以实现元素的自动排序。例如我们常用的签名中，对参数排序就可以用到此类。

TreeMap存储K-V键值对，通过红黑树（R-B tree）实现。而对于红黑树的特点及原理，此处不做讲解，有需要可自行了解。

TreeMap的内部结构如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5_size_16_color_FFFFFF_t_70 6][]

底层原理：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5_size_16_color_FFFFFF_t_70 7][]

## 4.7 HashSet ##

对于HashSet而言，它是基于HashMap实现的，HashSet底层使用HashMap来保存所有元素，因此HashSet 的实现比较简单，相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来完成。

特点：

*  存储唯一元素并允许空值
 *  非线程安全
 *  无序

### HashSet如何保持唯一性？ ###

> 当我们将一个对象放入一个HashSet时，它使用该对象的hashcode值来确定一个元素是否已经在该集合中。
> 
> 每个散列码值对应于某个块位置，该块位置可以包含计算出的散列值相同的各种元素。但是具有相同hashCode的两个对象可能不相等。
> 
> 因此，将使用equals（）方法比较同一存储桶中的对象。

HashSet的性能主要受两个参数影响 - 初始容量和负载因子。

将元素添加到集合的预期时间复杂度是O（1），在最坏的情况下（仅存在一个存储桶）可以降至O（n） - 因此，维护正确的HashSet容量至关重要。

一个重要的注意事项：从JDK 8开始，最坏的情况时间复杂度为O（log \* n）。不过hashSet的起始容量和负载因子都可以自定义

> Set<String> hashset = new HashSet<>();
> Set<String> hashset = new HashSet<>(20);
> Set<String> hashset = new HashSet<>(20, 0.5f);

--------------------

# 5.常用的五种并发包 #

*  ConcurrentHashMap
 *  CopyOnWriteArrayList
 *  CopyOnWriteArraySet
 *  ArrayBlockingQueue
 *  LinkedBlockingQueue

## 5.1 ConcurrentHashMap ##

**特点：**

> 1.  线程安全的HashMap的实现
> 2.  数据结构：一个指定个数的Segment数组，数组中的每一个元素Segment相当于一个HashTable（一个HashEntry\[\]）
> 3.  扩容的话，只需要扩自己的Segment而非整个table扩容
> 4.  key与value均不可以为null

**原理：**

ConcurrentHashMap基于concurrencyLevel划分出多个Segment来存储key-value，这样的话put的时候只锁住当前的Segment，可以避免put的时候锁住整个map，从而减少了并发时的阻塞现象。

而从map中获取元素，则：

> 1.  根据key获取key.hashCode的hash值
> 2.  根据hash值与找到相应的Segment
> 3.  根据hash值与Segment中的HashEntry的容量-1按位与获取HashEntry的index
> 4.  遍历整个HashEntry\[index\]链表，找出hash和key与给定参数相等的HashEntry，例如查找元素e： 
> 
>            如没找到e，返回null；
> 
>            如找到e，获取e.value；
> 
>            如果e.value!=null，直接返回；
> 
>            如果e.value==null,则先加锁，等并发的put操作将value设置成功后，再返回value值；

对于get操作而言，基本没有锁，只有当找到了e且e.value等于null,有可能是当下的这个HashEntry刚刚被创建，value属性还没有设置成功，这时候我们读到是该HashEntry的value的默认值null,所以这里加锁，等待put结束后，返回value值

*  加锁情况（分段锁）：
    
     *  get中找到了hash与key都与指定参数相同的HashEntry，但是value==null的情况
     *  size()：三次尝试后，还未成功，遍历所有Segment，分别加锁（即建立全局锁）

## 5.2 CopyOnWriteArrayList ##

*  线程安全且在读操作时无锁的ArrayList
 *  采用的模式就是"CopyOnWrite"（即写操作-->包括增加、删除，使用复制完成）
 *  底层数据结构是一个Object\[\]，初始容量为0，之后每增加一个元素，容量+1，数组复制一遍
 *  遍历的只是全局数组的一个副本，即使全局数组发生了增删改变化，副本也不会变化，所以不会发生并发异常。但是，可能在遍历的过程中读到一些刚刚被删除的对象
 *  增删改上锁、读不上锁
 *  读多写少且脏数据影响不大的并发情况下，选择CopyOnWriteArrayList

## 5.3 CopyOnWriteArraySet ##

*  基于CopyOnWriteArrayList，不添加重复元素

## 5.4 ArrayBlockingQueue ##

**特点：**

> 基于数组、先进先出、线程安全，可实现指定时间的阻塞读写，并且容量可以限制
> 
> 组成：一个对象数组+1把锁ReentrantLock+2个条件Condition

**三种入队对比：**

> offer(E e)：如果队列没满，立即返回true； 如果队列满了，立即返回false-->不阻塞
> 
> put(E e)：如果队列满了，一直阻塞，直到数组不满了或者线程被中断-->阻塞
> 
> offer(E e, long timeout, TimeUnit unit)：在队尾插入一个元素,，如果数组已满，则进入等待，直到出现以下三种情况：
> 
> 1.  阻塞被唤醒
> 2.  当前线程被中断
> 3.  等待时间超时

**三种出对对比：**

> poll()：如果没有元素，直接返回null；如果有元素，出队
> 
> take()：如果队列空了，一直阻塞，直到数组不为空或者线程被中断-->阻塞
> 
> poll(long timeout, TimeUnit unit)：如果数组不空，出队；如果数组已空且已经超时，返回null；如果数组已空且时间未超时，则进入等待，直到出现以下三种情况：
> 
> 1.  被唤醒
> 2.  当前线程被中断
> 3.  等待时间超时

**需要注意的是，**数组是一个必须指定长度的数组，在整个过程中，数组的长度不变，队头随着出入队操作一直循环后移。

锁的形式分为公平与非公平两种；另外，因为操作数组，且不需要扩容，所以性能很高。

## 5.5 LinkedBlockingQueue ##

*  基于链表实现，读写各用一把锁，在高并发读写操作都多的情况下，性能优于ArrayBlockingQueue
 *  组成一个链表+两把锁+两个条件
 *  默认容量为整数最大值，可以看做没有容量限制
 *  三种入队与三种出队与上边完全一样，只是由于LinkedBlockingQueue的的容量无限，在入队过程中，没有阻塞等待

--------------------

# 6.总结 #

本章有一部分是我的个人笔记，也参考了部分资料，将我们开发过程中常用的一些集合框架的知识点整理出来。在加深自己的理解同时，也是对别人的一种帮助。学无止境，Fighting。

> ### 本博客皆为学习、分享、探讨为本，欢迎各位朋友评论、点赞、收藏、关注，一起加油！ ###

![20201028145431331.gif][]

[Java_Java]: https://blog.csdn.net/yy339452689/article/details/103991120
[Java_Java 1]: https://blog.csdn.net/yy339452689/article/details/104014732
[Java_Java 2]: https://blog.csdn.net/yy339452689/article/details/105678083
[Java_Java 3]: https://blog.csdn.net/yy339452689/article/details/106478514
[Link 1]: https://blog.csdn.net/yy339452689/article/details/109314083
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200106144647473.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5,size_16,color_FFFFFF,t_70
[20200106154956251.png]: https://img-blog.csdnimg.cn/20200106154956251.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200106155118947.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5,size_16,color_FFFFFF,t_70
[20200106155231864.png]: https://img-blog.csdnimg.cn/20200106155231864.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020010616451294.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200106164538794.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200106175107981.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200106175411616.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200106181635164.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200106181759116.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l5MzM5NDUyNjg5,size_16,color_FFFFFF,t_70
[20201028145431331.gif]: https://img-blog.csdnimg.cn/20201028145431331.gif