JAVA集合最全面试题，值得收藏（下）-阿里云开发者社区

1.8 CAS+synchronized

在JDK1.8中，放弃了Segment臃肿的设计，取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现，synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N 倍。

put流程

首先计算hash，遍历node数组，如果node是空的话，就通过CAS+自旋的方式初始化。
如果当前数组位置是空则直接通过CAS自旋写入数据
如果hash==MOVED，说明需要扩容，执行扩容
如果都不满足，就使用synchronized写入数据，写入数据同样判断链表、红黑树，链表写入和HashMap的方式一样，key hash一样就覆盖，反之就尾插法，链表长度超过8就转换成红黑树

get流程

get很简单，和HashMap基本相同，通过key计算位置，table该位置key相同就返回，如果是红黑树按照红黑树获取，否则就遍历链表获取。

HashMap、LinkedHashMap、TreeMap最大的区别是什么？

HashMap是无序的，根据 hash 值随机插入
LinkedHashMap可以实现按插入的顺序或访问顺序排序
TreeMap 是按照 Key 的自然顺序或者 Comprator 的顺序进行排序。

LinkedHashMap怎么实现有序的？

LinkedHashMap维护了一个双向链表，有头尾节点，同时 LinkedHashMap 节点 Entry内部除了继承 HashMap 的 Node 属性，还有 before 和 after 用于标识前置节点和后置节点。

可以实现按插入的顺序或访问顺序排序。

TreeMap 怎么实现有序的？

TreeMap 是按照 Key 的自然顺序或者 Comprator 的顺序进行排序，内部是通过红黑树来实现。所以要么 key 所属的类实现 Comparable 接口，或者自定义一个实现了Comparator 接口的比较器，传给 TreeMap 用于 key 的比较。

HashMap、TreeMap为什么建议使用Integer、String等作为key?

因为Integer、String等类都是final类型，key的hash值都是固定的。如果使用了一个自定义的对象作为key, 在put的时候它的hash值可能是1，但是后面修改了属性，导致重新计算出的hash值是2，这时候Map对象很可能就定位不到映射的位置了，就无法get出数据了。

WeakHashMap了解过嘛?它是怎么工作的?

WeakHashMap」类似HashMap ，不同点在WeakHashMap的key是「弱引用」的key。

谈到「弱引用」，在这里扩展下四种引用

强引用：Object obj=new Object()这种，只要强引用关系还存在，垃圾收集器就永远不会回收掉被引用的对象。

软引用: 一般情况不会回收，如果内存不够要溢出时才会进行回收

弱引用：当垃圾收集器开始工作，无论当前内存是否足够，都会回收掉只被弱引用关联的对象。

虚引用：为一个对象设置虚引用的唯一目的只是为了能在这个对象被回收时收到一个系统的通知。

正是因为WeakHashMap使用的是弱引用，「它的对象可能随时被回收」。WeakHashMap 类的行为部分「取决于垃圾回收器的动作」,调用两次size()方法返回不同值，调用两次isEmpty()，一次返回true，一次返回false都是「可能的」。

List相关面试题

ArrayList、LinkedList、Vector的区别是什么？

这个类都继承了List接口，是个有序的集合容器。

	ArrayList	LinkedList	Vector
底层数据结构	数组	双向链表	数组
是否可以存null	是	是	是
是否线程安全	否	否	是
性能	随机访问、查询快；在尾部添加效率高，其他地方插入慢	插入、删除快；随机访问查询慢；	性能差，因为用synchronized关键字

由于Vector不怎么用了，这里重点比较下ArrayList、LinkedList。

（1）数据结构不同

ArrayList基于数组实现
LinkedList基于双向链表实现

（2）多数情况下，ArrayList更利于查找，LinkedList更利于增删

ArrayList基于数组实现，get(int index)可以直接通过数组下标获取，时间复杂度是O(1)；LinkedList基于链表实现，get(int index)需要遍历链表，时间复杂度是O(n)；当然，get(E element)这种查找，两种集合都需要遍历，时间复杂度都是O(n)。
ArrayList增删如果是数组末尾的位置，直接插入或者删除就可以了，但是如果插入中间的位置，就需要把插入位置后的元素都向前或者向后移动，甚至还有可能触发扩容；双向链表的插入和删除只需要改变前驱节点、后继节点和插入节点的指向就行了，不需要移动元素。

注意，这个地方可能会出陷阱，LinkedList更利于增删更多是体现在平均步长上，不是体现在时间复杂度上，二者增删的时间复杂度都是O(n)。

（3）是否支持随机访问

ArrayList基于数组，所以它可以根据下标查找，支持随机访问，当然，它也实现了RandmoAccess 接口，这个接口只是用来标识是否支持随机访问。
LinkedList基于链表，所以它没法根据序号直接获取元素，它没有实现RandmoAccess 接口，标记不支持随机访问。

（4）内存占用，ArrayList基于数组，是一块连续的内存空间，LinkedList基于链表，内存空间不连续，它们在空间占用上都有一些额外的消耗：

ArrayList是预先定义好的数组，可能会有空的内存空间，存在一定空间浪费
LinkedList每个节点，需要存储前驱和后继，所以每个节点会占用更多的空间

ArrayList为什么要进行扩容？它的扩容机制是什么样的？

ArrayList的底层数据结构就是一个数组，但是java中的是固定长度的，随着ArrayList不断添加元素，这时候就需要对底层的数组进行扩容。

