HashMap的相关问题及其底层数据结构和操作流程

本文主要介绍关于java,数据结构,开发语言的知识点，对【HashMap的相关问题】和【java面试的时候你被提问过哪些问题】有兴趣的朋友可以看下由【PnJg?】投稿的技术文章，希望该技术和经验能帮到你解决你所遇的JavaSE相关技术问题。

java面试的时候你被提问过哪些问题

目录

HashMap底层数据结构

JDK1.7和1.8有何不同？

为什么要用红黑树？

扩容

树化，何时会树化？

为何一上来不树化

树化阈值为何是8

何时会退化为链表？

索引 

索引是如何计算的？

hashcode都有了，为何还要提供hash()方法？

数组容量为何是2的n次幂？ 

 容量不用2的n次幂行不行？

Put方法与扩容

介绍一下put方法流程

1.7与1.8有何不同 

 扩容（加载）因子为何默认是 0.75f

 并发问题

 多线程下操作hashmap会有什么问题？

1、扩容死链（1.7）

2、数据错乱（1.7，1.8）

key 的设计 

key 的设计要求

 String 对象的 hashCode() 设计，为啥每次乘的是31

---

HashMap底层数据结构 JDK1.7和1.8有何不同？ 1.7 数组 + 链表1.8 数组 + （链表 | 红黑树）---->元素较多时链表会转换成红黑树

hash表可以做到快速查找：查找元素时只需要计算hash值，根据计算出来的下标去对应的表中的下标与元素进行比较，无需从头到尾一个个的去对比。 

为什么要用红黑树？

当多个元素计算出的hash值相同时，根据链接法会接在同一个下标下面，这样hash表可以快速查询的优势就体现不出来了。解决链表长度的方法有两个：扩容、红黑树。

扩容

当元素的个数超过当前容量的四分之三就会发生扩容，

 扩容之后桶下标要重新计算。

如果各个元素的原始hash值都一样，那么无论扩容几次都无法缩减链表长度。这时候只能树化。

树化，何时会树化？

树化要满足两个条件：链表长度超过树化阈值，固定值为8；数组容量大于64，否则不考虑树化。只有两个都满足才会树化。

红黑树：父节点左边的都比其小，父节点右边的都比其大（先根据hash码比较，一样的话根据key值比较）。搜索的时间复杂度是O(longN)

为何一上来不树化

当链表短的时候性能是比红黑树要好，hash 表的查找，更新的时间复杂度是 O(1)，而红黑树的查找，更新的时间复杂度是 O(log_2⁡n )，TreeNode 占用空间也比普通 Node 的大，如非必要，尽量还是使用链表

树化阈值为何是8

红黑树不是一个正常的情况，正常情况下链表长度不可能超过8，只有当有人恶意DOS攻击（准备大量一样hash值的对象，计算出来的桶下标一样）的时候，就会造成链表特别长。hash 值如果足够随机，则在 hash 表内按泊松分布，在负载因子 0.75 的情况下，长度超过 8 的链表出现概率是 0.00000006，树化阈值选择 8 就是为了让树化几率足够小

何时会退化为链表？

情况1：在扩容时如果拆分树时，树元素个数 <= 6 则会退化链表

情况2：remove 树节点时，（是根据移除之前的状态判断）若 root、root.left、root.right、root.left.left 有一个为 null ，也会退化为链表

索引  索引是如何计算的？

首先，计算对象的 hashCode()

再进行调用 HashMap 的 hash() 方法进行二次哈希

二次 hash() 是为了综合高位数据，让哈希分布更为均匀

最后 & (capacity – 1)---->这个计算方法只能用在capacity为2的n次幂上---->用按位与运算代替了跟容量进行取模运算， 得到索引

hashcode都有了，为何还要提供hash()方法？

二次哈希：

 为了让最后计算索引的hash值分布的更加均匀，避免链表过长的情况。取高位是为了避免低位数字一样，跟数组容量相模的时候出现hash值一样

数组容量为何是2的n次幂？ 

1. 计算索引时效率更高：如果是 2 的 n 次幂可以使用位与运算 & (capacity – 1)代替取模
2. 扩容时重新计算索引效率更高： hash & oldCap == 0 的元素留在原来位置 ，否则新位置 = 旧位置 + oldCap

 

 容量不用2的n次幂行不行？

