【一道面试题】关于HashMap的一系列问题

HashMap底层数据结构在1.7与1.8的变化

1.7是基于数组+链表实现的，1.8是基于数组+链表+红黑树实现的，链表长度达到8时会树化

使用哈希表的好处

使用hash表是为了提升查找效率，比如我现在要在数组中查找一个A对象，在这种情况下是无法根据数组下标查找的，这样我们就需要从数组头部开始，将A对象与数组元素依次比较，直到找到A对象，这样显然是比较麻烦的，如果使用了hash表，我们只需要计算出A元素的hash值，通过hash值找到其在数组中的索引，就可以很快的找到A元素了，当然一个索引对应的很可能不止一个元素，所以需要使用数组+链表的形式，但如果链表的长度过长，查找时还是需要沿着链表一一比对，这样也是比较消耗性能的，为了避免链表长度过长造成的查找效率下降，有两种解决方案：1是数组扩容，2是链表树化

HashMap底层数组的扩容

底层数组默认长度是16，当数组使用超过最大长度的0.75（这个0.75被称为负载因子），则会对该数组进行扩容，扩容为原来长度的两倍，扩容结束之后，由于数组的长度发生了变化（元素位置的确定是由元素哈希值对数组长度取模），因此会重新计算集合元素在数组中的存储位置，因此扩容前存在的链表结构很可能会消失，这样也就在一定程度上解决了链表长度过长的问题

负载因子为什么选择0.75

• 在空间占用与查询时间之间取得较好的权衡
• 大于这个值，空间节省了，但链表就会比较长影响性能
• 小于这个值，冲突减少了，但扩容就会更频繁，空间占用也更多

链表树化

链表的树化有两个必要条件，一是数组长度大于等于64，二是链表长度必须超过8，如果链表长度超过了8但是数组长度小于64，那么会直接对数组进行扩容（此时不考虑阈值的问题）而非将链表树化，也就是说在数组长度小于64时，链表长度是可能大于8的；当上述两个条件都满足时，链表会树化为红黑树，红黑树的一个特点是父节点左侧的都是比它小的元素，父节点右侧的都是比它大的元素，因此在元素较多的情况下，红黑树的查找效率就比链表要高很多了，这也就是jdk1.8使用数组+链表+红黑树的意义

链表的树化，我们还需要思考几个问题

• 为什么不一上来就树化？

  在链表短时没有必要进行树化，在链表比较短的情况下，无论是查询还是更新，其性能都要高于红黑树，而且红黑树的内存占用比链表高，红黑树是由TreeNode组成的，而链表是由Node组成的，TreeNode的成员变量要比Node多很多，因此没有必要一上来就树化

• 树化阈值为什么选择8？

  首先需要说明的是，虽然HashMap底层数据结构使用的是数组+链表+红黑树，但是正常情况下是几乎不可能出现红黑树的，如果hash 值足够随机，则在 hash 表内按泊松分布，在负载因子 0.75 的情况下，长度超过 8 的链表出现概率是 0.00000006（一亿分之六），之所以树化阈值选择 8 就是为了让树化几率足够小

正常情况下链表几乎不可能树化，红黑树存在的意义主要是用来避免 DoS 攻击的，是用来应对偶然情况的一种保底策略

红黑树退化成链表

链表会树化成红黑树，红黑树也会退化成链表，红黑树退化的场景：

• 数组扩容时会对红黑树进行拆分，若拆分后树的元素小于等于6则退化为链表
• remove任意一个树节点之前，若root（根节点）、root.left（根节点的左孩子）、root.right（根节点的右孩子）、root.left.left（根节点的左孙子） 有一个为 null ，那么remove完成后，树也会退化为链表

索引的计算过程

对象先调用其自身的hashCode方法计算出hash值，再由HashMap的hash方法对这个hash值进行二次hash，二次hash的结果再使用位与运算（hash值 & (数组长度 – 1)），得到这个对象在hash表中的索引

这个过程中也有几个问题需要思考