ArrayList扩容的本质就是计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去。默认情况下，新的容量会是原容量的1.5倍。

ArrayList存储元素的数组elementData是transient的，那么它是如何进行序列化？

ArrayList实现了Serializable接口，说明可以支持序列化。但是ArrayList底层存放数据的数组对象elementData加了关键字transient，加了这个关键字后，会对这个字段不进行序列化，那ArrayList没有序列化数组对象吗？其实不是的。

实际上ArrayList在序列化的时候会调用writeObject()方法，将size和element写入ObjectOutputStream；反序列化时调用readObject()，从ObjectInputStream获取size和element，再恢复到elementData。

而不是通过elementData来序列化，主要原因在于elementData是一个缓存数组，它通常会预留一些容量，等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素，采用上诉的方式来实现序列化时，就可以保证只序列化实际存储的那些元素，而不是整个数组，从而节省空间和时间。

ArrayList在删除元素的时候，需要注意什么？

在删除元素的时候，不要再for循环中或者foreach中删除元素，可能会出现异常。正确的做法，可以使用迭代器的方式删除或者使用jdk8新提供的removeIf这杨的api。

正确方式：

Iterator<Integer> it = list.iterator();
  while(it.hasNext()){
  // do something
  it.remove();
}

错误方式：

for(Integer i : list){
  list.remove(i)
}

ArrayList中有个subList方法，这个方法是干嘛的，使用要注意什么？

subList() 方法用于截取并返回动态数组中的一部分发，它是ArrayList的一个子视图，你可以对这个子list添加、删除元素，最终也会影响到原来的list。但是如果你对修改了原来的list，在调用子list的任何操作，都会报异常ConcurrentModificationException。

你知道集合中的Fail-fast机制吗？为什么要有这样的机制？

FailFast机制也叫做快速失败机制，它只能被用来检测错误，因为JDK并不保证fail-fast机制一定会发生。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。

通过记录ArrayList容器的modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

那什么是安全失败（fail-safe）机制呢？

采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发Concurrent ModificationException。

缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。

场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改，比如CopyOnWriteArrayList类。

ArrayList是线程安全的吗？有哪几种实现ArrayList线程安全的方法？

ArrayList不是线程安全的。保证ArrayList的线程安全可以通过这些方案：

使用 Vector 代替 ArrayList。（不推荐，Vector是一个历史遗留类）
使用 Collections.synchronizedList 包装 ArrayList，然后操作包装后的 list。
使用 CopyOnWriteArrayList 代替 ArrayList。
在使用 ArrayList 时，应用程序通过同步机制去控制 ArrayList 的读写。

CopyOnWriteArrayList是怎么实现的呢？

CopyOnWriteArrayList就是线程安全版本的ArrayList。

CopyOnWriteArrayList采用了一种读写分离的并发策略。CopyOnWriteArrayList容器允许并发读，读操作是无锁的，性能较高。至于写操作，比如向容器中添加一个元素，则首先将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器。

Set相关面试题

说一下 HashSet 的实现原理？

HashSet最大的特点就是不允许重复的值。

HashSet 是基于 HashMap 实现的，HashSet的值存放于HashMap的key上，

HashMap的value统一为PRESENT，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层 HashMap 的相关方法来完成，

HashSet如何检查重复？HashSet是如何保证数据不可重复的？

向HashSet 中add ()元素时，判断元素是否存在的依据，不仅要比较hash值，同时还要结合equles 方法比较。

HashSet 中的add ()方法会使用HashMap 的put()方法。

HashMap 的 key 是唯一的，由源码可以看出 HashSet 添加进去的值就是作为 HashMap 的key，并且在HashMap中如果K/V相同时，会用新的V覆盖掉旧的V，然后返回旧的V。所以不会重复（ HashMap 比较key是否相等是先比较 hashcode 再比较equals )。

其他相关面试题

常用数据接口数组、链表、哈希表、树的特点是什么？

数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)，但在数组中间以及头部插入数据时，需要复制移动后面的元素。
链表：一种在物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素）组成，结点可以在运行时动态生成。每个结点都包含“存储数据单元的数据域”和“存储下一个结点地址的指针域”这两个部分。由于链表不用必须按顺序存储，所以链表在插入的时候可以达到O(1)的复杂度，但查找一个结点或者访问特定编号的结点需要O(n)的时间。
哈希表：根据关键码值（Key value）直接进行访问的数据结构。通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组就叫做哈希表。
树：由n（n≥1）个有限结点组成的一个具有层次关系的集合，就像是一棵倒挂的树。

Queue 与 Deque 的区别是什么？

Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循先进先出（FIFO）规则。

Queue 扩展了 Collection 的接口，根据因为容量问题而导致操作失败后处理方式的不同可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。

Deque 是双端队列，在队列的两端均可以插入或删除元素。

Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：

ArrayDeque和LInkedList都实现了Deque接口，他们有什么区别？

ArrayDeque 和 LinkedList 都实现了 Deque 接口，

ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。
ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。
ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。

栈的特点是什么？Java中你使用什么容器实现栈的功能？

栈最大的特点就是先进后出。

java中实现栈的功能有Stack类和ArrayDeque, Stack类继承了Vector方法，所有的方法都加了synchronized关键字同步，效率不高。更加推荐使用ArrayDeque这个类。

PriorityQueue这个类是干嘛的？它有什么特点呢？

PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。

PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据。
PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。
PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。