JAVA集合最全面试题，值得收藏

概述

Java集合是Java面试中出现频率非常高的面试题，本文整理汇总Java集合中有价值的一些面试题，希望可以帮助大家，真的非常有用，建议大家收藏，以备不时之需。

其实面试题目内容很多，死记硬背肯定不行，关键还是了解原理，然后记住一些重点（关键字），最后尝试用自己的话串联起来，这样你才能在面试的时候游刃有余。

Map相关面试题

HashMap底层的数据结构是什么？

JDK1.7的数据结构是数组+链表，

JDK1.8的数据结构是数组+链表+红黑树。

其中，桶数组是用来存储数据元素，链表是用来解决冲突，红黑树是为了提高查询的效率。

• 数据元素通过映射关系，也就是散列函数，映射到桶数组对应索引的位置
• 如果发生冲突，从冲突的位置拉一个链表，插入冲突的元素
• 如果链表长度>8&数组大小>=64，链表转为红黑树
• 如果红黑树节点个数<6 ，转为链表

HashMap的扩容机制是什么样的？

HashMap底层的数组长度是固定，随着元素增加，需要进行动态扩容。

扩容的时机发生在put的时候，当当前HashMap的元素个数达到一个临界值的时候，就会触发扩容，把所有元素rehash之后再放在扩容后的容器中，这是一个相当耗时的操作。

临界值threshold 就是由加载因子和当前容器的容量大小来确定的。临界值（threshold ）= 默认容量（DEFAULT_INITIAL_CAPACITY） * 默认扩容因子（DEFAULT_LOAD_FACTOR）。比如容量是16，负载因子是0.75，那就是大于 16x0.75=12 时，就会触发扩容操作，扩容之后的长度是原来的二倍。容量都是2的幂次方。

为什么HashMap的容量是2的幂次方呢？

• 第一个原因是为了方便哈希取余。

将元素放在table数组上面，是用hash值%数组大小定位位置，而HashMap是用hash值&(数组大小-1)，却能和前面达到一样的效果，这就得益于HashMap的大小是2的倍数，2的倍数意味着该数的二进制位只有一位为1，而该数-1就可以得到二进制位上1变成0，后面的0变成1，再通过&运算，就可以得到和%一样的效果，并且位运算比%的效率高得多。HashMap的容量是2的n次幂时，(n-1)的2进制也就是1111111***111这样形式的，这样与添加元素的hash值进行位运算时，能够充分的散列，使得添加的元素均匀分布在HashMap的每个位置上，减少hash碰撞。

• 第二个方面是在扩容时，利用扩容后的大小也是2的倍数，将已经产生hash碰撞的元素完美的转移到新的table中去。

如果初始化HashMap，传一个17的值 new HashMap<> ，它会 怎么处理？

简单来说，就是初始化时，传的不是2的倍数时，HashMap会向上寻找 离得最近的2的 倍数 ，所以传入17，但HashMap的实际容量是32。源码如下：

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

由于HashMap的capacity都是2的幂，因此这个方法用于找到大于等于initialCapacity的最小的2的幂（initialCapacity如果就是2的幂，则返回的还是这个数）

通过5次无符号移位运算以及或运算得到：

• n第一次右移一位时，相当于将最高位的1右移一位，再和原来的n取或，就将最高位和次高位都变成1，也就是两个1；
• 第二次右移两位时，将最高的两个1向右移了两位，取或后得到四个1；
• 依次类推，右移16位再取或就能得到32个1；
• 最后通过加一进位得到2^n。

比如initialCapacity = 10 ，那就返回16， initialCapacity = 17，那么就返回32

10的二进制是1010，减1就是1001

第一次右移取或： 1001 | 0100 = 1101 ；

第二次右移取或： 1101 | 0011 = 1111 ；

第三次右移取或： 1111 | 0000 = 1111 ；

第四次第五次同理

最后得到 n = 1111，返回值是 n+1 = 2 ^ 4 = 16 ;

让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。这是为了防止，cap已经是2的幂。如果cap已经是2的幂，又没有执行这个减1操作，则执行完后面的几条无符号右移操作之后，返回的capacity将是这个cap的2倍。

例如十进制数值8，二进制为1000，如果不对它减1而直接操作，将得到答案10000，即16。显然不是结果。减1后二进制为111，再进行操作则会得到原来的数值1000，即8。

HashMap中为什么选择了0.75作为HashMap的默认加载因子呢？

简单来说，这是对 空间 成本和 时间 成本平衡的考虑。

我们都知道，HashMap的散列构造方式是Hash取余，负载因子决定元素个数达到多少时候扩容。

假如我们设的比较大，元素比较多，空位比较少的时候才扩容，那么发生哈希冲突的概率就增加了，查找的时间成本就增加了。

我们设的比较小的话，元素比较少，空位比较多的时候就扩容了，发生哈希碰撞的概率就降低了，查找时间成本降低，但是就需要更多的空间去存储元素，空间成本就增加了。

Jdk8中rehash的过程是怎么样的？