• 数组容量为何要设计为2的n次幂？

  • 如果数组容量是2的n次幂，则位与运算与取模运算的结果是相同的，可以用位与运算代替取模运算，且效率更高；
  • 在数组扩容时，如果数组容量是2的n次幂，那么扩容时重新计算索引效率更高，只需要将链表中每个元素与oldCap（扩容前的容量）做位与运算，如果结果为0，那么说该元素在扩容后会保留在原位置，如果结果不为零，那么该元素在扩容后位置会发生变化，这样遍历下来，就可以把原来的链表拆分成两个链表，一是位置不需要移动的，二是位置需要移动的，在扩容后，位置需要移动的链表的新位置的索引=旧位置+oldCap
  • 容量设计为2的n次幂虽然可以提高计算索引时的效率，但是会导致hash的分布性变差，比如说我现在要存放一组较小的偶数，那么这些偶数就会集中在数组的偶数索引位置上（在没有经过二次hash的情况下），因此为了避免这种情况，需要进行二次hash；如果我们选择质数作为数组容量，那么hash的分布性是很好的，我们完全不需要进行二次hash，即使这样，HashMap仍然选择2的n次幂作为数组容量，是出于更看重效率的角度出发的

• 为什么要进行二次hash？

  之所以要进行二次hash，是为了让hash分布的更为均匀，避免一组数据的hash值集中在某些索引上导致链表过长

Put元素流程

HashMap 是懒惰创建数组的，首次插入元素时才会去创建数组，假如说现在要插入一个元素A，流程如下：

1. 计算出元素A的索引值

2. 如果该索引上没有元素，则创建元素A的Node节点占位并返回

3. 如果该索引上已经有元素了，则

   • 如果该索引位置上的元素是TreeNode，则走红黑树的添加或更新逻辑
   • 如果该索引位置上的元素是Node，则走链表的添加或更新逻辑，添加完毕后如果链表长度超过树化阈值，走树化逻辑

   是添加还是更新，需要比对元素A与其他元素的hash值，hash值不同走添加逻辑，hash值相同则调用元素的equals方法进行比对，返回false走添加逻辑，返回true走更新逻辑

4. 返回前检查容量是否超过阈值，一旦超过则对数组进行扩容

上述过程中，1.7 的实现与 1.8 的实现有所不同：

• 1.7 使用头插法，新增的元素会插入到链表头部；1.8 使用尾插法，新增的元素会插入到链表尾部
• 1.7 是数组使用长度超过阈值，且再次put时，put的索引位置上已经有元素了才会去对数组扩容； 1.8 是使用长度超过阈值就会扩容
• 1.8 在扩容计算 Node 索引时，会进行优化（这个优化上面提到过，1.7是没有这个优化的）

多线程下HashMap存在的问题

• 数据丢失：假如现在HashMap索引为1的位置上是空的，现在有t1和t2两个线程同时希望在该位置上插入元素，假设此时t1希望插入元素A，那么首先t1线程需要检查该位置上是否已经存在元素，经过检查后发现不存在元素，正当t1线程准备插入元素时，发生了线程切换，CPU执行权给到了t2线程，t2线程将要插入元素B，那么它首先还是会去检查该位置是否存在元素，结果当然是也不存在，于是t2线程便在该位置上插入了元素B然后返回，如果此时执行权再次给到t1线程，那么t1线程插入元素A就会把原来位置上的元素B给覆盖，这样就丢失了一次数据更新
• 并发扩容死链（存在于jdk1.7中）：在1.7中，由于使用头插法，当两个线程同时对数组进行扩容时很有可能会产生死链（环形链表），此时一旦有任意查找元素的动作，线程将会进入死循环，导致CPU飙升；1.8使用尾插法避免了这一问题

HashMap的key是否为null，作为key的对象应该有哪些要求

1. HashMap 的 key 可以为 null，Map 的其他实现则不然
2. 作为 key 的对象，必须实现 hashCode 和 equals 方法，并且要保证 key 的内容不能修改（不可变），一旦key被修改了，那么其hash值就会发生变化，那么就无法找到其在hash表中的索引了
3. key 的 hashCode 应该有良好的散列性

HashMap和HashTable的区别

• HashMap线程不安全，HashTable线程安全(大多使用Synchronize修饰)，所以相对来说HashMap要更快一些，这是最主要也是最重要的区别
• HashMap的key和value都允许为null，而HashTable键值对都不能为空，否则会报空指针异常
• HashMap在计算Hash值时需要二次Hash，而HashTable不需要，原因在于HashTable不使用2的n次幂来作为数组长度，Hash分布更加均匀
• 接上一点，既然说了HashTable不使用2的n次幂来作为数组长度，那就需要提一下HashTable的扩容规则了，HashTable的数组扩容是扩容为原来的两倍加一，而HashMap是扩容为原来的两倍
• Java8中HashMap使用数组+链表+红黑树的形式，而Java8中HashTable仍然是数组+链表