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