JAVA 集合框架- HashMap

HashMap 是 Java 中最常用的键值对存储容器它的底层数据结构在不同 Java 版本中有核心优化但核心设计思路是「数组 链表 / 红黑树」的组合目的是平衡查询、插入的效率。作为Java集合框架Map中最重要的 HashMap在面试中都快被问包浆了。HashMap的底层数据结构1. 哈希桶数组Node [] table这是 HashMap 的基础结构数组的每个元素被称为桶每个桶的初始类型是Node节点实现了Map.Entry接口结构如下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; } }数组的长度默认是 16且必须是 2 的幂次目的是通过hash (length-1)替代取模运算提升哈希计算效率。数组的扩容阈值默认是16 * 0.75 12负载因子 0.75当元素数量超过阈值时数组会扩容为原来的 2 倍。2. 链表解决哈希冲突当多个键经过哈希处理后得到相同的索引时需要通过链表来解决哈希冲突——将具有相同索引的键值对通过链表存储起来。例如键 A 和键 B 的哈希值计算后都指向数组下标 3那么下标 3 的桶会形成A - B的链表。链表的问题如果链表过长比如超过 8 个节点查询效率会从 O (1) 退化为 O (n)。3. 红黑树优化长链表Java 8 引入了红黑树来解决长链表的性能问题当某个桶的链表节点数≥ 8且数组长度≥ 64时链表会转为红黑树TreeNode 类型当红黑树的节点数≤ 6时会重新转回链表红黑树维护成本高短链表更高效红黑树的查询效率是 O (log n)远高于长链表的 O (n)。注意我一开始以为这个64是当前数组中元素的个数 实际上是数组的容量 一定要清楚树化需要满足两个核心阈值条件这俩缺一不可 仅仅满足链表长度是不能转换成红黑树的链表长度阈值冲突链表的节点数 ≥TREEIFY_THRESHOLD源码中固定为 8数组容量阈值哈希桶数组的长度 ≥MIN_TREEIFY_CAPACITY源码中固定为 64。下面是源码中treeifyBin方法的核心逻辑Java 8对应树化的判断流程final void treeifyBin(NodeK,V[] tab, int hash) { int n, index; NodeK,V e; // 第一步判断数组容量是否 ≥ MIN_TREEIFY_CAPACITY(64) // 若不满足 → 直接扩容resize不树化 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; do { TreeNodeK,V 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); } }哈希表的寻址过程哈希表以 Java HashMap 为例的寻址过程本质是通过键的哈希值定位到哈希桶数组中具体位置的过程核心是哈希计算 → 下标计算 → 冲突处理 三步而且HashMap 的寻址过程贯穿put/get等核心方法。1计算键的哈希值Hash 扰动首先对传入的key计算哈希值目的是尽可能让不同的 key 生成不同的哈希值减少后续冲突。如果key nullHashMap 允许 key 为 null直接固定哈希值为 0如果key ! null调用key.hashCode()得到原始哈希值int 类型范围 -2³¹ ~ 2³¹-1然后对这个值做「扰动处理」哈希扰动static final int hash(Object key) { int h; // 扰动公式h key.hashCode() ^ (h 16) return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }为什么要扰动原始哈希值的高位特征可能被浪费后续下标计算只用到低位通过「高 16 位异或低 16 位」让高位特征参与到后续下标计算中进一步减少哈希冲突。2计算数组下标定位桶位置得到扰动后的哈希值后需要将其映射到哈希桶数组Node[] table的合法下标范围内核心公式int index hash (table.length - 1);为什么不用取模%因为 HashMap 规定数组长度必须是 2 的幂次如 16、32、64...此时table.length - 1的二进制是全 1比如 16-115 → 0b1111hash (length-1)等价于hash % length但位运算比取模运算快得多。示例假设数组长度为 16length-1150b1111某个 key 的哈希值扰动后为 230b10111则下标 23 15 70b00111该 key 会被定位到数组下标 7 的桶中。3处理哈希冲突桶内寻址如果下标对应的桶为空直接将节点放入即可如果桶不为空哈希冲突则需要在桶内进一步寻址桶内是链表遍历链表逐个比较节点的hash值和key用equals()如果找到hash相等且key.equals()为 true 的节点就是目标节点get 则返回 valueput 则替换 value如果遍历完链表都没找到说明是新节点put 则添加到链表尾部。桶内是红黑树调用红黑树的查找方法如getTreeNode()通过红黑树的特性快速定位节点红黑树会根据节点的hash和key进行比较查找效率为 O (log n)远高于链表的 O (n)。4扩容判断每次插入新元素后检查是否需要扩容当前元素的个数是否大于阈值容量*负载因子如果大于数组容量扩招为原来的2倍并且重新计算每个节点的索引进行数据重新分布。哈希寻址示例假设我们要从 HashMap 中获取key Java的值完整寻址过程计算key.hashCode()→ 得到原始哈希值比如 3254818扰动处理3254818 ^ (3254818 16) → 得到最终哈希值比如 3254820计算下标3254820 (16-1) 4 → 定位到数组下标 4 的桶桶内有链表节点数 8遍历链表第一个节点 key 是 Python → hash 不等跳过第二个节点 key 是 Java → hash 相等且equals()为 true → 找到目标节点返回其 value。HashMap put流程示例现在用一个Java 8 HashMap 插入数据的完整例子一步步展示数组、链表、红黑树的变化过程。初始化一个空 HashMap默认参数数组长度容量16负载因子 0.75扩容阈值 16×0.7512树化阈值链表转红黑树8退链阈值 6。为了简化我们假设插入的 key 计算后得到的哈希值对应的数组下标全部为 3模拟极端哈希冲突场景方便看链表 / 红黑树变化。步骤 1插入第 1~7 个元素keyA~Gvalue1~7寻址过程以 keyA 为例B~G 逻辑一致计算 hash 值调用key.hashCode()得到原始哈希值执行扰动运算hash A.hashCode() ^ (A.hashCode() 16)计算数组下标当前数组容量 16 → 下标 hash (16-1) hash 15 3桶内操作检查 table [3] 为空 → 新建 Node 节点hash 计算出的 hash 值keyAvalue1nextnull放入 table [3]。keyB~G 依次执行上述步骤因下标均为 3且 key 不重复尾插到链表尾部原有状态补充数组下标 3 的桶指向链表头A链表长度 7状态无扩容、无树化size7 threshold12结构table[3] A→B→C→D→E→F→G。步骤 2插入第 8 个元素keyHvalue8→ 触发扩容检查寻址过程计算 hash 值执行hash H.hashCode() ^ (H.hashCode() 16)计算数组下标当前数组容量 16 → 下标 hash 15 3桶内操作检查 table [3] 不为空 → 遍历链表A→G对比每个节点的 hash 值和 key.equals ()确认无重复 key尾插法将 H 节点添加到链表尾部链表长度变为 8触发树化检查链表长度 8 → 调用treeifyBin(tab, hash)检查数组容量 16 64 → 放弃树化触发resize()扩容。扩容后的寻址所有节点重新哈希数组扩容至 32重新计算每个节点的下标hash (32-1) hash 31 3仍为 3所有节点A~H按原链表顺序迁移到新数组的 table [3] 桶中。原有状态补充扩容后数组容量 32threshold24size8 24结构table[3] A→B→C→D→E→F→G→H。步骤 3插入第 9~24 个元素keyI~Xvalue9~24寻址过程以 keyI 为例J~X 逻辑一致计算 hash 值执行hash I.hashCode() ^ (I.hashCode() 16)计算数组下标当前数组容量 32 → 下标 hash 31 3桶内操作遍历 table [3] 的链表A→H确认 keyI 无重复尾插法添加到链表尾部size 从 9 逐步增长到 24。关键节点keyX第 24 个元素的寻址补充插入 X 后size24 threshold24 → 因源码中扩容条件是size threshold故暂不扩容链表长度 24数组容量 32 64 → 仍不树化结构table[3] A→B→…→X。步骤 4插入第 25 个元素keyYvalue25→ 再次扩容寻址过程计算 hash 值执行hash Y.hashCode() ^ (Y.hashCode() 16)计算数组下标当前数组容量 32 → 下标 hash 31 3桶内操作遍历链表A→X确认 keyY 无重复 → 尾插法添加size25size25 threshold24 → 触发resize()扩容。扩容后的寻址所有节点重新哈希数组扩容至 64重新计算下标hash (64-1) hash 63 3仍为 3所有节点A~Y迁移到新数组的 table [3] 桶中链表长度 25扩容后数组容量 64threshold48满足树化的容量条件。步骤 5触发链表转红黑树寻址 树化过程插入 Y 后HashMap 在完成插入操作后立即对 table [3] 的链表执行树化检查寻址验证确认 table [3] 的链表长度 25 ≥ 8且数组容量 64 ≥ 64执行树化调用treeifyBin(tab, hash)→ 将链表节点Node逐个转为树节点TreeNode按红黑树规则排列最终寻址结果table [3] 指向红黑树根节点后续对该桶的寻址将走红黑树的查找逻辑O (log n)。原有状态补充最终状态table [3] 指向红黑树根节点size25无链表。步骤 6删除元素至红黑树节点数 6keyY、X 删除寻址过程以删除 keyY 为例计算 hash 值执行hash Y.hashCode() ^ (Y.hashCode() 16)计算数组下标当前数组容量 64 → 下标 hash 63 3桶内操作遍历红黑树通过 hash 值和 key.equals () 定位到 Y 节点删除 Y 节点红黑树自动调整结构以满足红黑树特性重复上述步骤删除 X 节点红黑树节点数降至 6 → 触发退链逻辑红黑树转回链表table [3] 重新指向链表头节点。原有状态补充状态链表长度 6数组容量 64无红黑树。步骤 7插入重复 keykeyAvalue99寻址过程计算 hash 值执行hash A.hashCode() ^ (A.hashCode() 16)计算数组下标当前数组容量 64 → 下标 hash 63 3桶内操作遍历 table [3] 的链表A→W对比每个节点的 hash 值相等 key.equals (A)true找到目标节点后仅将 value 从 1 更新为 99不新增节点、不改变链表结构。原有状态补充结构table[3] A(99)→B→C→D→E→F→G→…→W。手搓HashMap源码/** * Author * Date 2021/11/21 * Description 自己实现HashMap修复版 */ public class ThirdHashMapK, V { /** * 节点类 */ class NodeK, V { //键值对 private K key; private V value; //链表后继 private NodeK, V next; public Node(K key, V value) { this.key key; this.value value; } public Node(K key, V value, NodeK, V next) { this.key key; this.value value; this.next next; } } //默认容量2的幂 final int DEFAULT_CAPACITY 16; //负载因子 final float LOAD_FACTOR 0.75f; //HashMap的大小 private int size; //桶数组 NodeK, V[] buckets; /** * 无参构造器设置桶数组默认容量 */ public ThirdHashMap() { buckets new Node[DEFAULT_CAPACITY]; size 0; } /** * 有参构造器指定桶数组容量自动向上取整为2的幂 */ public ThirdHashMap(int capacity) { int cap tableSizeFor(capacity); buckets new Node[cap]; size 0; } /** * 计算大于等于cap的最小2的幂 */ private 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 Integer.MAX_VALUE) ? Integer.MAX_VALUE : n 1; } /** * 哈希函数获取地址修复版哈希扰动位运算 */ private int getIndex(K key, int length) { if (key null) { return 0; // 支持null key哈希值为0 } int h key.hashCode(); // 哈希扰动高低16位异或减少冲突 h ^ (h 16); // 位运算替代取模仅当length为2的幂时生效 return h (length - 1); } /** * put方法 */ public void put(K key, V value) { putVal(key, value, buckets); // 先插入再判断扩容避免size超过阈值 if (size buckets.length * LOAD_FACTOR) { resize(); } } /** * 将元素存入指定的node数组修复版尾插法 */ private void putVal(K key, V value, NodeK, V[] table) { int index getIndex(key, table.length); Node node table[index]; // 插入位置为空直接插入 if (node null) { table[index] new Node(key, value); size; return; } // 插入位置不为空遍历链表 while (node ! null) { // key相同覆盖value if ((node.key key || (node.key ! null node.key.equals(key)))) { node.value value; return; } // 到达链表尾部尾插法插入 if (node.next null) { node.next new Node(key, value); size; return; } node node.next; } } /** * 扩容 */ private void resize() { // 创建两倍容量的桶数组保证2的幂 int newCapacity buckets.length 1; NodeK, V[] newBuckets new Node[newCapacity]; // 重新散列 rehash(newBuckets); buckets newBuckets; } /** * 重新散列当前元素修复版避免size重复累加 */ private void rehash(NodeK, V[] newBuckets) { // 遍历旧桶数组迁移节点 for (int i 0; i buckets.length; i) { NodeK,V node buckets[i]; while (node ! null) { NodeK,V next node.next; // 保存next避免链表断裂 int index getIndex(node.key, newBuckets.length); // 尾插法迁移 if (newBuckets[index] null) { newBuckets[index] new Node(node.key, node.value); } else { NodeK,V tail newBuckets[index]; while (tail.next ! null) { tail tail.next; } tail.next new Node(node.key, node.value); } node next; } } } /** * 获取元素 */ public V get(K key) { int index getIndex(key, buckets.length); Node node buckets[index]; while (node ! null) { if ((node.key key || (node.key ! null node.key.equals(key)))) { return (V) node.value; } node node.next; } return null; } /** * 返回HashMap大小 */ public int size() { return size; } }HashMap扩容机制⏰ 一、 扩容的触发条件扩容并非随意发生主要在put元素时进行判断。当满足以下任一条件时就会触发扩容元素数量超过阈值这是最常见的情况。当 HashMap 中的元素数量 (size) 大于扩容阈值 (threshold) 时触发。扩容阈值计算公式threshold capacity * loadFactor默认初始容量 (capacity) 为 16默认负载因子 (loadFactor) 为 0.75所以初始阈值为16 * 0.75 12。当放入第 13 个元素时就会触发扩容。链表树化前的检查当一个桶中的链表长度达到树化阈值默认为 8时HashMap 会先检查当前数组的容量。如果容量小于最小树化容量默认为 64则会优先触发扩容而不是立即转换为红黑树。设计思想在数组容量较小时通过扩容增加桶的数量可以有效分散冲突的元素可能使链表长度降低从而避免了过早地转换为占用更多内存的红黑树。 二、 核心扩容流程 (resize)JDK 1.8 对扩容过程进行了重大优化核心在于高效地迁移元素避免了重新计算哈希值。整个过程可以概括为三步计算新容量创建一个新数组其容量是旧数组的 2 倍。例如从 16 扩容到 32。这保证了容量始终是 2 的幂次方为后续的位运算优化打下基础。创建新数组根据计算出的新容量创建一个新的Node[]数组。迁移旧数据 (Rehash)这是最关键、最耗时的步骤。JDK 1.8 利用容量翻倍的特性通过一个巧妙的位运算将旧数组中的元素直接拆分到新数组的两个可能位置上而无需重新计算哈希。 三、 关键细节JDK 1.8 的高效迁移在 JDK 1.7 中迁移元素需要重新计算每个元素的哈希值和新索引并且在多线程环境下使用头插法可能导致链表形成环引发死循环。JDK 1.8 对此进行了优化核心优化由于新容量是旧容量的 2 倍一个元素在新数组中的位置只有两种可能保持在原索引位置。移动到原索引 旧容量的位置。判断方法通过(e.hash oldCap) 0这个简单的位运算来判断。如果为true说明该元素的哈希值在“新增的那一位”上是 0它在新数组中的位置不变。如果为false说明该元素的哈希值在“新增的那一位”上是 1它需要被移动到原索引 oldCap的位置。迁移方式链表JDK 1.8 使用尾插法来迁移链表。在迁移过程中会将旧链表拆分成两条新链表低位链表loHead和高位链表hiHead分别放到新数组的对应位置。尾插法保证了链表元素的原有顺序彻底解决了 JDK 1.7 中多线程扩容可能导致的死循环问题。红黑树如果桶中是红黑树会调用split()方法按照同样的逻辑将树节点拆分成两个子树或链表再放入新数组。