HashMap八股文，一篇就够了

HashMap八股文，一篇就够了 HashMap ① HashMap 的底层结构和原理

HashMap 就是以 Key-Value 的方式进行数据存储的一种数据结构嘛，在我们平常开发中非常常用，它在 JDK 1.7 和 JDK 1.8 中底层数据结构是有些不一样的。总体来说，JDK 1.7 中 HashMap 的底层数据结构是数组 + 链表，使用 Entry 类存储 Key 和 Value；JDK 1.8 中 HashMap 的底层数据结构是数组 + 链表/红黑树，使用 Node 类存储 Key 和 Value。当然，这里的 Entry 和 Node 并没有什么不同

• Node 类的源码

  // HashMap 1.8 内部使用这个数组存储所有键值对
  transient Node[] table;
  

  每一个节点都会保存自身的 hash、key 和 value、以及下个节点

• 简略的 HashMap 示意图

因为 HashMap 本身所有的位置都为 null 嘛，所以在插入元素的时候即 put *** 作时，会根据 key 的 hash 去计算出一个 index 值，也就是这个元素将要插入的位置。举个例子：比如 put("小牛肉"，20)，我插入了一个 key 为 “小牛肉” value 为 20 的元素，这个时候我们会通过哈希函数计算出这个元素将要插入的位置，假设计算出来的结果是 2：

当然数组的长度是有限的，在有限的数组上使用哈希，那么哈希冲突是不可避免的，很有可能两个元素计算得出的 index 是相同的，那么如何解决哈希冲突呢？拉链法。也就是把 hash 后值相同的元素放在同一条链表上。如：

当然，当 Hash 冲突严重时，在数组上形成的链表会变的越来越长，由于链表不支持索引，要想在链表中找一个元素就需要遍历一遍链表，那显然效率是比较低的。为此，JDK 1.8 引入了红黑树，当链表的长度大于 8 的时候就会转换为红黑树，不过，在转换之前，会先去查看 table 数组的长度是否大于 64，如果数组的长度小于 64，那么 HashMap 会优先选择对数组进行扩容 resize，而不是把链表转换成红黑树。

• 转换的源码

  final void treeifyBin(Node[] tab, int hash) {
      int n, index; Node e;
      // 数组扩容
      if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
          resize();
      // 链表转换为红黑树
      else if ((e = tab[index = (n - 1) & hash]) != null) {
          TreeNode hd = null, tl = null;
          do {
              TreeNode p = replacementTreeNode(e, null);
              if (tl == null)
                  hd = p;
              else {
                  p.prev = tl;
                  tl.next = p;
              }
              tl = p;
          } while ((e = e.next) != null);
          if ((tab[index] = hd) != null)
              hd.treeify(tab);
      }
  }
  

• JDK 1.8 下 HashMap 的完整示意图

② HashMap在jdk8中相较于jdk7在底层实现方面的不同

• new HashMap():底层没创建一个长度为16的数组
• jdk 8底层的数组是：Node[],而非Entry[]
• 首次调用put()方法时，底层创建长度为16的数组
• jdk7底层结构只：数组+链表。jdk8中底层结构：数组+链表+红黑树。
  • 形成链表时，七上八下（jdk7:新的元素指向旧的元素。jdk8：旧的元素指向新的元素）
  • 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时，此时此索引位置上的所数据改为使用红黑树存储。
• 后续如果由于删除或者其他原因调整了大小，当红黑树的节点小于或等于 6 个以后，又会恢复为链表形态
• 1.7中新增节点采用头插法，1.8中新增节点采用尾插法。这也是为什么1.8不容易出现环型链表的原因
• 1.8rehash时保证原链表的顺序，而1.7中rehash时有可能改变链表的顺序（头插法导致）

③HashMap底层典型属性的属性的说明

• DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16
• DEFAULT_LOAD_FACTOR：HashMap的默认加载因子：0.75
• threshold：扩容的临界值，=容量*填充因子：16 * 0.75 => 12
• TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树:8
• MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量:64

④ 新的节点在插入链表的流程

在 JDK 1.7 的时候，采用的是头插法。不过 JDK 1.8 改成了尾插法。

原因：因为 JDK 1.7 中采用的头插法在多线程环境下可能会造成循环链表问题。

不断的插入节点，数组大小会不断增加。数组容量是有限的，如果数据多次插入并到达一定的数量就会进行数组扩容，也就是resize 方法。什么时候会进行 resize 呢？与两个因素有关：

1）Capacity：HashMap 当前最大容量/长度

2）LoadFactor：负载因子，默认值0.75f

static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int MIN_TREEIFY_CAPACITY = 64;
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;

如果当前存入的数据数量大于 Capacity * LoadFactor 的时候，就会进行数组扩容 resize。就比如当前的 HashMap 的最大容量大小为 100，当你存进第 76 个的时候，判断发现需要进行 resize了，那就进行扩容。

扩容的步骤：

1）扩容：创建一个新的 Entry/Node 空数组，长度是原数组的 2 倍

2）ReHash：遍历原 Entry/Node 数组，把所有的 Entry/Node 节点重新 Hash 到新数组

为什么要 ReHash 呢？直接复制到新数组不行吗？

​ 显然是不行的，因为数组的长度改变以后，Hash 的规则也随之改变。index 的计算公式是这样的：

​ index = HashCode(key) & (Length - 1)

​ 比如说数组原来的长度（Length）是 4，Hash 出来的值是 2 ，然后数组长度翻倍了变成 16，显然 Hash 出来的值也就会变了。

图例：

为啥 JDK 1.7 使用头插法，JDK 1.8 之后改成尾插法了呢？

jdk1.7的源码

newTable 就是扩容后的新数组，transfer 方法是 resize 的核心，它的的功能就是 ReHash，然后将原数组中的数据迁移到新数据。

简化transfer方法:

单线程情况下，正常的 resize 的过程

假设我们原来的数组容量为 2，记录数为 3，分别为：[3,A]、[7,B]、[5,C]，并且这三个 Entry 节点都落到了第二个桶里面，新数组容量会被扩容到 4。

如果我们有两个线程 Thread1 和 Thread2，假设线程 Thread1 执行到了 transfer 方法的 Entry next = e.next 这一句，然后时间片用完了被挂起了。随后线程 Thread2 顺利执行并完成 resize 方法。于是我们有下面这个样子：

注意，Thread1 的 e 指向了 [3,A]，next 指向了 [7,B]，而在线程 Thread2 进行 ReHash后，e 和 next 指向了线程 Thread2 重组后的链表。我们可以看到链表的顺序被反转了。

这个时候线程 Thread1 被重新调度执行，先是执行 newTalbe[i] = e，i 就是 ReHash 后的 index 值：

然后执行 e = next，导致了 e 指向了 [7,B]，而下一次循环执行到 next = e.next 时导致了 next 指向了 [3,A]

然后，线程 Thread1 继续执行。把旧数组的 [7,B] 摘下来，放到 newTable[i] 的第一个，然后把 e 和 next 往下顺移：

OK，Thread1 再进入下一步循环，执行到 e.next = newTable[i]，导致 [3,A].next 指向了 [7,B]，循环链表出现

由于 JDK 1.7 中 HashMap 使用头插会改变链表上元素的的顺序，在旧数组向新数组转移元素的过程中修改了链表中节点的引用关系，因此 JDK 1.8 改成了尾插法，在扩容时会保持链表元素原本的顺序，避免了链表成环的问题。

⑤ HashMap和HashTable 的异同

