HashMap 源码深度解析合集 - Java高频面试精选(7)1.LinkedList 插入真的是 O(1) 吗？深度解析 Java 双向链表的性能陷阱与源码真相04-192.HashM

为什么 HashMap 是 Java 中最常用、最重要的数据结构核心原因就一个性能。常见的基础数据结构中数组查询快但插入删除慢链表插入快但查询慢。HashMap 综合了数组和链表的优点将查询与插入的效率都控制在近似 O(1) 的复杂度内。但 HashMap 的设计远不止于此。容量为什么是 2 的幂哈希扰动函数spread()如何防止哈希冲突链表转红黑树的阈值为什么选 8本文将从源码级别逐一揭示这些设计背后的原理。学完本文你将掌握HashMap 的底层实现原理数组 链表 红黑树put 方法的完整执行流程与哈希扰动算法扩容机制与 2 倍扩容的根本原因HashMap 为什么线程不安全并发下会产生什么事故HashMap 的容量为什么必须是 2 的幂HashMap 在 Java 8 版本中做了哪些变更简介HashMap 的底层数据结构由数组、链表和红黑树组成核心是基于数组实现的。为了解决哈希冲突采用拉链法于是引入了链表结构。为了解决链表过长导致的查询性能下降Java 8 引入了红黑树结构。HashMap 类中有两个关键的阈值常量TREEIFY_THRESHOLD 8当链表长度达到 8 时链表会转换为红黑树UNTREEIFY_THRESHOLD 6当红黑树节点数减少到 6 时红黑树会退化为链表MIN_TREEIFY_CAPACITY 64只有数组容量达到 64 时才会触发树化否则优先扩容数组而不是树化这三个常量配合使用目的是避免频繁的树化和退化操作。如果链表只是短暂变长不会触发树化如果红黑树只是短暂变小不会立即退化。 核心提示为什么树化阈值是 8、退化阈值是 6这背后有统计学依据。HashMap 中节点的分布服从泊松分布Poisson Distribution。在理想的 hash 散列下链表长度达到 8 的概率约为 0.00000006千万分之六几乎不可能自然发生。如果达到了 8说明 hash 冲突严重此时用红黑树代替链表可以将 O(n) 退化为 O(log n)。退化为 6 是为了留出缓冲区间8→6避免在临界值附近频繁树化/退化这就是所谓的迟滞效应Hysteresis。HashMap 类架构图containsimplementsimplements«abstract»AbstractMapcontainsKey(Object) : booleancontainsValue(Object) : booleanisEmpty() : booleansize() : intclear() : void«interface»Mapput(K, V) : Vget(Object) : Vremove(Object) : VcontainsKey(Object) : booleancontainsValue(Object) : booleanentrySet() : SetEntrykeySet() : SetKvalues() : CollectionVHashMap-transient Node[] table-transient int size-transient int threshold-transient int modCount-final float loadFactorput(K, V) : Vget(Object) : Vremove(Object) : Vresize() : Node[]-hash(Object) : int-putVal(int, K, V, boolean, boolean) : V-getNode(int, Object) : Node-treeifyBin(Node[], int) : void-tableSizeFor(int) : intLinkedHashMap-transient Entry head-transient Entry tail-final boolean accessOrderNodefinal int hashfinal K keyV valueNode nextgetKey() : KgetValue() : VsetValue(V) : VTreeNodeTreeNode parentTreeNode leftTreeNode rightTreeNode prevboolean redputTreeVal(HashMap, Node[], int, K, V) : TreeNodegetTreeNode(int, Object) : TreeNoderemoveTreeNode(HashMap, Node[], boolean) : voidsplit(HashMap, Node[], int, int) : void«interface»Cloneable«interface»SerializableHashMap 的核心工作原理可以用下面的流程图概括是否是否是否红黑树链表是是否否是否是否初始化: tablenull, size0, threshold0put(key, value)hash(key): h key.hashCode()\n返回 h ^ (h 16)table 为空?resize(): 初始化数组\n容量16 或 tableSizeFor(指定容量)计算下标: i (n - 1) hashtab[i] 是否为空?直接插入新节点key 是否已存在?覆盖旧值, 返回旧值节点类型?putTreeVal: 红黑树插入遍历链表, 尾插法追加链表长度 8?数组容量 64?treeifyBin: 链表转红黑树resize(): 扩容数组size threshold?resize(): 容量翻倍\n链表拆分为低位/高位两条链表modCount, size, 返回nullget(key)hash(key) 计算哈希值计算下标: (n-1) hash找到 key?返回 value返回 null类属性再看一下 HashMap 类中有哪些关键属性public class HashMapK, V extends AbstractMapK, V implements MapK, V, Cloneable, Serializable { /** * 默认容量大小1 4 16 */ static final int DEFAULT_INITIAL_CAPACITY 1 4; /** * 负载系数容量超过 threshold capacity * loadFactor 时触发扩容 * 默认 16 * 0.75 12 个元素时扩容 */ static final float DEFAULT_LOAD_FACTOR 0.75f; /** * 容量最大值2 的 30 次方 */ static final int MAXIMUM_CAPACITY 1 30; /** * 链表转红黑树的阈值链表长度 8 时树化 */ static final int TREEIFY_THRESHOLD 8; /** * 红黑树退化为链表的阈值节点数 6 时退化 */ static final int UNTREEIFY_THRESHOLD 6; /** * 树化的最小数组容量只有 table 容量 64 才会树化 */ static final int MIN_TREEIFY_CAPACITY 64; /** * 存储元素的数组容量始终为 2 的幂 */ transient NodeK, V[] table; /** * 实际存储的键值对数量 */ transient int size; /** * 扩容阈值当 size threshold 时触发扩容 */ transient int threshold; /** * 结构修改次数用于 fail-fast 机制 */ transient int modCount; }其中Node是链表的节点static class NodeK, V implements Map.EntryK, V { final int hash; // 哈希值缓存避免重复计算 final K key; // 键 V value; // 值 NodeK, V next; // 后继节点 Node(int hash, K key, V value, NodeK, V next) { this.hash hash; this.key key; this.value value; this.next next; } }以及红黑树的节点TreeNode继承自LinkedHashMap.Entry本质是Node的子类static final class TreeNodeK, V extends LinkedHashMap.EntryK, V { TreeNodeK, V parent; // 父节点 TreeNodeK, V left; // 左子节点 TreeNodeK, V right; // 右子节点 TreeNodeK, V prev; // 前驱节点继承自 LinkedHashMap.Entry boolean red; // 节点颜色 TreeNode(int hash, K key, V val, NodeK, V next) { super(hash, key, val, next); } }初始化HashMap 常见的初始化方法有两个无参初始化有参初始化指定容量大小/** * 无参初始化 */ MapInteger, Integer map new HashMap(); /** * 有参初始化指定容量大小 */ MapInteger, Integer map new HashMap(10);再看一下构造方法的底层实现/** * 无参初始化 */ public HashMap() { this.loadFactor DEFAULT_LOAD_FACTOR; } /** * 有参初始化指定容量大小 */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * 有参初始化指定容量大小和负载系数 */ public HashMap(int initialCapacity, float loadFactor) { // 校验参数 if (initialCapacity 0) { throw new IllegalArgumentException(Illegal initial capacity: initialCapacity); } if (initialCapacity MAXIMUM_CAPACITY) { initialCapacity MAXIMUM_CAPACITY; } if (loadFactor 0 || Float.isNaN(loadFactor)) { throw new IllegalArgumentException(Illegal load factor: loadFactor); } this.loadFactor loadFactor; // 计算出合适的容量大小2的幂 this.threshold tableSizeFor(initialCapacity); }可以看出无参构造方法只初始化了负载系数。指定容量大小的有参构造方法也只是初始化了负载系数和threshold扩容阈值两个方法都没有初始化数组大小。tableSizeFor方法会将传入的容量值转换为大于等于它的最小的 2 的幂。例如tableSizeFor(10)返回 16tableSizeFor(20)返回 32。这个方法实现非常精妙/** * 返回大于等于 cap 的最小的 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; } 核心提示tableSizeFor方法为什么先cap - 1如果不减 1当 cap 本身就是 2 的幂时比如 16结果会变成 32导致浪费一半空间。减 1 保证了 恰好等于 2 的幂 时不会翻倍。而右移 或运算的组合能将最高位 1 右侧的所有位都填充为 1最后 1 就是下一个 2 的幂。如果再有面试官问你HashMap 初始化的时候数组大小是多少答案是0或者说未初始化因为 HashMap 采用了懒加载策略数组在第一次put时才会通过resize()方法初始化。深入 hash 算法在深入 put 方法之前先看一下 HashMap 的hash()方法static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }这个方法做了两件事如果 key 为 null返回 0HashMap 允许 null 作为 key否则取 key 的hashCode()然后将其无符号右移 16 位再与原值做异或运算为什么要这样做HashMap 计算数组下标用的是(n - 1) hash其中 n 是数组容量2 的幂。当 n 较小时比如 16n - 1只有低 4 位是 1高位都是 0这意味着运算只会用到 hash 的低位。如果不同 key 的 hashCode 只有高位不同、低位相同就会产生哈希冲突。通过右移 16 位再异或把高位的信息混入低位让高位也参与下标计算从而减少哈希冲突。 核心提示为什么选择右移 16 位因为 int 是 32 位右移 16 位恰好将高 16 位与低 16 位对齐异或后高低位的信息混合在一起。这是一个在性能和散列质量之间的权衡更多次的混合比如多次右移异或可以提高散列质量但会降低性能16 位一次的混合在实践中已足够好。put 源码put 方法的流程如下计算 key 的 hash 值如果数组为空调用resize()初始化根据(n - 1) hash计算数组下标如果下标位置为空直接插入如果下标位置不为空判断 key 是否已存在存在则覆盖如果是红黑树节点执行红黑树插入如果是链表节点遍历链表尾插长度达到 8 时树化如果size threshold调用resize()扩容put 方法详细流程图是否是否是否是否是是否否是否put(key, value)hash(key) 计算扰动后的哈希值table 是否为空?resize() 初始化数组i (n-1) hash 计算下标tab[i] null?tab[i] newNode() 直接插入p.hash hash key匹配?e p 记录待覆盖节点p instanceof TreeNode?putTreeVal() 红黑树插入遍历链表尾插binCount 7?table.length 64?treeifyBin() 链表转红黑树resize() 扩容数组size threshold?覆盖旧值, 返回旧值resize() 扩容modCount, size, 返回null返回旧值put 源码详解再看一下 put 方法的具体源码实现/** * put 方法入口 */ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /** * 计算 hash 值高位和低位都参与计算 */ static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); } /** * 实际的put方法逻辑 * param hash key对应的hash值 * param key 键 * param value 值 * param onlyIfAbsent 如果为true则只有当key不存在时才会put否则会覆盖 * param evict 如果为false表处于创建模式 * return 返回旧值 */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { NodeK, V[] tab; NodeK, V p; int n, i; // 1. 如果数组为空则执行初始化resize 同时负责初始化和扩容 if ((tab table) null || (n tab.length) 0) { n (tab resize()).length; } // 2. 如果 key 对应下标位置元素不存在直接插入即可 if ((p tab[i (n - 1) hash]) null) { tab[i] newNode(hash, key, value, null); } else { NodeK, V e; K k; // 3. 如果头节点 key 匹配直接结束后续判断是否需要覆盖 if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) { e p; } else if (p instanceof TreeNode) { // 4. 判断下标位置的元素类型如果是红黑树则执行红黑树的插入逻辑 e ((TreeNodeK, V) p).putTreeVal(this, tab, hash, key, value); } else { // 5. 否则执行链表的插入逻辑 for (int binCount 0; ; binCount) { // 6. 遍历链表直到找到空位置为止 if ((e p.next) null) { // 7. 创建一个新的链表节点并追加到末尾尾插法 p.next newNode(hash, key, value, null); // 8. 如果链表长度达到 8则转换为红黑树 if (binCount TREEIFY_THRESHOLD - 1) { treeifyBin(tab, hash); } break; } // 9. 如果在链表中找到相同的 key则结束 if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) { break; } p e; } } // 10. 判断是否需要覆盖旧值 if (e ! null) { V oldValue e.value; if (!onlyIfAbsent || oldValue null) { e.value value; } afterNodeAccess(e); return oldValue; } } modCount; // 11. 判断是否需要扩容 if (size threshold) { resize(); } afterNodeInsertion(evict); return null; }其中treeifyBin方法负责将链表转换为红黑树但只有在数组容量达到MIN_TREEIFY_CAPACITY64时才会真正树化否则只是扩容数组final void treeifyBin(NodeK, V[] tab, int hash) { int n, index; NodeK, V e; // 如果数组容量 64优先扩容而不是树化 if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY) { resize(); } else if ((e tab[index (n - 1) hash]) ! null) { // 否则将链表转换为红黑树 TreeNodeK, V hd null, tl null; // 遍历链表将所有 Node 替换为 TreeNode do { TreeNodeK, V p new TreeNode(e.hash, e.key, e.value, null); if (tl null) { hd p; } else { p.prev tl; tl.next p; } tl p; } while ((e e.next) ! null); // 将 TreeNode 双向链表构造成红黑树 if ((tab[index] hd) ! null) { hd.treeify(tab); } } }