Java - HashMap底层原理

一、对比

1、底层实现差异

📊 JDK 7 vs JDK 8 HashMap 底层实现差异

2、关键差异

1. 数据结构与红黑树的引入
这是最根本的变化。JDK 7 在哈希冲突严重时，链表会退化为 O(n) 的线性查询。JDK 8 引入红黑树，将最坏情况下的查询复杂度从 O(n) 降至 O(log n)，以应对哈希函数设计不佳或恶意哈希攻击的场景。

2. 插入方式的改变与死循环问题
JDK 7 的头插法在并发扩容时，可能使链表形成环，导致get()操作陷入死循环。JDK 8 的尾插法在扩容时能保持链表元素的相对顺序，从根本上避免了成环问题。

3. 扩容机制的优化
JDK 7 扩容需要对每个节点重新计算哈希和索引（rehash），开销较大。JDK 8 利用容量为 2 的幂这一特性，只需判断hash值在扩容后新增的那一位是 0 还是 1：为 0 则索引不变，为 1 则新索引为“原索引 + 旧容量”，无需重新计算哈希，显著提升效率。

4. 树化与退化的阈值设计
树化需要同时满足链表长度 ≥ 8 和数组容量 ≥ 64。如果容量不足 64，会优先选择resize()扩容，因为扩容本身就能有效打散冲突，比直接树化的成本更低。退化阈值设为 6（而非 7）是为了在 7 和 8 之间留出缓冲区，避免节点数在临界值附近波动时，引发链表与红黑树之间频繁的无效转换。

红黑树是一种自平衡二叉搜索树：它给节点染红/黑两色，遵守"根黑、叶黑、红不连红、黑高相等"五条性质，通过变色 + 旋转在插入/删除后自动修复，保证树高始终 ≤ 2log(n+1)，从而让查找、插入、删除都稳定在 O(log n)。

二、JDK8及之后

1、结构图（数组+链表+红黑树）

🥽JDK8图解

2、PUT步骤详解

1、进行hash扰动，调用putVal(hash(key), key, value, false,true);2、if 桶数组table 为 null 或 tab.length==0，调用 resize()进行初始化3、if 桶数组tab[i]的头节点P是否为空，i=(n -1)&hashtab[i]的头节点P为空直接插入，tab[i]=newNode(hash, key, value, null);4、else ：桶数组tab[i]的头节点P不为空， if：头节点 p 是否就是我们要找的 key，p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k)))e=p;elseif：该桶已经树化（红黑树） 调用 putTreeVal 在树里查找，找到返回该节点赋给 e； 没找到，putTreeVal会插入新节点并返回 nullelse普通链表，则遍历链表查找for遍历节点if((e=p.next)==null)，尾节点指向null 遍历没找到，插入：p.next=newNode(hash,key,value,null);尾插后若 binCount>=7，调用 treeifyBin； 内部再判数组长度 ≥64才真正树化，否则扩容 break跳出循环 过程中发现某个节点 e 的 key 与待插入 key 相同 if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))找到目标，break跳出循环ife!=null，说明 key 已经存在（在头节点、红黑树或链表中找到了） 进行覆盖，并返回5、上述未返回，说明是新增节点 元素个数加一；如果超过阈值 threshold，则调用resize()扩容 节点插入，新增场景返回 null（表示之前没有这个 key）

3、PUT底层代码

