java面试重难点之集合专题-Map
大家好，现在开始陆续更新面试题，文章部分是我在面试中遇到的重难点，参考于网络，现将总结出来，帮助大家准备春招、暑期实习等。
如果有帮助，记得点赞收藏关注哦，你们的支持是我更新的动力，接下来会陆续更新各个专题的面试题。
Map集合主要考查HashMap，在这个专题里我会重点列出相关面试题。
1、Map集合图
（图片来源于网络）
2、HashMap集合简介
HashMap基于哈希表的Map接口实现，是以key-value存储形式存在，即主要用来存放键值对。HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突(两个对象调用的hashCode方法计算的哈希码值一致导致计算的数组索引值相同)而存在的（“拉链法”解决冲突）.JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（或者红黑树的边界值，默认为 8）并且当前数组的长度大于64时，此时此索引位置上的所有数据改为使用红黑树存储。
补充：将链表转换成红黑树前会判断，即使阈值大于8，但是数组长度小于64，此时并不会将链表变为红黑树。而是选择进行数组扩容。
这样做的目的是因为数组比较小，尽量避开红黑树结构，这种情况下变为红黑树结构，反而会降低效率，因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡 。同时数组长度小于64时，搜索时间相对要快些。所以综上所述为了提高性能和减少搜索时间，底层在阈值大于8并且数组长度大于64时，链表才转换为红黑树。具体可以参考 treeifyBin方法。
3、HashMap的put方法
HashMap的put方法可分成1.7与1.8两个版本
1.7：①、调用 hash(K) 方法计算 K 的 hash值，然后结合数组长度，计算得数组下标； hash(k)&(length - 1)
②、判断是否需要扩容（当容器中的元素个数大于 capacity * loadfactor 时，容器会进行扩容resize 为 2n）；
③、i.如果 该位置不存在元素，则执行插入，若存在，则发生碰撞；
如果该位置存在元素的话，用equals方法 判断当前数组位置上key以及这个位置链表中的key是否相等，相等的话就覆盖该key的value；
如果不相等的话就用头插法插入该键值对
1.8：①、调用 hash(K) 方法计算 K 的 hash值，然后结合数组长度，计算得数组下标；
②、判断该位置是否存在元素，如果不存在就把key和val封装成entry对象加入链表中
③、如果该位置存在元素，判断该节点是红黑树节点还是链表节点
如果是红黑树节点，接着判断该元素的key值与该数组下标位置上的key值及红黑树中的key否equal相等，相等的话直接更新，不相等的话直接加到树中
如果是node节点，接着判断该元素的key值与该数组下标位置上的key值及链表中的key否equal相等，相等的话直接更新，不相等的话用尾插法插到链表的后面去,接着判断是否转化为红黑树（链表节点个数大于8且数组长度大于64，如果小于64是将数组扩容）
④、判断数组是否需要扩容
扩容后的位置要么为原位置，要么为原位置+旧容量，取决于原来的hash值的前一个bit位是1还是0
4、HashMap 的 size 为什么必须是 2 的整数次方？
-
这样做总是能够保证 HashMap 的底层数组长度为 2 的 n 次方。当 length 为 2 的 n 次方时，h & (length – 1) 就相当于对 length 取模，而且速度比直接取模快得多，这是 HashMap 在速度上的一个优化。而且每次扩容时都是翻倍。
-
如果 length 为 2 的次幂，则 length – 1 转化为二进制必定是 11111……的形式，在与 h 的二进制进行与操作时效率会非常的快，而且空间不浪费。但是，如果 length 不是 2 的次幂，比如：length 为 15，则 length – 1 为 14，对应的二进制为 1110，在于 h 与操作，最后一位都为 0 ，而 0001，0011，0101，1001，1011，0111，1101 这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率，这样就会造成空间的浪费
5、为什么HashMap 多线程不安全？
HashMap会进行resize操作，在resize操作的时候会造成线程不安全。下面将举两个可能出现线程不安全的地方。
1、put的时候导致的多线程数据不一致。
这个问题比较好想象，比如有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。
2、另外一个比较明显的线程不安全的问题是HashMap的get操作可能因为resize而引起死循环（cpu100%）
具体分析如下：
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
} 这个方法的功能是将原来的记录重新计算在新桶的位置，然后迁移过去。
我们假设有两个线程同时需要执行resize操作，我们原来的桶数量为2，记录数为3，需要resize桶到4，原来的记录分别为：[3,A],[7,B],[5,C]，在原来的map里面，我们发现这三个entry都落到了第二个桶里面。 假设线程thread1执行到了transfer方法的Entry next = e.next这一句，然后时间片用完了，此时的e = [3,A], next = [7,B]。线程thread2被调度执行并且顺利完成了resize操作，需要注意的是，此时的[7,B]的next为[3,A]。此时线程thread1重新被调度运行，此时的thread1持有的引用是已经被thread2 resize之后的结果。线程thread1首先将[3,A]迁移到新的数组上，然后再处理[7,B]，而[7,B]被链接到了[3,A]的后面，处理完[7,B]之后，就需要处理[7,B]的next了啊，而通过thread2的resize之后，[7,B]的next变为了[3,A]，此时，[3,A]和[7,B]形成了环形链表，在get的时候，如果get的key的桶索引和[3,A]和[7,B]一样，那么就会陷入死循环。
如果在取链表的时候从头开始取（现在是从尾部开始取）的话，则可以保证节点之间的顺序，那样就不存在这样的问题了。
6、HashMap 的 table 的容量如何确定？loadFactor 是什么？ 该容量如何变化？这种变化会带来什么问题？
①、table 数组大小是由 capacity 这个参数确定的，默认是16，也可以构造时传入，最大限制是1<<30；②、loadFactor 是装载因子，主要目的是用来确认table 数组是否需要动态扩展，默认值是0.75，比如table 数组大小为 16，装载因子为 0.75 时，threshold 就是12，当 table 的实际大小超过 12 时，table就需要动态扩容；
③、扩容时，调用 resize() 方法，将 table 长度变为原来的两倍（注意是 table 长度，而不是 threshold）
④、如果数据很大的情况下，扩展时将会带来性能的损失，在性能要求很高的地方，这种损失很可能很致命。
7、HashMap的初始容量为什么是16？为什么必须是2的幂？如果输入值不是2的幂比如10会怎么样
1.为了数据的均匀分布，减少哈希碰撞。因为确定数组位置是用的位运算，若数据不是2的次幂则会增加哈希碰撞的次数和浪费数组空间。(PS:其实若不考虑效率，求余也可以就不用位运算了也不用长度必需为2的幂次)2.输入数据若不是2的幂，HashMap通过一通位移运算和或运算得到的肯定是2的幂次数，并且是离那个数最近的数字
8、讲讲HashMap的扩容机制
1.什么时候才需要扩容
因此，在扩容时，不需要重新计算元素的hash了，只需要判断最高位是1还是0就好了。
JDK8的HashMap还有以下细节：
- JDK8在迁移元素时是正序的，不会出现链表转置的发生。
- 如果某个桶内的元素超过8个，则会将链表转化成红黑树，加快数据查询效率。
9、HashMap与HashTable的区别
1、HashMap的Key、Value允许为空，但Key只允许一个为空，HashTable的Key、Value不允许为空。
2、HashMap是线程不安全的，HashTable是线程安全的，底层方法由synchronized关键字修饰，HashTable的执行效率会高于HashTable。
10、ConcurrentHashMap与HashTble的区别
HashTable 是使用 synchronize 关键字加锁的原理（就是对对象加锁）；
而针对 ConcurrentHashMap，在 JDK 1.7 中采用 分段锁的方式；JDK 1.8 中直接采用了CAS（无锁算法）+ synchronized。
11、HashMap & ConcurrentHashMap 的区别？
12、为什么 ConcurrentHashMap 比 HashTable 效率要高？
ConcurrentHashMap
JDK 1.7 中使用分段锁（ReentrantLock + Segment + HashEntry），相当于把一个 HashMap 分成多个段，每段分配一把锁，这样支持多线程访问。锁粒度：基于 Segment，包含多个 HashEntry。
JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度：Node（首结点）（实现 Map.Entry）。锁粒度降低了。
13、ConcurrentHashMap 锁机制具体分析
①、Segment 继承 ReentrantLock（重入锁） 用来充当锁的角色，每个 Segment 对象守护每个散列映射表的若干个桶；
②、HashEntry 用来封装映射表的键-值对；
③、每个桶是由若干个 HashEntry 对象链接起来的链表
