本文记录下 Map 最常用的实现类 HashMap 相关的高频的面试知识点。

HashMap 的底层数据结构

数组 + 链表。结合了数组和链表二者的优点，利用数组可以在计算键的 hash 值以后快速的定位到所属位置，而当发生 hash 冲突（即两个键的 hash 值相等）时，又可以将元素以链表的形式存储。在 JDK 1.8 以后当链表的长度超过 8 且数组长度大于 64 以后会转变为红黑树。

HashMap 的工作原理

  • 根据 HashMap 的底层结构可以知道，要想确定一个键值对（K/V）的位置要对 K 进行 hash 运算，再结合当前数组长度确定一个下标
  • 如果计算出的下标没有元素（未发生 hash 冲突），那就依据当前的键值对构造一个 Node 放入数组中
  • 如果发生 hash 冲突时，先判断二者的 K 是否相等，如果相等说明是同一个元素，此时更新键值对的值即可
  • 如果 K 不相等，那就将当前元素插入到链表当中（JDK 1.7 是头插，1.8 是尾插）
  • 插入元素后判断当前数组的长度是否大于 capacity * loadfactor，如果大于，会对整个数组进行扩容，新的数组长度为 2 * capacity，之后对 HashMap 中的所有 K 重新进行 hash，确定在新数组中的位置

Hash 算法的实现

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

计算 K 的 hashCode 的高16位异或低16位的值，让高16位的值参与了 hash 运算，而且减少了 hash 冲突的概率

如何确定 table 的容量？loadFactor 又是什么？

  • table 数组的长度由 capacity 决定，默认值是16，最大值是 1 « 30
  • loadFactor 是负载因子，用于规定 table 数组是否需要扩容。默认的负载因子是 0.75

源码

为什么 HashMap 的底层数组长度为何总是 $2^n$

  • 如果不考虑这个问题的话，根据 hash 值计算下标通常是 hash % length，此时数组长度为多少都可以。但是数组的长度决定了 HashMap 的存取效率，于是开发人员就发现了当 length 为 $2^n$时 hash & （length - 1）= hash % length，因为位运算效率要比求模运算效率高，所以数组长度就一直保持在 $2^n$
  • 当使用了上述的计算公式时，如果数组长度不为 $2^n$ 时，length - 1 转换成2进制时最后一位为 0，在进行 & 运算时会造成空间浪费；而当长度为2的n次方时，计算的结果可以均匀的分配到数组的每一个位置

JDK1.7 和 JDK1.8 中的 HashMap 有什么不同

  • 底层数据结构不同，1.7 中是数组 + 链表，而在 1.8 中当链表的长度大于 8 且数组长度大于 64 时会转变为红黑树（小于 6 时会重新变回链表）
  • 在发生 hash 冲突时，1.7 中是插入到链表的头部，而 1.8 则是插入链表尾部

为什么 HashMap 是线程不安全的

  • put/get 操作并不是原子操作，多线程中可能会覆盖其他线程写入的值
  • 在 1.7 中头插法会修改链表元素的位置，导致产生环。当获取有环的元素时会造成死循环，在 1.8 中修改为尾插来避免这个问题