容量为2的幂虽然计算索引速度快了，但是hash的分布就没那么好了，比如全都为偶数，那么只有偶数下标上有数。追求分布性更好可以选择质数作为容量大小，对于没有两次hash的值也能做到很好哈希分布性。

容量是 2 的 n 次幂这一设计计算索引效率更好，但 hash 的分散性就不好，需要二次 hash 来作为补偿，没有采用这一设计的典型例子是 Hashtable

Put方法与扩容 介绍一下put方法流程

HashMap 是懒惰创建数组的，首次使用才创建数组

计算索引（桶下标）

如果桶下标还没人占用，创建 Node 占位返回

如果桶下标已经有人占用

已经是 TreeNode 走红黑树的添加或更新逻辑

是普通 Node，走链表的添加或更新逻辑，如果链表长度超过树化阈值，走树化逻辑

返回前检查容量是否超过阈值，一旦超过进行扩容（先把这个元素放进旧数组，然后进行扩容，把旧数组的数据迁移到新数组）

1.7与1.8有何不同 

链表插入节点时，1.7 是头插法，1.8 是尾插法

1.7 是大于等于阈值且没有空位时才扩容，而 1.8 是大于阈值就扩容

1.8 在扩容计算 Node 索引时，会优化（ hash & oldCap == 0 的元素留在原来位置 ，否则新位置 = 旧位置 + oldCap）

 扩容（加载）因子为何默认是 0.75f

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

 并发问题  多线程下操作hashmap会有什么问题？ 1、扩容死链（1.7）

线程1（绿色）的临时变量 e 和 next 刚引用了这俩节点，还未来得及移动节点，发生了线程切换，由线程2（蓝色）完成扩容和迁移

线程2 扩容完成，由于头插法，链表顺序颠倒。但线程1 的临时变量 e 和 next 还引用了这俩节点，还要再来一遍迁移

 

第一次循环

循环接着线程切换前运行，注意此时 e 指向的是节点 a，next 指向的是节点 be 头插 a 节点，注意图中画了两份 a 节点，但事实上只有一个（为了不让箭头特别乱画了两份）当循环结束是 e 会指向 next 也就是 b 节点

第二次循环

next 指向了节点 ae 头插节点 b当循环结束时，e 指向 next 也就是节点 a

第三次循环

next 指向了 nulle 头插节点 a，a 的 next 指向了 b（之前 a.next 一直是 null），b 的 next 指向 a，死链已成当循环结束时，e 指向 next 也就是 null，因此第四次循环时会正常退出

2、数据错乱（1.7，1.8）

public class HashMapMissData {
    public static void main(String[] args) throws InterruptedException {

        HashMap
  
    map = new HashMap<>(); Thread t1 = new Thread(() -> { map.put("a", new Object()); // 97 => 1 }, "t1"); Thread t2 = new Thread(() -> { map.put("1", new Object()); // 49 => 1 }, "t2"); t1.start(); t2.start(); t1.join(); t2.join(); System.out.println(map); } }
  

两个线程同时向hashmap添加一个相同hash值的数，会导致其中一个被覆盖，造成数据丢失

key 的设计  key 的设计要求

HashMap 的 key 可以为 null，但 Map 的其他实现则不然

作为 key 的对象，必须实现 hashCode （为了key在hashmap中能有更好的分布性，提高性能）和 equals（万一计算出来的索引一样，进一步用equals比较是不是相同的对象），并且 key 的内容不能修改（不可变）否则会出现找不到对应的key（因为hashcode值已经变了）

key 的 hashCode 应该有良好的散列性

 String 对象的 hashCode() 设计，为啥每次乘的是31

目标是达到较为均匀的散列效果，每个字符串的 hashCode 足够独特

字符串中的每个字符都可以表现为一个数字，称为 $S_i$，其中 i 的范围是 0 ~ n - 1

散列公式为： S0∗31^{(n-1)}+ S1∗31^{(n-2)}+ … Si ∗ 31^{(n-1-i)}+ …S_{(n-1)}∗31^0

31 代入公式有较好的散列特性，并且 31 * h 可以被优化为

即 32 ∗h -h 

即 2^5 ∗h -h

即 h≪5 -h

本文《HashMap的相关问题》版权归PnJg?所有，引用HashMap的相关问题需遵循CC 4.0 BY-SA版权协议。