四.java中的集合框架有哪些？他们之间有什么区别？

谁借莪１个温暖的怀抱￠ 2023-10-10 17:11 70阅读 0赞

**目录**

一、 集合是什么

二、集合的两种类型（collection、map）

一、Collection

一.List

————一、ArrayList

————二、LinkedList

————三、Vector（线程安全）

————四、CopyOnWriteArrayList（1.5后引入，线程安全）

二、Set

————一、HashSet

————二、LinkedHashSet

————三、TreeSet(底层是红黑树)

二、Map，存储键/值对映射。

一、HashMap

二、TreeMap

三、HashTable（线程安全）

四、ConcurrentHashMap（线程安全）

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

## 一、 集合是什么 ##

集合类主要是对常见的数据结构进行完整的实现包装，然后提供了一系列的接口和实现子类。依次来帮助用户减少数据结构所带来的开发困难。所有的类都继承`Object`，集合类也是。

## **二、集合的两种类型（collection、map）** ##

###    一、`Collection` ###

``集合（`Collection`），存储一个元素集合，实现了lterable,支持迭代，主要有List和Set两类。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bkAGkAYM-1647002825415)(E:\\Typora笔记\\java笔记\\img\\image-20220221154516785.png)\]][img-bkAGkAYM-1647002825415_E_Typora_java_img_image-20220221154516785.png]

#### 一.List ####

**List集合的特点：**

*  元素允许重复
 *  各元素的顺序就是插入的顺序
 *  可以存放`null`值

**实现类有哪些：**

*  `ArrayList`：数组实现，查询快，增删慢，轻量级；(线程不安全)
 *  `LinkedList`：双向链表实现，增删快，查询慢 (线程不安全)
 *  `Vector`：数组实现，重量级 (线程安全、使用少)

#### ————一、ArrayList ####

**底层采用数组实现，查询速度快，增删速度慢的特点**

**实现了哪些接口：**

1.  List接口： 得到了List接口框架基础功能。
2.  RandomAccess接口： 获得了快速随机访问存储元素的功能，
3.  Cloneable： 得到了clone()方法，可以实现克隆功能；
4.  Serializable： 表示可以被序列化，通过序列化去传输，典型的应用就是hessian协议

**扩容机制：**

1.  初始化默认值是10
2.  如果数组的长度小于需要的最小容量自动化扩容
3.  扩容到原来的1.5倍(数组copyof复制的方法)（navite 方法由C/C++实现）

**操作特点：**

1.  指定容量为0时，返回该空数组
2.  可以插入到指定的位置
3.  尝试容量+1会不会满足我们的需求，不浪费资源
4.  删除元素然后向左移动
5.  删除元素时不会减少容量，若希望减少容量则调用trimToSize()
6.  它不是线程安全的。它能存放null值

#### ————二、LinkedList ####

**底层层通过链表来实现的，元素不断增加向链表的后端增加节点。linkedList是一个双向链表，每一个节点都拥有指向后节点的引用。想比较于ArrayList来说，LinkedList查询效率低，增删速度快。**

在LinkedList中，内部类Node对象最为重要，它组成了LinkedList集合的整个链表，分别指向上一个点、下一个结点，存储着集合中的元素。成员变量中，first表明是头结点，last表明是尾结点

**实现了哪些接口：**

继承了AbstractSequentialList，实现了List，Deque，cloneable，Serializable接口

**add增加操作**

1.  将添加的元素转换为LinkedList的Node对象节点
2.  增加该Node节点的前后引用，即该Node节点的prev、next属性，让其分别指向哪一个节点）。
3.  修改该Node节点的前后Node节点中pre/next属性，使其指向该节点。

**remove操作**

删除元素实际就是用equals去比较里面有没有这个元素

#### ————三、Vector（线程安全） ####

和ArrayList基本相同，有以下不同

> 1.  线程安全(加了synchronized)
> 2.  扩容机制不同，是1倍

#### ————四、CopyOnWriteArrayList（1.5后引入，线程安全） ####

底层跟ArrayList一样采用数组的方式，实现的接口跟ArrayList一样

删除修改元素原理和添加元素差不多，操作时都需要进行加锁，而读操作不会加锁

不存在扩容的概念，每次都会复制一个副本来操作

大面积复制数组，性能差

**两个主要变量**

1.  **ReentrantLock**： 独占锁，多线程运行的情况下，只有一个线程会获得这个锁，只有释放锁后其他线程才能获得。
2.  **array接口**： 存放数据的数组，关键是被volatile修饰了，被volatile修饰，就保证了可见性，也就是一个线程修改后，其他线程立即可见。

**add操作步骤：**

1.  获得独占锁，将添加功能加锁
2.  获取原来的数组，并得到其长度
3.  创建一个长度为原来数组长度+1的数组，并拷贝原来的元素给新数组
4.  追加元素到新数组末尾
5.  指向新数组
6.  释放锁
7.  每次修改都会拷贝一个新的资源去修改

#### 二、Set ####

set集合不能包含重复元素，存储是无序的。

**特点：**

1.  set提供了HashCode和equals方法，所以set支持比较
2.  set允许存储一个null值，并且不为空。
3.  主要实现有HashSet，Treeset，LinkedHashSet
4.  不等于随机性，是根据Hash值来排序的

####    ————一、HashSet ####

**线程不安全，可以存储null值。底层使用hashmap来保存元素。**

