阅读这篇关于用于存储数据的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(Collection>c);还有一些对集合整体的操作:判断集合是否为空: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