HashMap扩容后，需要将每一个元素重新rehash放置到HashMap中。jdk1.8中的做了优化操作，可以不需要再重新计算每一个元素的哈希值。

因为HashMap的初始容量是2的次幂，扩容之后的长度是原来的二倍，新的容量也是2的次幂，所以，元素，要么在原位置，要么在原位置再移动2的次幂。

看下这张图，n为table的长度，图 a 表示扩容前的key1和key2两种key确定索引的位置，图 b 表示扩容后key1和key2两种key确定索引位置。

元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

所以在扩容时，只需要看原来的hash值新增的那一位是0还是1就行了，是0的话索引没变，是1的化变成 原索引+oldCap ，看看如16扩容为32的示意图：

HashMap的put操作流程是什么样的？

1. 首先对key的哈希值通过扰动方法，获取一个新的哈希值。扰动函数： (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
2. 判断tab是否位空或者长度为0，如果是则进行扩容操作。

if ((tab = table) == null || (n = tab.length) == 0) 
    n = (tab = resize()).length;

1. 根据哈希值计算数组桶下标，如果对应下标正好没有存放数据，则直接插入，否则说明hash冲突了，这时候要遍历链表或者红黑树进行插入或者覆盖。 计算下标的方法：tab[i = (n - 1) & hash])。
2. 判断tab[i]是否为树节点，否则向链表中插入数据，是则向树中插入节点。
3. 如果链表中插入节点的时候，链表长度大于等于8，则需要把链表转换为红黑树。 转换树的方法：treeifyBin(tab, hash)
4. 最后所有元素处理完成后，判断是否超过阈值； threshold ，超过则扩容。

HashMap中的根据Hash值计算数组下标是怎么实现？

HashMap中需要将key计算得到的散列值映射到数组桶的位置上，源码中采用的是将散列值和数组长度 -1 做一个 " 与& " 操作，这样比直接取余运算%要快。

我们知道HashMap 的数组长度要取 2 的整数幂。以初始长度 16 为例，16-1=15。2进制表示是0000 0000 0000 0000 0000 0000 0000 1111 。和某个散列值做与操作如下，结果就是截取了最低的四位值：

相当于散列值地位的本身，和求余运算的逻辑等价。

HashMap中的散列值（哈希值）是怎么得到的？为什么这么做？

HashMap的哈希函数是先拿到 key 的hashcode，是一个32位的int类型的数值，然后让hashcode的高16位和低16位进行异或操作, 这种方式也要扰动函数。

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

这么做主要是为了为了降低哈希冲突的概率。

那你提到扰动函数异或操作可以降低哈希冲突，那它为什么可以降低呢？

正如前面讲过了，需要将Hash值求余映射到数组桶位置上，但是有一个问题就是，如果不采用扰动函数的方式，要是只取最后几位的话，碰撞也会很严重。如果散列本身做得不好，分布上成等差数列的漏洞，如果正好让最后几个低位呈现规律性重复，那就更难搞了。

这时候 扰动函数 的价值就体现出来了，看一下扰动函数的示意图：

右移 16 位，正好是 32bit 的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

解决哈希冲突的方法有哪几种，HashMap中采用的什么方式？

解决哈希冲突的方法常见的有下面几种：

1. 链地址法 ：在冲突的位置拉一个链表，把冲突的元素放进去。
2. 开放定址法：开放定址法就是从冲突的位置再接着往下找，给冲突元素找个空位。
3. 再哈希法 ：换种哈希函数，重新计算冲突元素的地址。
4. 建立公共溢出区 ：再建一个数组，把冲突的元素放进去。

HashMap中采用的是链地址法来解决Hash冲突。

HashMap中为什么要转换为红黑树？为什么不用二叉树/平衡树呢？

其实主要就是解决hash冲突导致链化严重的问题，如果链表过长，查找时间复杂度为O(n)，效率变慢。

本身散列表最理想的查询效率为O(1)，但是链化特别严重，就会导致查询退化为O(n)。

严重影响查询性能了，为了解决这个问题，JDK1.8它才引入的红黑树。红黑树其实就是一颗特殊的二叉排序树，这个时间复杂度是log(N)。

红黑树本质上是一种二叉查找树，为了保持平衡，它又在二叉查找树的基础上增加了一些规则：

1. 每个节点要么是红色，要么是黑色；

2. 根节点永远是黑色的；

3. 所有的叶子节点都是是黑色的（注意这里说叶子节点其实是图中的 NULL 节点）；

4. 每个红色节点的两个子节点一定都是黑色；

5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；

红黑树是一种平衡的二叉树，插入、删除、查找的最坏时间复杂度都为 O(logn)，避免了二叉树最坏情况下的O(n)时间复杂度。

平衡二叉树是比红黑树更严格的平衡树，为了保持保持平衡，需要旋转的次数更多，也就是说平衡二叉树保持平衡的效率更低，所以平衡二叉树插入和删除的效率比红黑树要低。

什么时候HashMap链表转红黑树呢？为什么阈值为8呢？

