转载

【Java 容器面试题】谈谈你对HashMap 的理解

为了能够在面试回答中优雅而不失体面回答面试考点，该文章借鉴了不同平台对知识点的描述。

我的回答

HashMap 是一种存取高效但不保证有序的常用容器。它的数据结构为“数组+链表”，是解决哈希冲突的产物，也就是我们常说的链地址法。它实现了Map 接口采用K-V 键值对存储数据，并实现了浅拷贝和序列化。

HashMap 的默认初始大小为16，初始化大小必须为2的幂，最大大小为2的30次方。数组中存储的链表节点Entry 类实现于Map.Entry 接口，它实现了对节点的通用操作。HashMap 的阈值默认为“容量*0.75f”，当存储节点数量超过该值，则对map 进行扩容处理。

HashMap 提供了4种构造方法，分别是默认构造方法；可以指定初始容量的构造方法；可以指定初始容量和阈值的构造方法以及基于一个Map 的构造方法。虽然是构造函数，但是真正的初始化都是在第一次添加操作里面实现的。

在第一次添加操作中，HashMap 会先判断存储数组有没有初始化，如果没有先进行初始化操作，初始化过程中会取比用户指定的容量大的最近的2 的幂次方数作为数组的初始容量，并更新扩容的阈值。

接着添加操作讲吧。添加操作的执行流程为:

获取节点的操作和添加差不多，也是

HashMap 的其他操作大同小异，再讲讲HashMap1.7 的问题还有1.7 和1.8 的差别。

HashMap 是一个并发不安全的容器，在迭代操作是采用的是fast-fail 机制；在并发添加操作中会出现丢失更新的问题；因为采用头插法在并发扩容时会产生环形链表的问题，导致CPU 到达100%，甚至宕机。

解决并发问题可以采用

Hash1.7 和1.8 最大的不同在于1.8 采用了“数组+链表+红黑树”的数据结构，在链表长度超过8 时，把链表转化成红黑树来解决HashMap 因链表变长而查询变慢的问题；其次

HashMap 作为最基本的容器，它本身的设计与1.7 1.8的差异性导致HashMap 成为面试中最最高频的考点。所以掌握HashMap 势在必行，但是想要在各种宽泛的回答中脱颖而出，就必须对hashMap 前因后果了然于胸。

这些问题都要围绕一个点来回答： 减少哈希冲突 。

（1）容量必须为2 的幂是为了增加取值的可能性。

2 的n次幂转化为二进制为1后面n个0，在计算下标的时候是hash&(length - 1)，也就是&(n-1)个1:初始容量为4->100，length-1 -> 11。所有的二进制为都为1有什么好处？

可以看出&1保证了取值的平均。如果某一位为0 ，比如最后一位，那么它&出来下标就一定是个偶数，减少了HashMap 数组一半的取值，大大增加了冲突的可能。

（2）负载因子为0.75f 是空间与时间的均衡

如果负载因子小，意味着阈值变小。比如容量为10 的HashMap，负载因子为0.5f，那么存储5个就会扩容到20，出现哈希冲突的可能性变小，但是空间利用率不高。适用于有足够内存并要求查询效率的场景。
相反如果阈值为1 ，那么容量为10，就必须存储10个元素才进行扩容，出现冲突的概率变大，极端情况下可能会从O(1)退化到O(n)。适用于内存敏感但不要求要求查询效率的场景

（3）hash() 的意义在于使hash 结果不同 hash 算法的好坏直接影响hash 结构的效率，坏的hash 算法极端情况下可能会使hash 结构的存取效率从O(1)退化到O(n)。1.8 之所以把9 次扰动降到2 次，是出于计算效率的考虑。