• 二者的存储结构和解决冲突的方法都是相同的。
• HashTable在不指定容量的情况下的默认容量为11，而HashMap为16，Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。
• HashTable 中 key和 value都不允许为 null，而HashMap中key和value都允许为 null（key只能有一个为null，而value则可以有多个为 null）。但是如果在 Hashtable中有类似 put( null, null)的 *** 作，编译同样可以通过，因为 key和 value都是Object类型，但运行时会抛出 NullPointerException异常。
• Hashtable扩容时，将容量变为原来的2倍+1，而HashMap扩容时，将容量变为原来的2倍。
• Hashtable计算hash值，直接用key的hashCode()，而HashMap重新计算了key的hash值，Hashtable在计算hash值对应的位置索引时，用 %运算，而 HashMap在求位置索引时，则用 &运算。

⑥ 优化HashMap

初始化 HashMap 的时候，我们可以自定义数组容量及加载因子的大小。所以，优化 HashMap 从这两个属性入手，但是，如果你不能准确的判别你的业务所需的大小，请使用默认值，否则，一旦手动配置的不合适，效果将适得其反。

threshold = (int)( capacity * loadFactor );

阈值 = 容量 X 负载因子

初始容量默认为16,负载因子(loadFactor)默认是0.75; map扩容后，要重新计算阈值；当元素个数 大于新的阈值时，map再自动扩容；以默认值为例，阈值=16*0.75=12，当元素个数大于12时就要扩容；那剩下的4个数组位置还没有放置对象就要扩容，造成空间浪费，所以要进行时间和空间的折中考虑；

• loadFactor过大时，map内的数组使用率高了，内部极有可能形成Entry链，影响查找速度；

• loadFactor过小时，map内的数组使用率较低，不过内部不会生成Entry链，或者生成的Entry链很短，由此提高了查找速度，不过会占用更多的内存；所以可以根据实际硬件环境和程序的运行状态来调节loadFactor；

所以，务必合理的初始化 HashMap

⑦ HashMap有关的问题 1、HashMap 的默认初始数组长度是多少？为什么是这么多？

默认数组长度是 16，其实只要是 2 的次幂都行，至于为啥是 16 呢，我觉得应该是个经验值问题，Java 作者是觉得 16 这个长度最为常用。

那为什么数组长度得是 2 的次幂呢？

首先，一般来说，我们常用的 Hash 函数是这样的：index = HashCode(key) % Length，但是因为位运算的效率比较高嘛，所以 HashMap 就相应的改成了这样：index = HashCode(key) & (Length - 1)。

那么为了保证根据上述公式计算出来的 index 值是分布均匀的，我们就必须保证 Length 是 2 的次幂。

解释一下：2 的次幂，也就是 2 的 n 次方，它的二进制表示就是 1 后面跟着 n 个 0，那么 2 的 n 次方 - 1 的二进制表示就是 n 个 1。而对于 & *** 作来说，任何数与 1 做 & *** 作的结果都是这个数本身。也就是说，index 的结果等同于 HashCode(key) 后 n 位的值，只要 HashCode 本身是分布均匀的，那么我们这个 Hash 算法的结果就是均匀的。

2、以 HashMap 为例，解释一下为什么重写 equals 方法的时候还需要重写 hashCode 方法呢？

既然讲到 equals 了，那就先顺便回顾下运算符 == 的吧，它存在两种使用情况：

• 对于基本数据类型来说， == 比较的是值是否相同；
• 对于引用数据类型来说， == 比较的是内存地址是否相同。

equals()也存在两种使用情况：

• 情况 1：没有重写 equals() 方法。则通过 equals() 比较该类的两个对象时，等价于通过 == 比较这两个对象（比较的是地址）。
• 情况 2：重写 equals() 方法。一般来说，我们都会重写 equals() 方法来判断两个对象的内容是否相等，比如 String 类就是这样做的。当然，你也可以不这样做。

另外，我们还需要明白，如果我们不重写 hashCode()，那么任何对象的 hashCode() 值都不会相等。

OK，回到问题，为什么重写 equals 方法的时候还需要重写 hashCode 方法呢？

