【面试宝典】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 攻击。