**注意事项：**

向set中添加数据，其所在类一定要重写hashCode和equals。（hash碰撞）  
如果只重写equals而不重写hashcode，则会调用object类下的hashcode，他是一个本地方法，会随机产生一个哈希值，不经过equals去比较。

**Hash添加add：**

1.  调用元素的hashcode算法，计算元素的哈希值，hash通过计算出在hashset底层数组中的存放位置(索引位置)
2.  哈希值存在数据就用链表的形式来存储
3.  hash值不相同就添加成功，如果hash相同，进而需要调用equals方法来判断元素是否存在。

**扩容机制**

1.  初始化容量16
2.  如果使用率超过0.75
3.  会扩容到原来的2倍

#### ————二、LinkedHashSet ####

**  继承于HashSet，可以按照添加的顺序便利(双向链表)记录此数据前一个和后一个数据。底层存储元素使用的LinkedHashMap。**

#### ————三、TreeSet(底层是红黑树) ####

**特点：**

1.  可以按照添加对象的指定属性，进行排序。
2.  不允许存在null值

**注意事项：**

向TreeSet中添加的数据，要求是相同类的对象。不同的类无法进行比较

**排序方式：**

自然排序(实现Comparable接口)和定制排序(Comparator)  
Comparator：实现接口，然后重写compareTo方法

### 二、`Map`，存储键/值对映射。 ###

**由`key-value`的方式组成的集合，同时没有继承`Collection`。实现map的有`HashMap`，`TreeMap`，`HashTable`。**

![在这里插入图片描述][2fb92925c16f4ba2b3071d1ccadbc38b.png]

#### 一、HashMap ####

**特点：**

key可以为null值(只能一个null)，value也可以为null

**底层实现方式：**

1.  以hash表实现的，内部定义了一个hash数组，通过计算找索引去存储。
2.  底部是数组+链表/红黑树
3.  转化为红黑树前会判断链表大于8但是数组长度小于64，会进行数组扩容不会转为红黑树。（treeifyBin方法）

**扩容机制：**

1.  当链表大于8个时候会变成红黑树，初始容量是16，默认加载因子是0.75
2.  扩容为原来容量的2倍，并将原有的数据复制过来

**hash长度为什么是2的整数次幂：**

为了加快哈希计算以及减少哈希冲突。

**红黑树和Hash值计算：**

**红黑树：**

红黑树是进行左旋，有旋，变色这些操作保持平衡的，  
根节点为黑色，叶子节点黑色且为null  
左旋：逆时针旋转两个节点，让⼀个节点被其右⼦节点取代，⽽该节点成为右⼦节点的左⼦节点  
右旋：顺时针旋转两个节点，让⼀个节点被其左⼦节点取代，⽽该节点成为左⼦节点的右⼦节点

**Hash值：**

底层采用的位运算符号计算出索引  
其他：取余数，伪随机算法  
调用hashcode方法结合数组长度计算出索引值，如果与前面存在的索引位置一样，比较hash值是否相同，如果相同则发生hash碰撞，底层会调用equals来比较两个值是否相同。相同则覆盖，如果都不相同就划出一个节点存储数据。

**初始化容量设置为10和为什么桶的长度是8转化为红黑树？**

1、假定指定初始容量是10，它会经过位运算变为16。用于找到大于等于10  
2、泊松分布，超过8的时候概率很小。

#### 二、TreeMap ####

红黑树实现，实现了NavigableMap接口，而NavigableMap接口继承了SortedMap接口，导航方法，返回有序key集合。

**特点：**

1.  天然支持排序，默认自然排序。
2.  synchronized来实现锁，实现线程安全，效率低

####    三、HashTable（线程安全） ####

synchronized来实现锁，实现线程安全，效率低

#### 四、ConcurrentHashMap（线程安全） ####

**不同jdk版本特点：**

*  jdk1.5加入的，jdk67主要是分段锁实现。
 *  jdk7：分段锁+数组+链表
 *  jdk8：数组+链表/红黑树+特殊结构
 *  jdk7会通过最多三次来计算，如果两次相同就返回，如果不同就分段锁来计算
 *  jdk8会维护一个计算属性来记录节点的数量，每次进行put操作都会使用自旋来增加属性值

**扩容机制：**

初始容量16，负载因子0.75，懒加载模式，支持并发，无序

**锁机制：**

CAS+Synchronize技术来保障线程安全,这里注意Node其实就是保存一个键值对的最基本的对象。其中Value和next都是使用的volatile关键字进行了修饰，以确保线程安全。在添加元素是，会进行cas判断，如果ok就插入其中，并将size+1,如果失败了，通过自旋锁再次尝试插入，直到成功为止。

**volatitle的作用：**

防止被其他线程修改不可见性。  
防止指令重排序

**锁的使用地方：**

先判断hash是否冲突，不冲突就自旋插入，如果存在hash冲突就是会加锁来保证线程安全，size是直接返回count值

###  ###

[img-bkAGkAYM-1647002825415_E_Typora_java_img_image-20220221154516785.png]: https://img-blog.csdnimg.cn/ec0c098804e145d6b49f1873471526fe.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5pix5pmfMTY4,size_20,color_FFFFFF,t_70,g_se,x_16
[2fb92925c16f4ba2b3071d1ccadbc38b.png]: https://img-blog.csdnimg.cn/2fb92925c16f4ba2b3071d1ccadbc38b.png