/** * 方法：HashMap 对外暴露的 put 入口。 * 作用：把 key-value 放入 map；如果 key 已存在，则覆盖旧值并返回旧值，不存在则返回 null。 * 参数：key——键，value——值 * 返回：旧值（key 之前存在）或 null（key 之前不存在） */publicVput(Kkey,Vvalue){// hash(key) ：先对 key 做扰动运算，得到更均匀的 hash，减少哈希冲突// putVal(...) ：真正执行插入/覆盖逻辑// 参数 4 = false ：onlyIfAbsent=false，表示 key 已存在时允许覆盖旧值// 参数 5 = true ：evict=true，表示不是初始化建表模式（供 LinkedHashMap 等子类回调使用）returnputVal(hash(key),key,value,false,true);}/** * 方法：真正实现 put 及 putIfAbsent、compute、merge 等方法的公共逻辑。 * * @param hash key 经过扰动后的哈希值 * @param key 键 * @param value 值 * @param onlyIfAbsent 为 true 时，若 key 已存在且旧值不为 null，则不覆盖（putIfAbsent 用） * @param evict 为 false 时表示表处于创建模式（子类 afterNodeInsertion 回调会用到） * @return 旧值；key 原本不存在时返回 null */finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){// tab：桶数组引用；Node<K,V>[]tab;//p：当前定位到的桶的头节点；Node<K,V>p;//n：数组长度；i：桶下标intn,i;// ① 如果 table 还没初始化（null）或长度为 0，先调用 resize() 完成初始化/扩容// resize() 返回新数组，n 记录新数组长度if((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;// ② 用 (n - 1) & hash 计算桶下标 i（等价于 hash % n，因为 n 是 2 的幂，位运算更快）// 如果该桶为空（p == null），说明没有冲突，直接新建节点挂上去if((p=tab[i=(n-1)&hash])==null)tab[i]=newNode(hash,key,value,null);// 无冲突，直接插入// ③ 桶不为空，说明发生了哈希冲突，需要进一步查找else{// e：用来指向"已存在的那个节点"；Node<K,V>e;//k：临时存放节点 keyKk;// 3.1 先检查桶的头节点 p 是否就是我们要找的 key// 判断条件：// - 头节点 p的hash 相同（快速过滤）// - 头节点 p的key（==，同一对象）入参key 引用相同。 或 key 内容相等（equals）if(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))e=p;// 头节点就是目标 key// 3.2 头节点不是，且该桶已经树化（红黑树），交给 TreeNode 处理elseif(pinstanceofTreeNode)e=((TreeNode<K,V>)p).putTreeVal(this,tab,hash,key,value);// 3.3 头节点不是，且是普通链表，则遍历链表查找else{// binCount 记录遍历过的节点数，用于判断是否要树化for(intbinCount=0;;++binCount){// 走到链表末尾还没找到 key → 说明是新 key，在尾部追加新节点// （JDK 8 采用尾插法；JDK 7 是头插法）if((e=p.next)==null){p.next=newNode(hash,key,value,null);// 链表长度达到 TREEIFY_THRESHOLD - 1（默认 8 - 1 = 7，// 加上头节点即第 8 个节点）时，尝试把链表转成红黑树// 注意 treeifyBin 内部还会判断数组长度是否 >= MIN_TREEIFY_CAPACITY(64)，// 不满足则优先扩容而不是树化if(binCount>=TREEIFY_THRESHOLD-1)// -1 because binCount starts at 0treeifyBin(tab,hash);break;// 新节点已插入，跳出循环}// 遍历过程中发现某个节点 e 的 key 与待插入 key 相同 → 找到目标，跳出循环if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))break;// 否则继续向后遍历p=e;}}// ④ 如果 e != null，说明 key 已经存在（在头节点、红黑树或链表中找到了）if(e!=null){// existing mapping for keyVoldValue=e.value;// 记下旧值，用于返回// 只有满足以下任一条件才覆盖旧值：// - onlyIfAbsent == false（普通 put，允许覆盖）// - 旧值为 null（putIfAbsent 场景，null 也视为可覆盖）if(!onlyIfAbsent||oldValue==null)e.value=value;// 节点被访问后的回调，HashMap 是空实现，LinkedHashMap 用它维护访问顺序（LRU）afterNodeAccess(e);returnoldValue;// 返回旧值（覆盖成功）}}// ⑤ 走到这里说明是新增节点（不是覆盖），做收尾工作// modCount++：记录结构性修改次数，用于迭代器 fail-fast 检测并发修改++modCount;// size++：元素个数加一；如果超过阈值 threshold，则触发扩容if(++size>threshold)resize();// 节点插入后的回调，HashMap 是空实现，LinkedHashMap 用它维护插入顺序afterNodeInsertion(evict);// 新增场景返回 null（表示之前没有这个 key）returnnull;}

三、JDK7及之前

1、结构图（数组+链表）

⚽JDK7图解

JDK7数组+链表图解

数组 table ┌────┬────┬────┬────┬────┐ │0│1│2│3│4│... ├────┼────┼────┼────┼────┤ │null│null│null│ ● │null│ └────┴────┴────┴─┼──┴────┘ │ ▼ ┌───────────────────┐ │ Node1 │ ← 一个完整键值对 │hash=h1 │ │key="apple"│ │value=100│ │ next ────────┐ │ └──────────────┼────┘ │ ▼ ┌───────────────────┐ │ Node2 │ ← 一个完整键值对 │hash=h2 │ │key="banana"│ │value=200│ │ next ────────┐ │ └──────────────┼────┘ │ ▼ ┌───────────────────┐ │ Node3 │ ← 一个完整键值对 │hash=h3 │ │key="cherry"│ │value=300│ │ next=null │ └───────────────────┘

2、PUT步骤详解

首次 put → table==EMPTY_TABLE 初始化数组； null key → putForNullKey 单独处理，固定0号桶； //计算桶下标：内部等价于hash&(table.length -1)int i=indexFor(hash, table.length);遍历链表找 Entry<K,V>e=table[i]→if(e.hash==hash&&((k=e.key)==key||key.equals(k)))命中则覆盖 value、回调、返回旧值； 没找到 将新节点加入桶 i 对应的链表；JDK7的 addEntry 内部使用头插法、返回 null。

3、PUT底层代码

/* * JDK 7 HashMap.put 源码 */publicVput(Kkey,Vvalue){// 第一次 put 时 table 仍是 EMPTY_TABLE，需要先初始化数组if(table==EMPTY_TABLE){// 按 threshold 初始化底层 Entry 数组inflateTable(threshold);}// HashMap 允许 null key，null key 单独处理，固定放入 0 号桶if(key==null)// 在 0 号桶中查找 null key：存在则覆盖并返回旧值，不存在则新增并返回 nullreturnputForNullKey(value);// 对 key.hashCode() 做扰动，让高位参与桶下标计算，减少碰撞inthash=hash(key);// 计算桶下标：内部等价于 hash & (table.length - 1)inti=indexFor(hash,table.length);// 从桶 i 的头节点开始遍历链表，e 为当前节点for(Entry<K,V>e=table[i];e!=null;e=e.next){// 暂存当前节点的 key，便于后续比较Objectk;// 先比较 hash 快速过滤，再比较 key 引用或内容，判断是否命中目标 keyif(e.hash==hash&&((k=e.key)==key||key.equals(k))){// 命中已存在的 key：保存旧 value 用于返回VoldValue=e.value;// 用新 value 覆盖旧 value；key 和 hash 是 final，不会改变e.value=value;// 回调钩子：HashMap 为空实现，LinkedHashMap 用于维护访问顺序e.recordAccess(this);// 覆盖场景返回旧值returnoldValue;}}// 走到这里说明链表中没有找到相同 key，属于新增节点// modCount 自增，供迭代器 fail-fast 检测结构性修改modCount++;// 将新节点加入桶 i 对应的链表；JDK 7 的 addEntry 内部使用头插法addEntry(hash,key,value,i);// 新增场景没有旧值，返回 nullreturnnull;}