树化发生在table数组的长度大于64，且链表的长度大于8的时候。

为什么是8呢？

红黑树节点的大小大概是普通节点大小的两倍，所以转红黑树，牺牲了空间换时间，更多的是一种兜底的策略，保证极端情况下的查找效率。阈值为什么要选8呢？和统计学有关。理想情况下，使用随机哈希码，链表里的节点符合泊松分布，出现节点个数的概率是递减的，节点个数为8的情况，发生概率仅为0.00000006 。

至于红黑树转回链表的阈值为什么是6，而不是8？是因为如果这个阈值也设置成8，假如发生碰撞，节点增减刚好在8附近，会发生链表和红黑树的不断转换，导致资源浪费。

jdk1.8对HashMap主要做了哪些优化呢？为什么？

jdk1.8 的HashMap主要有五点优化：

1. 数据结构：数组 + 链表改成了数组 + 链表或红黑树。

原因 ：发生 hash 冲突，元素会存入链表，链表过长转为红黑树，将时间复杂度由 O(n) 降为 O(logn)

1. 链表插入方式：链表的插入方式从头插法改成了尾插法

简单说就是插入时，如果数组位置上已经有元素，1.7 将新元素放到数组中，原始节点作为新节点的后继节点，1.8 遍历链表，将元素放置到链表的最后。

原因 ：因为 1.7 头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环。

1. 扩容rehash：扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8 采用更简单的判断逻辑，不需要重新通过哈希函数计算位置，新的位置不变或索引 + 旧的数组容量大小。

原因： 提高扩容的效率，更快地扩容。

1. 扩容时机：在插入时，1.7 先判断是否需要扩容，再插入，1.8 先进行插入，插入完成再判断是否需要扩容；

2. 散列函数：1.7 做了四次移位和四次异或，jdk1.8只做一次。

原因 ：做 4 次的话，边际效用也不大，改为一次，提升效率。

HashMap 是线程安全的吗？多线程下会有什么问题？

HashMap不是线程安全的，可能会发生这些问题：

• 多线程下扩容死循环。JDK1.7 中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
• 多线程的 put 可能导致元素的丢失。多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在 JDK 1.7 和 JDK 1.8 中都存在。
• put 和 get 并发时，可能导致 get 为 null。线程 1 执行 put 时，因为元素个数超出threshold 而导致 rehash，线程 2 此时执行 get，有可能导致这个问题。这个问题在 JDK 1.7 和 JDK 1.8 中都存在。

有什么办法能解决HashMap线程不安全的问题呢？

Java 中有 HashTable、Collections.synchronizedMap、以及 ConcurrentHashMap 可以实现线程安全的 Map。

• HashTable 是直接在操作方法上加 synchronized 关键字，锁住整个table数组，粒度比较大，不推荐；
• Collections.synchronizedMap 是使用 Collections 集合工具的内部类，通过传入Map 封装出一个 SynchronizedMap 对象，内部定义了一个对象锁，方法内通过对象锁实现；
• ConcurrentHashMap 在jdk1.7中使用分段锁，在jdk1.8中使用CAS+synchronized。

能说一下ConcurrentHashmap的实现吗？

ConcurrentHashmap线程安全在jdk1.7版本是基于 分段锁 实现，在jdk1.8是基于CAS+synchronized 实现。

1.7分段锁

从结构上说，1.7版本的ConcurrentHashMap采用分段锁机制，里面包含一个Segment数组，Segment继承于ReentrantLock，Segment则包含HashEntry的数组，HashEntry本身就是一个链表的结构，具有保存key、value的能力能指向下一个节点的指针。实际上就是相当于每个Segment都是一个HashMap，默认的Segment长度是16，也就是支持16个线程的并发写，Segment之间相互不会受到影响。

• put流程

整个流程和HashMap非常类似，只不过是先定位到具体的Segment，然后通过ReentrantLock去操作而已，后面的流程，就和HashMap基本上是一样的。

1. 计算hash，定位到segment，segment如果是空就先初始化。

2. 使用ReentrantLock加锁，如果获取锁失败则尝试自旋，自旋超过次数就阻塞获取，保证一定获取锁成功。

3. 遍历HashEntry，就是和HashMap一样，数组中key和hash一样就直接替换，不存在就再插入链表，链表同样操作。

• get流程

get也很简单，key通过hash定位到segment，再遍历链表定位到具体的元素上，需要注意的是value是volatile的，所以get是不需要加锁的。

1.8 CAS+synchronized

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

• put流程

1. 首先计算hash，遍历node数组，如果node是空的话，就通过CAS+自旋的方式初始化。
2. 如果当前数组位置是空则直接通过CAS自旋写入数据
3. 如果hash==MOVED，说明需要扩容，执行扩容
4. 如果都不满足，就使用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 作为构造参数，从而来自定义元素优先级的先后。

参考

juejin.cn/post/684490…

www.cnblogs.com/crazymakerc…

mp.weixin.qq.com/s/SHkQ7LEOT…