关于HashMap的灵魂问题（很灵魂的哦~），持续更新中...

---

前言

让我们一起来 Geek！Hello，大家好！我是Leo！

这篇文章是一篇关于HashMap的问题总结，希望能给各位看客老爷提供帮助。

本人是一个技术小白，如果这些问题和各位老爷的想法有出入，望指正（留言）。

好了废话不多说，我先帮各位盆友们活跃活跃气氛哈，上才艺......

---

- 什么是hash？

hash是将任意长度的输入通过hash算法，映射成一个固定长度的输出。

- 是否可以避免hash冲突?

hash冲突是不可避免的，类比：9个盒子要放10个物品，并且每个盒子最多只能放一个，肯定会有一个物品放不下。所以说hash冲突是没办法避免的。

- 在jdk1.8之后，hashmap的散列表是在什么时候创建的？

在Java 1.8中，HashMap的散列表是懒加载机制，只有在第一次put元素时创建的。当元素数量达到容量的0.75倍时，散列表会进行扩容操作。这个容量阈值可以通过构造函数中的负载因子参数进行调整。

tips：什么是懒加载机制呢？

所谓的懒加载机制就是在Spring中可以规定指定的bean不在启动时立即创建，而是在后续第一次用到时才创建，从而减轻在启动过程中对时间和内存的消耗。

- 说下HashMap的底层数据结构？

JDK1.8之前底层是由数组 + 链表组成的； JDK1.8之后底层是由数组 + 链表 + 红黑树组成，如下图

- JDK1.8为什么要使用数组+链表+红黑树呢？

为了提升hash碰撞（冲突）时因为链表过长导致的查询性能下降问题，使用链表的时间复杂度为O(n)，使用红黑树的时间复杂度为O(logn)。

- hashMap什么时候会出现红黑树？

- 链转树:

当同一索引位置新增Node<k,v>[ ]节点时，默认是会使用链表结构，当同一位置的节点新增大于 8 个的情况下，并且此时数组长度大于等于 64 ，就会将链表转化为红黑树（treeifyBin）；如果数组的长度小于 64 ，会进行扩容，并不会出现链表转红黑树。

- 树转链:

当同一个索引位置的节点在移除后达到 6 个，并且该索引位置的节点为红黑树节点，会将红黑树节点转链表节点（untreeify）。

总结：链表长度⼤于 8 且数组长度⼤于 64，则将链表转换成红⿊树；链表长度⼩于 6 时会将红⿊树转换成链表

- 为什么树转链表节点是到 6 而不是 8 呢？

这样会出现性能耗损问题，如果节点数大于8就转红黑树，小于8就转链表，频繁的切换链表结构和红黑树，会影响性能。

- HashMap的属性都有哪些？

table：存储节点的Node<k,v>[ ] table 数组。

threshold：扩容阈值；默认值是12，当数组大小超过这个阈值时，数组进行扩容。

loadFactor：哈希表的负载因子，主要是参与计算table数组的大小，默认值0.75f；扩容阈值 = 容量 * 负载因子。

- threshold除了用于存放扩容阈值还有什么其他的作用？

在新建HashMap对象时，threshold 还会用来存储初始化时的容量，HashMap 直到我们第一次插入节点时，才会对 table 进行初始化，避免不必要的空间浪费。

- HashMap的默认初始容量为多少？

HashMap的默认初始容量为 16 ；HashMap的容量 必须是2的n次方；HashMap 会根据我们传入的容量计算一个大于等于该容量的最小的2的N次方，例如传 9，容量为16。

注意：HashMap最小容量为：16 = 1 << 4，最大容量为：1 << 30（2的30次方）

- 为什么HashMap的容量必须是2的N次方?