以 HashMap 为例，HashMap 是通过 hashCode(key) 去计算寻找 index 的，如果多个 key 哈希得到的 index 一样就会形成链表，那么如何在这个具有相同 hashCode 的对象链表上找到某个对象呢？

那就是通过重写的 equals 比较两个对象的值。

总体来说，HashMap 中get(key) 一个元素的过程是这样的，先比较 key 的 hashcode() 是否相等，若相等再通过 equals() 比较其值，若 equals() 相等则认为他们是相等的。若 equals() 不相等则认为他们不相等。

如果只重写 equals 没有重写 hashCode()，就会导致相同的对象却拥有不同的 hashCode，也就是说在判断的第一步 HashMap 就会认为这两个对象是不相等的，那显然这是错误的。

3、HashMap 线程不安全的表现有哪些？

关于 JDK 1.7 中 HashMap 的线程不安全，上面已经说过了，就是会出现环形链表。虽然 JDK 1.8 采用尾插法避免了环形链表的问题，但是它仍然是线程不安全的，我们来看看 JDK 1.8 中 HashMap 的 put 方法：

假设线程 1 和线程 2 同时进行 put *** 作，恰好这两条不同的数据的 hash 值是一样的，并且该位置数据为null，这样，线程 1 和线程 2 都会进入这段代码进行插入元素。假设线程 1 进入后还没有开始进行元素插入就被挂起，而线程 2 正常执行，并且正常插入数据，随后线程 1 得到 CPU 调度进行元素插入，这样，线程 2 插入的数据就被覆盖了。

总结一下 HashMap 在 JDK 1.7 和 JDK 1.8 中为什么不安全：

• JDK 1.7：由于采用头插法改变了链表上元素的的顺序，并发环境下扩容可能导致循环链表的问题
• JDK 1.8：由于 put *** 作并没有上锁，并发环境下可能发生某个线程插入的数据被覆盖的问题

4、如何保证 HashMap 线程安全？

1）使用 java.util.Collections 类的 synchronizedMap 方法包装一下 HashMap，得到线程安全的 HashMap，其原理就是对所有的修改 *** 作都加上 synchronized。方法如下：

public static  Map synchronizedMap(Map m)

2）使用线程安全的 HashTable 类代替，该类在对数据 *** 作的时候都会上锁，也就是加上 synchronized

3）使用线程安全的 ConcurrentHashMap 类代替，该类在 JDK 1.7 和 JDK 1.8 的底层原理有所不同，JDK 1.7 采用数组 + 链表存储数据，使用分段锁 Segment 保证线程安全；JDK 1.8 采用数组 + 链表/红黑树存储数据，使用 CAS + synchronized 保证线程安全。

5、 HashMap底层为什么是2倍扩容？

   static final int tableSizeFor(int cap) {
       int n = cap - 1;
       n |= n >>> 1;
       n |= n >>> 2;
       n |= n >>> 4;
       n |= n >>> 8;
       n |= n >>> 16;
       return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
   }

第一是因为哈希函数的问题
通过除留余数法方式获取桶号，因为Hash表的大小始终为2的n次幂，因此可以将取模转为位运算 *** 作，提高效率，容量n为2的幂次方，n-1的二进制会全为1，位运算时可以充分散列，避免不必要的哈希冲突，这也就是为什么要按照2倍方式扩容的一个原因

第二是因为是否移位的问题
是否移位，由扩容后表示的最高位是否1为所决定，并且移动的方向只有一个，即向高位移动。因此，可以根据对最高位进行检测的结果来决定是否移位，从而可以优化性能，不用每一个元素都进行移位，因为为0说明刚好在移位完之后的位置，为1说明不是需要移动oldCop，这也是其为什么要按照2倍方式扩容的第二个原因。

本文参考文章https://www.kuangstudy.com/bbs/1383265607989891074，且加上自己的见解