java各大集合的区别

​ Java集合也称呼为容器&＃xff0c;他是由2大接口组曾&＃xff0c;一个是Collection主要用来存放单一的元素&＃xff0c;另一个是Map接口&＃xff0c;主要用来存放K-V的数据。

**List&＃xff1a;**存储的元素是有序的&＃xff0c;可重复得到。

Set&＃xff1a; 存储的元素是无序了&＃xff0c;但是不可以重复。

**Queue: **使用特定的排序规则来确定排序顺序&＃xff0c;存储的元素是有序的&＃xff0c;可以重复的

Map: 使用k-v存储。key是无序的&＃xff0c;不可以重复。val是无序的可以重复。

List

ArrayList&＃xff1a; Object[] Arrays

Vector: Object[] arrays

LinkedList: 双向链表&＃xff08;JDK1.6之前未循环链表&＃xff0c;JDK1.7取消的循环&＃xff09;

Set

HashSet&＃xff1a; &＃xff08;无序&＃xff0c;唯一&＃xff09;基于HashMap实现&＃xff0c;底层采用HashMap来保存元素

**LinkedHashSet&＃xff1a; ** LinkedHashSet是HashSet的子类&＃xff0c;内部是通过LinkedHashMap来实现。

TreeSet&＃xff1a; 有序唯一&＃xff1a;红黑树&＃xff08;自平衡的排序二叉树&＃xff09;

Queue

**PriortyQueue: ** Object[] array 数组来实现二叉堆

ArrayQueue: Object[] arrays 数组 &＃43; 双指针

Map

HashMap: JDK1.8之前是由数组&＃43;链表组成&＃xff0c;数组是HashMap的主体&＃xff0c;链表主要是为了解决hash冲突存在的&＃xff0c;使用拉链法解决hash冲突。在JDK1.8以后在解决hash冲突有了很大的变化&＃xff0c;当链表长度大于阈值8并且数组长度大于等于64的时候就会转换为红黑树&＃xff0c;否则就是进行数组扩容数组。

LinkedHashMap&＃xff1a; LinkedHashMap继承自HashMap,它和hashmap的结构大致相同&＃xff0c;只不过他在上面的结构上添加了双向链表&＃xff0c;这样可以保证k-v的形式插入&＃xff0c;同事也可以通过链表进行相应的操作。

HashTable 数组&＃43;链表组成&＃xff0c;数组是HashTable的主体&＃xff0c;链表主要解决hash冲突。

TreeMap &＃xff1a; 红黑树&＃xff08;自平衡的排序二叉树&＃xff09;

Collection

​ 对于Coleection来说&＃xff0c;它主要有3大子接口List、Set、Queue

ArrayList和vector的区别

ArrayList是list的主要实现类&＃xff0c;底层使用Object[]存储&＃xff0c;适合频繁的查找工作&＃xff0c;线程不安全

Vector是list的古老的类&＃xff0c;底层使用Object[]存储&＃xff0c;是线程安全的

ArrayList和LinkedList的去呗

他们都是线程不安全的&＃xff0c;ArrayList的底层是数组&＃xff0c;LinkedList的底层是双向链表

插入的区别&＃xff1a;

当我们Arraylist尾插入的情况时间复杂度就是O(1)&＃xff0c;如果我们插入的位置不是尾巴&＃xff0c;是某个index的位置&＃xff0c;那么时间复杂度就是O(n-index)。删除也是同理&＃xff0c;因为我们要实现向前向后的移动。

当我们LinkedList实现头插入和尾巴插入删除的时候时间复杂度是O(1),当我们要再在位置i插入或者删除元素的时候&＃xff0c;时间复杂度是i&＃xff0c;因为我们在移动到指定的位置在开始插入。

随机访问的区别

LinkedList不支持随机访问&＃xff0c;但是ArrayList支持随机访问&＃xff0c;因为ArrayList实现了RandomAccess接口&＃xff0c;所以支持快速随机访问也就是get方法。

内存的占用

​ ArrayList的内存占用是它内部的数组所占用的大小&＃xff0c;而LinkedList内存占用的内存是根据元素的个数。

​ ArrayList底层实现了RandomAccess接口&＃xff0c;但是这个接口里面是空空的什么也没有写&＃xff0c;我想&＃xff0c;**这个接口可能就是一个标识吧&＃xff0c;标识告诉我们ArrayList是可以实现的随机访问的。**LinkedList没有实现RandomAccess接口时因为它的底层数据结构&＃xff0c;而ArrayList的底层是数组天然支持随机访问&＃xff0c;而数组要到置顶的位置才可以时间复杂是O(节点的位置)&＃xff0c;所以不支持随机访问&＃xff0c;

Queue

​ Queue是单端队列&＃xff0c;遵循这FIFO&＃xff08;先进先出&＃xff09;的规则

ArrayDeque和LinkedList的区别

虽然他们都实现了Deque接口&＃xff0c;两者都有队列的功能&＃xff0c;他们的区别如下

​ ArrayDeque是基于可变长的数组和双指针实现的。而LinkedList是通过链表来实现的。

​ ArrayDeque不支持NUll值&＃xff0c;但是LinkedList支持

​ ArrayDeue插入的时候可能会出现扩容的过程&＃xff0c;不过均摊后他的时间复杂度依然是O(1),然后Linked不需要扩容&＃xff0c;但是每次插入数据需要申请新的堆空间&＃xff0c;均摊的话性能很慢。

PriorityQueue

​ PriorityQueue利用了二叉堆的数据结构实现&＃xff0c;底层使用可变长的数组来存数据。

​ PriorityQueue通过堆元素的上符合下沉&＃xff0c;实现了在O&＃xff08;Longn&＃xff09;的时间复杂度内插入元素和删除堆顶元素。

​ PriorityQueue不是线程安全的&＃xff0c;不支持存储NUll和non-comparable对象

​ priorityQueue默认是小顶堆&＃xff0c;达到你是可以接受一个COmparator作为构造参数来改变优先级的规则

Set

hashSet,linkedhashset,treeste都是通过set接口实现的&＃xff0c;都可以保证元素的唯一&＃xff0c;但是他们都不是线程安全的。

他们的区别主要在他们的底层不一样&＃xff0c;hashset的底层是hash表&＃xff0c;linkedhashset是链表&＃43;hash表元素的插入取出的顺序满足fifo&＃xff0c;treeset的底层是红黑树&＃xff0c;元素是有序的&＃xff0c;排序由自然排序和自定义排序规则。