Java集合框架-Collection
2022-05-27 15:51:07 29 举报Java集合框架-Collection 基于敖丙
作者其他创作
大纲/内容
简介
Java集合，也称作容器，主要是由两大接口（interface）派生出来的：Collection和Map
顾名思义，容器就是来存放数据的
那么两大接口的不同之处在于：
Colletion存放单一元素
Map存放key-value键值对
单身狗放在Collection中，couple存放在Map中
学习集合框架，有四个目标
1，明确每个接口和类的对应关系
2，对每个接口和类，熟悉常用的API
3，对不同的场景，能够选择合适的数据结构并分析优缺点
4，学习源码的设计
Collection
Collection 里还定义了很多方法，这些方法也都会继承到各个子接口和实现类里面，而这些API的使用也是日常工作和面试常见常考的，所以我们先看这些方法
操作集合，无非就是【增删改查】四大类
我们把API分为四大类
1，增：add()/addAll()
boolean add(E e)
add()方法传入的数据类型必须是Object ， 所以当写入基本数据类型的时候，会做自动装箱和自动拆箱
boolean addAll(Collection<? extends E> c)
addAll()方法，可以把另一个集合里的元素加到此集合中
2,删：remove()/removeAll()
boolean remove(Object o);
remove()是删除指定元素
boolean removeAll(Collection<?> c)
就是把集合B中的元素都删掉
3,改：Colletion Interface 里面没有
没有直接改元素的操作，反正删和增之后就可以完成改了
4，查：contains()/containsAll()
boolean contains(Object o)
查看集合中有没有某个特定的元素
boolean containsAll(Collection<?> c)
查看集合A是否包含了集合B
4,其他：isEmpty()/size()/toArray()
boolean isEmpty（）
判断集合是否为空
int size()；
集合的大小
Object[] toArray()
把集合转成数组
在父接口中都定义好了，子类不要也得要，当然子类中也会做一些自己的实现，这样就有了不同的数据结构
List
List最大的特点就是：有序，可重复
官网介绍
An ordered collection (also known as a sequence).
有序集合（也称为序列）。
有序集合（也称为序列）。
Unlike sets, lists typically allow duplicate elements.
与sets不同，list通常允许重复元素。
与sets不同，list通常允许重复元素。
这样的话Set的特点也有了，和List完全相反，Set是无序的，不重复的；
List的实现方式有LinkedList和ArrayList两种，那面试时最常问的就是两个数据结构如何选择。
对于这类选择问题：
1.考虑数据结构是否能完成需要的功能
2.如果都能完成需要的功能，就考虑那种更高效
ArrayList和LinkedList两个API的时间复杂度
add(E e)
O(1) , O(1)
add(E e)是在尾巴上添加元素，虽然ArrayList可能会有扩容的情况，但是均摊复杂度还是O（1）
add(int index , E e)
O(n),O(n)
add(int index ,E e) 实在特定的位置上加元素，LinkedList需要先找到这个位置，再加上这个元素，虽然单纯的加这个动作是O(1)，但是要找到这个位置还是O(n)
remove (int index)
O(n),O(n)
ArrayList找到这个元素的过程是O(1),但是remove之后，后续元素都要往前移动一位，所以均摊复杂度还是O(n)
LinkedList也是先找到这个index，这个过程是O(n),所以整体也是O(n)
remove(E E)
O(n),O(n)
ArrayList要先找到这个元素，这个过程是O(1),然后移除后还要往前移动一位，是O(n)
LinkedList要先找，O(n)，然后移走是O(1)，总的是O(n)
set (int index , E e)
O(1),O(n)
get (int index)
O(1),O(n)
造成时间复杂度的原因是什么
因为Arraylist是数组实现的
而数组和链表最大的区别就是数组是可以随机访问的
这个特点造成了数组里可以通过下标用O(1)的时间拿到任何位置的数，而链表做不到，只能从头开始逐个遍历
也就是说在改查两个功能上，因为数组能够随机访问，所以ArranList的效率高
那么增删呢？
如果不考虑找到这个元素的时间，数组因为物理上的连续性，当要增删元素师，在尾部还好，但是其他地方就会导致后续元素都要移动，所以效率较低，而链表则可以轻松的断开和下一个元素的连接，直接插入新元素或者移除旧的元素
但是实际上你不能不考虑找到元素的时间，而且如果是在尾部操作，数组量大时ArrayList会更快
总结
改查选择ArrayList
增删在尾部选择ArrayList
其他情况下，如果时间复杂度一样，推荐选择ArrayList，因为overhead更小，或者说内存使用更有效率
Vector
和ArrayList一样，也是继承自AbstractList，底层也是通过数组来实现的
但是现在已经被弃用了，因为它加了太多的synchronized
任何好处都是有代价的，线程安全的成本就是效率低，在某些系统里很容易称为平静，所以现在大家不再在数据结构的曾铭加synchronized，而是把这个任务转移给我们程序员
面试常见问题，Vector和ArrayList的区别
1，是刚才所说的线程安全问题
2，是扩容时扩多少的区别
ArrayList的扩容实现，这个算术右移操作是把这个数的二进制往右移动一位，最左边补符号位，但是因为容量没有负数，所以还是补0，那右移一位的效果就是除以2，那么定义的心容量就是原容量的1.5倍
vector默认情况扩容两倍
Queue和Deque
Queue（队列）是一端进另一端出的线性数据结构，而Deque是两段都可以进出的
Queue
Java中的这个Queue接口稍微有点坑，一般来说队列的语义都是先进先出
但是这里有个例外，就是PriorityQueue，也叫heap，并不按照进去的时间顺序出来，而是按照规定的优先级出去，并且他的操作不是O(1)de ,时间复杂度的计算稍微有点复杂
Queue有两组API，基本功能一样但是一组抛异常，另一组返回一个特殊值
增
抛异常：add(e)
返回值：offer(e)
删
抛异常：remove()
返回值：poll（）
查
抛异常：element()
返回值：peek()
为什么会抛异常呢？
比如队列空了，那么remove()就会抛异常，但是poll()就会返回null；element()就会抛异常，但是peek()就会返回null
为什么add(e)也会抛异常呢
有些Queue它会有容量的限制，比如BlockingQueue，如果已经达到了它最大的容量且不扩容，就会抛异常；如果offer(e) 就会返回false
怎么样选择呢？
首先，要用就用同一组API,前后要同一
其次，根据需求来选择是否抛异常
Deque
Deque是两端都可以进出的，那自然是由针对First端的操作和Last端的操作，而且没端都有两组，一组抛异常，一组返回特殊值
子主题
Queue和Deque的这些API都是O(1)的时间复杂度，准确来说就是均摊时间复杂度
实现类
实现类有哪些
LinkedList
ArrayDeque
PriorityQueue
如何选择实现类
如果想实现【普通队列-先进先出】的语义，就使用LinkedList或者ArrayDeque来实现
如果想实现【优先队列】就使用PriorityQueue
如果想实现【栈】的语义，就使用ArrayDeque
在实现普通队列时，如何选择用LinkedList 还是 ArrayDeque呢？
子主题
子主题
总的来说就是推荐使用ArrayDeque，因为效率高，而LinkedList还会有其他的额外开销；
ArrayDeque和LinkedList的区别
1，ArrayDeque是一个可扩容的数组，LinkedList是链表结构；
2，ArrayDeque是不可以存null值，但是LinkedList可以
3，ArrayDeque在操作头尾端的增删操作时更高效，但是LinkedList只有在当要移除中间某个元素且已经找到了这个元素后的移除才是O(1);
4,ArrayDeque在内存使用方面更高效
所以说只要不要存放null值，就选择ArrayDeque
Stack
Stack（栈）在语义上是先进后出的线性数据结构
但是因为Vector已经被弃用了，而Stack是继承Bector的
如果想实现Stack的语义，可以使用ArrayDeque
Set
无序，不重复，和数学中的集合概念一致；
Set的常用实现类有三个
HashSet
采用HashMap的key来存储元素，主要特点是无序的，基本操作就是O(1)的时间复杂度；
LinkedHashSet
这是一个HashSet + LinkedList 的结构，特点就是既拥有了O(1)的时间复杂度，又能保留插入的顺序
TreeSet
采用红黑树结构，特点是有序，可以用自然排序或者自定义比较器来排序，缺点就是查询速度没有HashSet快。
每个Set的底层实现其实就是对应的Map
子主题
收藏
0 条评论
下一页
