Map源码会问哪些面试题

Map 整体数据结构类问题

说一说 HashMap 底层数据结构

JDK1.8，HashMap底层是数组 + 链表 + 红黑树的数据结构。数组的主要作用是方便快速查找，时间复杂度为 O(1)，默认大小为16，数组的下标索引是通过 key 的 hashcode 计算出来的，数组的元素叫做 Node，当不同的 key 的 hashcode 相同时（hash冲突），Node 会转换成链表，链表的查询复杂度的 O(n)，当链表的长度大于等于 8 并且数组的大小大于等于 64 时，链表会进化成红黑树，红黑树的查询时间复杂度为 O(log(n))，简单来说，最坏的查询次数相当于红黑树的最大深度。

HashMap、TreeMap、LinkedHashMap 三者有啥相同点，有啥不同点？

相同点：

• 三者在特定的情况下，都会使用红黑树
• 底层的 hash 算法相同
• 在迭代的过程中，如果 Map 的数据结构被改动，都会抛出 ConcurrentModificationException

不同点：

• HashMap 的数据结构以数组为主，查询非常快

• TreeMap 的数据结构以红黑树为主，利用了红黑树左小右大的特点，可以实现 key 的排序

• LinkedHash 继承了HashMap，增加了链表的结构，实现了插入顺序有序和 LRU 算法

• 由于三种 Map 底层数据结构的差别，导致了三者的使用场景的不同，

  • TreeMap 适合需要根据 key 进行排序的场景
  • LinkedHashMap 适合按照插入顺序访问，或需要删除最少访问元素的场景
  • 剩余场景我们使用 HashMap 即可，我们工作中大部分场景基本都在使用 HashMap

说一下 HashMap 的 hash 算法

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

key 在数组中的位置公式：tab[(n - 1) & hash]

HashMap 通过以上代买来计算 hash 的，首先计算出 key 的 hashcode，接着计算 h ^ (h >>> 16)，这样做的好处是使大多数场景下，算出来的 hash 值比较分散。

此问题可以延伸出三个小问题：

• 为什么不用 key % 数组大小，而是需要用 key 的 hash 值 % 数组大小

  如果 key 是数字，直接用 key % 数组大小是没有问题的，但我们的 key 还有可能是字符串，是复杂对象，这个时候用字符串或复杂对象 % 数组大小是不行的，所以需要先计算出 key 的 hash 值

• 计算 hash 值时，为什么需要右移16位？

  hash 算法是 h ^ (h >>> 16)，是为了使计算出来的 hash 值更分散，所以选择先将 h 无符号右移 16 位，然后再与 h 异或时，就能达到 h 的高 16 位和低 16 位都能参与计算，减少了碰撞的可能性。

• 为什么把取模操作换成了 & 操作

  key.hashCode() 算出来的 hash 值还不是数组的索引下标，为了随机的计算出索引的下标位置，我们还会用 hash 值和数组大小进行取模，这样子计算出来的索引下标比较均匀分布。

  取模操作处理器计算比较慢，处理器对 & 操作就比较擅长，换成了 & 操作，是有数学上证明的支撑，为了提高了处理器处理的速度。

• 为什么提倡数组的大小是 2 的幂次方

  因为只有大小是 2 的幂次方时，才能使 hash % n == (n -1) & hash 公式成立

HashMap 源码细节类问题

HashMap 是如何扩容的

扩容的时机：

• put 时，发现数组为空，进行初始化扩容，默认扩容大小为16
• put 成功后，发现数组大小大于扩容的阈值时，进行扩容，扩容后大小为原来的2倍

扩容阈值（threshold）等于数组大小 * 负载因子（load factor，默认 0.75），

新数组初始化之后，需要将老数组的值拷贝到新数组上，链表和红黑树都有自己拷贝的方法。

hash 冲突时怎么办

hash 冲突指的是 key 值的 hashcode 计算相同，但 key 值不同的情况。

• 如果桶中元素原本只有一个或已经是链表了，新增元素直接追加到链表尾部
• 如果桶中元素已经是链表，并且链表节点数大于等于 8 时：
  • 数组大小小于 64，数组会扩容，链表不会转换成红黑树
  • 数组大小大于等于 64 时，链表会进化为红黑树