概述
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操作流程是什么样的？
- 首先对key的哈希值通过扰动方法，获取一个新的哈希值。扰动函数：
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); - 判断tab是否位空或者长度为0，如果是则进行扩容操作。
if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;
- 根据哈希值计算数组桶下标，如果对应下标正好没有存放数据，则直接插入，否则说明hash冲突了，这时候要遍历链表或者红黑树进行插入或者覆盖。 计算下标的方法：
tab[i = (n - 1) & hash])。 - 判断tab[i]是否为树节点，否则向链表中插入数据，是则向树中插入节点。
- 如果链表中插入节点的时候，链表长度大于等于8，则需要把链表转换为红黑树。 转换树的方法：
treeifyBin(tab, hash) - 最后所有元素处理完成后，判断是否超过阈值； 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中采用的什么方式？
解决哈希冲突的方法常见的有下面几种：
- 链地址法 ：在冲突的位置拉一个链表，把冲突的元素放进去。
- 开放定址法：开放定址法就是从冲突的位置再接着往下找，给冲突元素找个空位。
- 再哈希法 ：换种哈希函数，重新计算冲突元素的地址。
- 建立公共溢出区 ：再建一个数组，把冲突的元素放进去。
HashMap中采用的是链地址法来解决Hash冲突。
HashMap中为什么要转换为红黑树？为什么不用二叉树/平衡树呢？
其实主要就是解决hash冲突导致链化严重的问题，如果链表过长，查找时间复杂度为O(n)，效率变慢。
本身散列表最理想的查询效率为O(1)，但是链化特别严重，就会导致查询退化为O(n)。
严重影响查询性能了，为了解决这个问题，JDK1.8它才引入的红黑树。红黑树其实就是一颗特殊的二叉排序树，这个时间复杂度是log(N)。
红黑树本质上是一种二叉查找树，为了保持平衡，它又在二叉查找树的基础上增加了一些规则：
- 每个节点要么是红色，要么是黑色；
- 根节点永远是黑色的；
- 所有的叶子节点都是是黑色的（注意这里说叶子节点其实是图中的 NULL 节点）；
- 每个红色节点的两个子节点一定都是黑色；
- 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；
红黑树是一种平衡的二叉树，插入、删除、查找的最坏时间复杂度都为 O(logn)，避免了二叉树最坏情况下的O(n)时间复杂度。
平衡二叉树是比红黑树更严格的平衡树，为了保持保持平衡，需要旋转的次数更多，也就是说平衡二叉树保持平衡的效率更低，所以平衡二叉树插入和删除的效率比红黑树要低。
什么时候HashMap链表转红黑树呢？为什么阈值为8呢？
树化发生在table数组的长度大于64，且链表的长度大于8的时候。
为什么是8呢？
红黑树节点的大小大概是普通节点大小的两倍，所以转红黑树，牺牲了空间换时间，更多的是一种兜底的策略，保证极端情况下的查找效率。阈值为什么要选8呢？和统计学有关。理想情况下，使用随机哈希码，链表里的节点符合泊松分布，出现节点个数的概率是递减的，节点个数为8的情况，发生概率仅为0.00000006 。
至于红黑树转回链表的阈值为什么是6，而不是8？是因为如果这个阈值也设置成8，假如发生碰撞，节点增减刚好在8附近，会发生链表和红黑树的不断转换，导致资源浪费。
jdk1.8对HashMap主要做了哪些优化呢？为什么？
jdk1.8 的HashMap主要有五点优化：
- 数据结构：数组 + 链表改成了数组 + 链表或红黑树。
原因 ：发生 hash 冲突，元素会存入链表，链表过长转为红黑树，将时间复杂度由 O(n) 降为 O(logn)
- 链表插入方式：链表的插入方式从头插法改成了尾插法
简单说就是插入时，如果数组位置上已经有元素，1.7 将新元素放到数组中，原始节点作为新节点的后继节点，1.8 遍历链表，将元素放置到链表的最后。
原因 ：因为 1.7 头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环。
- 扩容rehash：扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8 采用更简单的判断逻辑，不需要重新通过哈希函数计算位置，新的位置不变或索引 + 旧的数组容量大小。
原因： 提高扩容的效率，更快地扩容。
- 扩容时机：在插入时，1.7 先判断是否需要扩容，再插入，1.8 先进行插入，插入完成再判断是否需要扩容；
- 散列函数：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基本上是一样的。
- 计算hash，定位到segment，segment如果是空就先初始化。
- 使用ReentrantLock加锁，如果获取锁失败则尝试自旋，自旋超过次数就阻塞获取，保证一定获取锁成功。
- 遍历HashEntry，就是和HashMap一样，数组中key和hash一样就直接替换，不存在就再插入链表，链表同样操作。
- get流程
get也很简单，key通过hash定位到segment，再遍历链表定位到具体的元素上，需要注意的是value是volatile的，所以get是不需要加锁的。
