【面试宝典】HashMap的连环炮

注：文中源码都是基于jdk1.8

1、HashMap特性？

答：实现map接口；以KV的形式存储；不保证顺序；不是线程安全的；

2、HashMap与HashTable区别？

答：
1、hashTable是线程安全的，HashMap是线程不安全的。（这个回答出来就好了，其他点可以挑几个说）
2、HashMap的key、value都可以为null。Hashtable的key、value都不可以为null；
3、HashMap继承于AbstractMap，而Hashtable继承于Dictionary；
4、初始容量大小不一样，HashMap的容量为16；HashTable的容量为11；
5、扩容计算方式不一样，HashMap的扩容为：oldThr << 1 即2*老的容量大小；HashTable的扩容为：(oldCapacity << 1) + 1 即2*老的容量值+1；
6、HashMap的hashcode是自己实现的；HashTable的hashcode是object默认的；

3、HashMap线程不安全实际会如何体现？

答：
第一，如果多个线程同时使用put方法添加元素，假设正好存在两个put的key发生了碰撞(hash和key值一样)，那么根据HashMap的实现，这两个key会添加到数组的同一个位置，这样最终就会发生其中一个线程的put的数据被覆盖。

第二，如果多个线程同时检测到元素个数超过数组大小*loadFactor；这样会发生多个线程同时对hash数组进行扩容，都在重新计算元素位置以及复制数据，但是最终只有一个线程扩容后的数组会赋给table，也就是说其他线程的都会丢失，并且各自线程put的数据也丢失。且会引起死循环的错误。

4、HashMap如何变成线程安全？

答：可以使用Collections.synchronizeMap();方法把map变成线程安全；因为这个方法会把所有的方法都加上synchronized；

jdk1.5之后，也可以使用ConcurrentHashMap

5、HashMap的数据结构是什么？

答:数组+链表（红黑树）。
源码：

链表实现：

6、为什么String, Interger这样的wrapper类适合作为键？

答：String是不可变的，所以他的hashcode也是固定的，Integer的hashcode也是固定的；
因为map的put和get都是基于hash的，如果你的hash不固定，那么你存进去可能就获取不到了。

6.1、我们可以使用自定义的对象作为键吗？

答：可以的。
只要我们自己实现对象的hashcode和equals，保证put到map之后，他的hashcode不会变了，就可以。

7、HashMap初始化传入的容量参数的值就是HashMap实际分配的空间么？

答：不一定；
从源码看，


tableSizeFor方法会对传入的容量进行计算，经过多次无符号右移，找到大于等于initialCapacity的最小的2的幂。例如你传了7，那么initialCapacity为8；
如图打断点，可以看到输出结果。

8、什么是hash？

答：把任意长度的输入，通过哈希算法，变换成固定长度的输出，所输出的称为哈希值。一般用于快速查找和加密算法

8.1、什么是hash表？

哈希表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。

9、HashMap中hash函数是怎么实现的？

答：

对key的hashcode值先无符号右移16位，再与hashcode值进行亦或操作。
他的最终的目的是让散列分布地更加均匀。

10、HashMap中put的工作原理？

答：
1、对key进行hash函数计算；
2、获取链表的长度，并计算出hash在链表中的下标；
3、当前下标不存在Node，那么就创建一个新的Node；
4、如果当前下标存在Node，判断是否发生碰撞；
5、如果没有发生碰撞，就直接放到Node[]中；
6、如果发生了碰撞，以链表的形式放到Node[]的next中；如果链表的长度大于等于8，且Node[]的长度大于64，就把该链表切换为红黑树存储；
7、如果节点已经存在，就替换老的value；
8、如果Node[]超过阈值（LOAD_FACTOR*CAPACITY），就要进行扩容；

11、HashMap中get的工作原理？

答：
1、先对key的hashCode进行hash；
2、计算出hash所在的下标(n - 1) & hash，获取Node[]里的第一个Node；
3、总是比较第一个节点，如果hash和key都相等，那么直接返回；
4、如果发生了碰撞，那么需要判断是链表存储还是红黑树存储；
5、如果是红黑树存储，那么根据find来查找；
6、如果是链表存储，那么依次循环比较hash和key的值是否相等；

12、HashMap扩容机制是什么？

答：
1.扩容：容量扩充为原来的两倍（2 * table.length）；
2.移动：对每个节点重新计算哈希值，重新计算每个元素在数组中的位置，将原来的元素移动到新的哈希表中。

13、HashMap什么时候扩？

答：
在put的时候，如图判断是否需要进行扩容。

如果超过了负载因子的大小，那么会调用resize()方法，进行扩容。

14、HashMap每次扩多少？

答：
如图，每次扩容都是CAPACITY的2倍：

15、重新调整HashMap大小存在什么问题吗？

答：
（当多线程的情况下，可能产生条件竞争(race condition)）
当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。这个时候，你可以告诉面试官，在多线程的情况下，我会使用ConcurrentHashMap。

16、HashMap中如何解决碰撞问题？

答：
因为两个值的hashcode相同，所以他在Node[]里的下标相同，就发生碰撞了；HashMap使用链表的方式来存储那些碰撞的数据。jdk1.8之后如果链表太长，会使用红黑树。

链表和红黑树结构：

17、如何减少碰撞？

答：
使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生，提高效率。

18、HashMap中Entry链表太长，查找的时间复杂度可能达到 O(n)，怎么优化？

答：
将链表转为红黑树，实现 O(logn) 时间复杂度内查找。JDK1.8 已经实现了。

19、如何提升性能？

答：
创建map的时候，尽量指定map的初始容量大小，这样就可以减少resize。

20、什么是Hash攻击？

答：
通过请求大量key不同，但是hashCode相同的数据，让HashMap不断发生碰撞，硬生生的变成了SingleLinkedList。这样put/get性能就从O(1)变成了O(N)，CPU负载呈直线上升，形成了放大版DDOS的效果，这种方式就叫做hash攻击。在Java8中通过使用TreeMap，提升了处理性能，可以一定程度的防御Hash攻击。

可以加微信一起交流技术，记得备注：技术
不然通不过验证