阅读这篇关于用于存储数据的Java集合框架的文章就足够了。那么这两个接口的区别就是：Collection存储的是单个元素；Map存储key-value键值对。即单身狗放在Collection里，情侣放在Map里。（那么你属于哪里呢？学习这些集合框架，我认为有4个目标：明确每个接口和类的对应关系；对于每个接口和类，熟悉常用的API；针对不同的场景，能够选择合适的数据结构，分析优缺点；学习源码设计，面试一定能答对关于Map，之前关于HashMap的文章已经讲的很透彻很详细，所以这篇文章就不重复了，没看过那篇小伙伴的小伙伴，去公众号回复“HashMap”看文章~Collection先看顶层的Collection。Collection也定义了很多方法，而这些方法也会被继承到各个子接口和实现类中，而这些API的使用在日常工作和面试中也很常见，所以我们先来看看这些方法。操作集合无非是“增、删、改、查询”四大类，又称为CRUD：Create、Read、Update、Delete。然后我也把这些API分为这四类：函数方法addadd()/addAll()Deleteremove()/removeAll()ChangeCollection接口不检查contains()/containsAll()其他isEmpty()/size()/toArray()下面详细看一下：add:booleanadd(Ee);add()方法通过输入的数据类型必须是Object，所以在写基本数据类型的时候，会自动进行自动装箱和拆箱。还有另一种方法，addAll()，它可以将另一个集合中的元素添加到这个集合中。booleanaddAll(集合c);删除：booleanremove(Objecto);remove()是要删除的指定元素。对应addAll()，自然有removeAll()，也就是删除集合B中的所有元素。booleanremoveAll(集合c);Change：没有直接在CollectionInterface中改变元素的操作，反正delete和add就能完成改变！检查：检查集合中是否存在特定元素：booleancontains(Objecto);检查集合A是否包含集合B：booleancontainsAll(Collectionc);还有一些对集合整体的操作：判断集合是否为空：booleanisEmpty();集合大小：intsize()；将集合转成一个数组：Object[]toArray();以上就是Collection中常用的API。它是在接口中定义的，子类必须是必需的。当然，子类也会自己做一些实现，这样就会有不同的数据结构。让我们一一看看。ListList最大的特点是：有序、可重复。看官网是怎么说的：Anorderedcollection（也叫sequence）。与集合不同，列表通常允许重复元素。这也道出了Set的特点。它与List完全相反。集合无序且不重复。List有两种实现方式，LinkedList和ArrayList。面试中问的最多的就是这两种数据结构如何选择。对于这类选型问题：一是考虑数据结构能否完成需要的功能；如果能完成，另一个就是考虑哪个效率更高。（一切都是这样。我们来看一下这两个类的API及其时间复杂度：函数式方法ArrayListLinkedListAddadd(Ee)O(1)O(1)Addadd(intindex,Ee)O(n)O(n)deleteremove(intindex)O(n)O(n)删除remove(Ee)O(n)O(n)changeset(intindex,Ee)O(1)O(n)checkget(intindex)O(1)O(n)几点解释：add(Ee)是在尾部添加元素。虽然ArrayList可能会扩展，但摊销时间复杂度仍然是O(1)的。add(intindex,Ee)是在特定位置添加一个元素。LinkedList需要先找到这个位置，然后添加这个元素。虽然简单的“添加”动作是O(1)，但是要找到这个位置还是O(n)。（有人觉得这是O??(1)，给面试官解释清楚就行，拒载。remove(intindex)是移除这个index上的元素，所以在ArrayList中找到这个元素的过程是O(1)，但是remove之后，后面的元素必须向前移动一位，所以摊销后的复杂度是O(n);LinkedList也需要先找到索引，这个过程是O(n)，所以整体也是O(n)。remove(Ee)是remove看到的第一个元素，那么ArrayList需要先找到这个元素，这个过程是O(n)，然后remove之后需要向前移动，这个是O(n)，总数仍然是O(n)；LinkedList也需要先找到，这个过程是O(n)，然后删除，这个过程是O(1)，一共是O(n)。那造成时间复杂度差异的原因是什么？答：因为ArrayList是用数组实现的。数组和链表最大的区别是数组可以被随机访问（randomaccess）。这个特性使得可以在O(1)时间内通过下标获取数组中任意位置的数，而链表做不到，只能从头开始逐一遍历。也就是说，就“改查”这两个功能而言，由于可以随机访问数组，所以ArrayList的效率是高的。“增删改查”呢？如果不考虑找这个元素的时间，因为数组的物理连续性，当你要增加或者删除元素的时候，到最后还可以，但是其他地方会导致后面的元素移动，所以效率低；链表可以方便地与下一个元素断开连接，直接插入新元素或移除旧元素。但是，事实上，你不能忽视寻找元素的时间。..而如果是放在最后操作，ArrayList在数据量大的时候速度会更快。所以：选择ArrayList进行查询；最后选择ArrayList进行增删改查；其他情况，如果时间复杂度相同，建议选择ArrayList，因为开销更小，或者内存使用效率更高。Vector是List的最后一个知识点，下面说说Vector。这也是一个暴露年龄的帖子，用过的都是大佬。Vector和ArrayList一样，也是继承自java.util.AbstractList，底层也是用数组实现的。但是现在已经弃用了，因为...它添加了太多的同步！任何好处都是有代价的。线程安全的代价是效率低下，在一些系统中很容易成为瓶颈，所以现在大家都不那么在数据结构层面加上synchronized，而是把这个任务交给我们程序员来做==然后面试常问：WhatisVector和ArrayList的区别，只回答这个还不够全面。看看stackoverflow上高票的回答：一个是刚才提到的线程安全问题；另一个是扩展时扩展多少的区别。这个还得看源码：这是ArrayList的扩展实现。这个算术右移操作就是把这个数的二进制数向右移动一位，补上最左边的符号位。但是因为容量中没有负数，所以还是加了0。然后右移一位的作用是除以2，那么定义的新容量就是原来容量的1.5倍。我们再看一下Vector：因为我们通常不定义capacityIncrement，所以它默认将容量翻倍。如果你回答了这两点，你就没事了。Queue&DequeQueue是一种线性数据结构，一端进入，另一端退出；而Deque可以在两端进出。QueueJava中的队列接口有点棘手。一般来说，队列的语义是先进先出（FIFO）。但是这里有一个例外，就是PriorityQueue，也叫堆，不是按照进去的时间顺序出来的，而是按照指定的优先级出去的，它的操作不是O(1)，时间复杂度的计算有点复杂，后面会单独写一篇文章讲。Queue方法官网[1]对此进行了总结。它有两组基本功能相同的API，但是：一组会抛出异常；另一组将返回一个特殊值。Add(e)offer(e)deleteremove()poll()看到为什么element()peek()抛出异常了吗？比如队列为空，remove()会抛出异常，但是poll()返回null；element()抛出异常，peek()返回null。那为什么add(e)会抛出异常呢？有些Queue是有容量限制的，比如BlockingQueue，如果已经达到最大容量不再扩容，就会抛出异常；但如果提供（e），它将返回false。那么如何选择呢？：第一，想用就用同一套API，前后台一定要统一；二是根据需要。如果你需要它抛出异常，就使用抛出异常的那个；但是在做算法题的时候基本不会用到，所以选择返回特殊值的那组就行了。DequeDeque可以在两端进出。自然有First端的操作和Last端的操作。然后每一端有两组，一组抛出异常，另一组返回一个特殊的值：抛出异常的函数的返回值增加addFirst(e)/addLast(e)offerFirst(e)/offerLast(e)removeremoveFirst()/removeLast()pollFirst()/pollLast()看getFirst()/getLast()peekFirst()/peekLast()一样用，想用就用同组。Queue和Deque这些API的时间复杂度是O(1)，准确的说是摊销时间复杂度。一共有三个实现类：所以，如果要实现“普通队列——先进先出”的语义，使用LinkedList或者ArrayDeque；如果要实现“优先队列”的语义，使用PriorityQueue；如果要实现“堆栈”的语义，请使用ArrayDeque。让我们一一看看。实现普通队列时，如何选择LinkedList或ArrayDeque？看看StackOverflow[2]上的高票答案：综上所述，推荐使用ArrayDeque，效率高，LinkedList会有其他额外的开销（overhead）。那么ArrayDeque和LinkedList有什么区别呢？还是在刚才同样的问题下，这是我认为最好的总结：ArrayDeque是一个可展开的数组，LinkedList是一个链表结构；空值不能存储在ArrayDeque中，但是LinkedList可以；ArrayDeque在头部和尾部进行增删操作时效率更高，而LinkedList只有在要移除中间的一个元素并且已经找到该元素时才为O(1)；ArrayDeque在内存中使用效率更高。所以，只要不是一定要存空值，就选ArrayDeque！那么如果一个很资深的面试官问你，什么情况下应该选择使用LinkedList呢？答：在Java6之前。.因为ArrayDeque是Java6以后才有的。。为了版本兼容，我们不得不在实际工作中做出一些妥协。.最后一个问题是关于Stack的。StackStack在语义上是一种后进先出(LIFO)线性数据结构。使用栈的高频面试题有很多，比如接水的问题。虽然最优方案是使用双指针，但是使用栈是最直观的方案，需要自己去理解。有机会我会写的。那么栈在Java中是如何实现的呢？Java中虽然有Stack类，但是官方文档说不允许使用！原因也很简单，因为Vector已经被弃用了，而Stack继承了Vector的。那么如果要实现Stack的语义，就用ArrayDeque：Deque