判断桶的索引的实现是 i = ( n - 1 ) & hash，其中 n 是 map 的容量。任何 2 的整数幂 - 1 得到的二进制都是 1，如：16 - 1 = 15（1111）；32 - 1 = 31（11111）而 n-1 与 hash 做的是与运算(&)，与运算是 两个都为1，才为1;既然我们的 n-1 永远都是 1，那 ( n - 1 ) & hash 的计算结果就是 低位的hash 值。

    00100100 10100101 11000100 00100101    // Hash 值 
&   00000000 00000000 00000000 00001111    // 16 - 1 = 15
----------------------------------
    00000000 00000000 00000000 00000101    // 高位全部归零，只保留末四位。

如果 n 为 2次幂，可以保证数据的均匀插入，降低哈希冲突的概率，毕竟冲突越大，代表数组中的链表/红黑树越大，从而降低Hashmap 的性能。

- HashMap中对key的hash如何计算的？哈希桶的下标是如何得到的？（寻址算法）

hash算法：key.hashCode()值经过高低位异或得到hash值。

    static final int hash(Object key) {    
        int h;    
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

槽位（hash桶）下标：hash & （table. length - 1）得到下标。

例如： 有一个key.hashCode()的值为：

1111  1111   1111   1111  1111 1010 0111 1100   ^
0000  0000   0000   0000  1111 1111 1111 1111 (右移16位)

1111   1111  1111  1111  **0000  0101 1000 0011**

上述操作是将 h = key.hashCode() ^ h >>> 16(key的hash值高低16位进行异或操作)

为了避免hash冲突，将优化的hash值（高低16位异或运算的值）与（table.length - 1）进行 逻辑与运算，此时处理的hash值的低16位包含，高低16位的特征，避免出现hash冲突。

1111  1111  1111  1111  **0000 0101  1000  0011** &
0000  0000  0000  0000  0000  0000  0000   1111

- HashMap的put方法的过程是怎么样的？

• 首先根据寻址算法（根据key.hashCode()高低位的异或，然后再按位与 & (able. length - 1)得到槽位的下标）

• 根据槽内的状态不同，分为四种状态：

  • 第一种：slot == null
    • 将传进来的key和value包装成Node对象，直接占用这个slot（槽位）
  • 第二种：slot != null 并且槽内node 未链化。
    • 首先对比当前Node对象中的key和put进来的key是否完全相等，如果完全相等，将当前的Node对象的value做replace替换操作。
    • 否则这个put操作就是一次hash冲突，在当前的slot的Node后边采用尾插法进行追加一个Node对象。
  • 第三种：slot != null 并且槽内node 已经链化。
    • 首先迭代查找链表中的Node对象中的key和put进来的key是否完全相同，相同则replace替换当前node对象的value；
    • 否则将put的key和value包装新的Node追加到链表尾部，最后需要检查下当前链表的长度有没有达到树化阈值，如果达到树化阈值（树化标准），通过调用树化方法进行树化操作。
  • 第四种：slot != null 并且槽内node 链表已经转化为红黑树。

- HashMap 容量为何是 2 的倍数

HashMap的容量为2的倍数的原因是为了优化哈希值与数组索引之间的映射关系，以减少哈希冲突并提高查询效率。 在HashMap中，通过键（key）的哈希值计算其在内部数组中的索引位置。为了确保计算出的索引在数组范围内，需要将哈希值与数组大小减一进行按位与操作。如果数组大小是2的幂次方（即2的倍数），那么这个按位与操作可以简化为取哈希值的低位部分。这样可以很快地计算出索引，并且能够充分利用数组空间，减少哈希冲突的可能性。

举个例子，假设HashMap的容量为16（2的4次方），那么我们可以通过以下方式计算索引：

index = hash & (16 - 1)

由于16 - 1 = 15（二进制表示为1111），这个按位与操作实际上就是取hash值的低4位。这样可以确保计算出的索引在0到15之间，并且能够较好地分布在整个数组中。

如果容量不是2的倍数，那么按位与操作可能无法充分利用数组空间，导致哈希冲突更加频繁，从而降低查询效率。因此，将HashMap的容量设置为2的倍数是一种优化策略。