HashMap 源码深度解析

但 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); } } } 核心提示Java 8 采用尾插法而非 Java 7 的头插法这是为了解决多线程扩容时链表成环的问题。虽然 HashMap 本身不是线程安全的但尾插法至少避免了在并发场景下出现死循环。真正的并发场景仍然应该使用ConcurrentHashMap。扩容源码再看一下扩容逻辑的具体实现resize 详细流程图是是否否是否是否否是单节点红黑树链表是否resize() 入口oldCap table.length\noldThr thresholdoldCap 0?oldCap MAXIMUM_CAPACITY?threshold MAX_VALUE\n返回旧数组newCap oldCap 1\nnewThr oldThr 1oldThr 0?newCap oldThr\n有参构造首次扩容newCap 16, newThr 12\n无参构造首次扩容newThr 0?newThr newCap * loadFactorthreshold newThrnewTab new Node[newCap]oldTab ! null?返回 newTab遍历旧数组 0 ~ oldCap节点数量?newTab[e.hash (newCap-1)] esplit() 拆分红黑树hash oldCap 0?\n拆分低位/高位链表插入低位 newTab[j]插入高位 newTab[j oldCap]继续遍历扩容源码详解/** * 扩容同时负责首次初始化 */ final NodeK, V[] resize() { NodeK, V[] oldTab table; int oldCap (oldTab null) ? 0 : oldTab.length; int oldThr threshold; int newCap, newThr 0; // 计算扩容后容量大小 // 1. 如果原来容量大于0说明不是第一次扩容直接扩容为原来的2倍 if (oldCap 0) { if (oldCap MAXIMUM_CAPACITY) { threshold Integer.MAX_VALUE; return oldTab; } else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY) { newThr oldThr 1; } } else if (oldThr 0) { // 2. 把原来的阈值当成新的容量大小有参构造首次put时走这个分支 newCap oldThr; } else { // 3. 如果是第一次初始化无参构造则容量和阈值都用默认值 newCap DEFAULT_INITIAL_CAPACITY; newThr (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 4. 如果新的阈值未设置则重新计算扩容后阈值 if (newThr 0) { float ft (float) newCap * loadFactor; newThr (newCap MAXIMUM_CAPACITY ft (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE); } threshold newThr; // 5. 创建一个新数组容量使用上面计算的大小 NodeK, V[] newTab (NodeK, V[]) new Node[newCap]; table newTab; // 6. 遍历原来的数组将元素插入到新数组 if (oldTab ! null) { for (int j 0; j oldCap; j) { NodeK, V e; if ((e oldTab[j]) ! null) { oldTab[j] null; // 帮助 GC 回收 // 7. 如果下标位置只有一个元素则直接插入新数组即可 if (e.next null) { newTab[e.hash (newCap - 1)] e; } else if (e instanceof TreeNode) { // 8. 如果下标位置元素类型是红黑树则执行红黑树的拆分逻辑 ((TreeNodeK, V) e).split(this, newTab, j, oldCap); } else { // 9. 否则执行链表的拆分逻辑使用 do-while 循环 // loHead、loTail表示低位链表的头尾节点 // hiHead、hiTail表示高位链表的头尾节点 NodeK, V loHead null, loTail null; NodeK, V hiHead null, hiTail null; NodeK, V next; do { next e.next; // 10. 判断当前元素 hash oldCap 是否为0 // 为0 → 位置不变插入低位链表 // 不为0 → 位置 原下标 oldCap插入高位链表 if ((e.hash oldCap) 0) { if (loTail null) { loHead e; } else { loTail.next e; } loTail e; } else { if (hiTail null) { hiHead e; } else { hiTail.next e; } hiTail e; } } while ((e next) ! null); // 11. 将低位链表插入到新数组中位置不变 if (loTail ! null) { loTail.next null; newTab[j] loHead; } // 12. 将高位链表插入到新数组中位置 j oldCap if (hiTail ! null) { hiTail.next null; newTab[j oldCap] hiHead; } } } } } return newTab; }重点关注第 9 步的链表拆分逻辑。这个方法非常巧妙不是逐个计算元素在新数组中的下标而是将原链表拆成两个链表整体迁移。假设原数组容量是 16某个下标位置的链表元素分别是1 - 17 - 33 - 49这些元素的共同特点是对 16 求余等于 1。扩容后新数组容量是 32这些元素会拆分成两条链表下标 1 的链表1 - 33hash 16 0位置不变下标 17 的链表17 - 49hash 16 16新位置 1 16 17为什么hash oldCap能判断元素是否需要移动因为容量是 2 的幂扩容后多了一位。如果元素的 hash 值在这一位上是 0下标不变如果是 1新下标 原下标 oldCap。这样就不需要重新计算每个元素的下标大幅提升了扩容效率。 核心提示负载因子为什么默认是 0.75这是空间利用率和时间效率之间的最佳折中。根据泊松分布负载因子为 0.75 时链表长度达到 8 的概率极低约千万分之六。如果负载因子设为 1.0虽然空间利用率高了但哈希冲突会显著增加如果设为 0.5虽然冲突减少了但空间浪费了一半。0.75 是经过大量实验验证的最优值。哈希冲突解决从链表到红黑树当多个 key 的 hash 值计算出相同的数组下标时就会发生哈希冲突。HashMap 采用拉链法解决冲突将冲突的 key 串成链表挂在同一个桶位。但在极端情况下恶意构造 hashCode 或大量冲突链表会很长查询退化为 O(n)。Java 8 引入红黑树来解决这个问题。下面是链表到红黑树的转换流程图否是是否TreeNodeNode否是否是是否发生哈希冲突计算桶位 i (n-1) hashtab[i] 是否已有节点?直接插入, 无冲突key 是否匹配?覆盖旧值当前节点类型?红黑树插入 putTreeVal链表尾插链表长度 8?继续等待数组容量 64?resize() 扩容, 不树化treeifyBin() 链表转红黑树每个 Node 转为 TreeNodetreeify() 构建红黑树红黑树就绪, 查询 O(log n)扩容后该桶位链表长度 6?untreeify() 红黑树退化链表 核心提示红黑树的树化过程不是直接将链表中的节点逐个 insert 到空树中而是先将所有节点转为 TreeNode 并用 prev/next 连成双向链表再通过treeify()方法自底向上构建红黑树。这种方式比逐个插入更高效且构建后会自动平衡。退化过程同理untreeify()会遍历树节点逐个转回普通 Node 并重新连成单向链表。get 源码再看一下 get 方法源码实现/** * get 方法入口 */ public V get(Object key) { NodeK, V e; return (e getNode(hash(key), key)) null ? null : e.value; } /** * 查询节点方法 */ final NodeK, V getNode(int hash, Object key) { NodeK, V[] tab; NodeK, V first, e; int n; K k; // 1. 获取下标位置节点元素命名为 first if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) { // 2. 比较 first 节点哈希值与 key 值 if (first.hash hash ((k first.key) key || (key ! null key.equals(k)))) { return first; } if ((e first.next) ! null) { // 3. 如果 first 节点类型是红黑树就执行红黑树的查找逻辑 if (first instanceof TreeNode) { return ((TreeNodeK, V) first).getTreeNode(hash, key); } // 4. 否则就执行链表的查找逻辑 do { if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) { return e; } } while ((e e.next) ! null); } } // 5. 都没找到就返回 null return null; }get 方法的逻辑与 put 类似先计算下标 → 检查头节点 → 根据节点类型选择查找方式。头尾节点的比较都优先用判断引用是否相同再用equals判断值是否相等这是一种短路优化。remove 源码再看一下 remove 方法源码/** * 删除方法入口 */ public V remove(Object key) { NodeK, V e; return (e removeNode(hash(key), key, null, false, true)) null ? null : e.value; } /** * 删除节点方法 */ final NodeK, V removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { NodeK, V[] tab; NodeK, V p; int n, index; // 1. 判断数组是否为空下标位置节点是否为空 if ((tab table) ! null (n tab.length) 0 (p tab[index (n - 1) hash]) ! null) { NodeK, V node null, e; K k; V v; // 2. 判断下标节点 key 是否与传入的 key 相等 if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) { node p; } else if ((e p.next) ! null) { // 3. 如果节点类型是红黑树就执行红黑树的查找逻辑 if (p instanceof TreeNode) { node ((TreeNodeK, V) p).getTreeNode(hash, key); } else { // 4. 如果节点类型是链表就执行链表的查找逻辑 do { if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) { node e; break; } p e; } while ((e e.next) ! null); } } // 5. 当找到节点时执行删除 if (node ! null (!matchValue || (v node.value) value || (value ! null value.equals(v)))) { if (node instanceof TreeNode) { ((TreeNodeK, V) node).removeTreeNode(this, tab, movable); } else if (node p) { // 删除的是头节点 tab[index] node.next; } else { // 删除的是中间或尾节点 p.next node.next; } modCount; --size; afterNodeRemoval(node); return node; } } return null; }关于ConcurrentModificationExceptionHashMap 的迭代器是fail-fast的。在创建迭代器时会记录当前的modCount值每次调用next()时都会检查modCount是否与预期值一致。如果不一致说明在迭代过程中代码修改了 HashMap 的结构就会抛出ConcurrentModificationException。这是 Java 集合框架的一种快速失败机制目的是尽早发现并发修改问题而不是等到数据错乱后才暴露。时间复杂度分析各操作时间复杂度详细对比操作方法平均时间复杂度最坏时间复杂度空间复杂度说明插入putO(1)O(log n)O(1)无冲突时直接定位桶位 O(1)冲突严重时树化后 O(log n)查询getO(1)O(log n)O(1)同上删除removeO(1)O(log n)O(1)同上扩容resizeO(n)O(n)O(n)需要遍历所有元素并迁移到新数组n 为元素总数树化treeifyBinO(n)O(n)O(n)遍历链表构造 TreeNode 并构建红黑树退化untreeifyO(n)O(n)O(1)遍历红黑树转回链表n 为桶位节点数遍历forEach/entrySetO(n)O(n)O(1)遍历整个 table 数组 所有链表/树节点containsKeycontainsKeyO(1)O(log n)O(1)等价于get再判断是否为 nullcontainsValuecontainsValueO(n)O(n)O(1)需要遍历所有桶位的所有节点sizesizeO(1)O(1)O(1)直接返回size字段 核心提示HashMap 的最坏情况 O(log n) 依赖于红黑树机制。如果 key 的hashCode()实现很差导致大量冲突在 Java 7 中最坏情况是 O(n)Java 8 引入红黑树后才将最坏情况优化到 O(log n)。因此自定义对象作为 key 时务必正确实现hashCode()和equals()方法这是保证 HashMap 性能的关键前提。HashMap 核心参数与特性对比表不同 Map 实现对比特性HashMapLinkedHashMapTreeMapConcurrentHashMapHashtable底层结构数组链表红黑树数组链表红黑树双向链表红黑树数组链表红黑树数组链表有序性无序插入顺序/访问顺序按 key 排序无序无序线程安全否否否是CASsynchronized是synchronized允许 null key是仅1个是仅1个否是仅1个否允许 null value是多个是多个否是多个否迭代器fail-fastfail-fastfail-fastweakly consistentEnumerator查询复杂度O(1)O(1)O(log n)O(1)O(1)Java 版本1.21.41.21.51.0核心常量对比常量名值作用DEFAULT_INITIAL_CAPACITY16默认初始容量MAXIMUM_CAPACITY2^30最大容量限制DEFAULT_LOAD_FACTOR0.75默认负载因子TREEIFY_THRESHOLD8链表转红黑树阈值UNTREEIFY_THRESHOLD6红黑树退化链表阈值MIN_TREEIFY_CAPACITY64树化所需最小数组容量生产环境避坑指南1. 预估容量避免频繁扩容HashMap 每次扩容都会重新分配数组并迁移所有元素这是一个 O(n) 的操作。如果生产环境中数据量已知应该在构造时就指定合适的容量。// 推荐预估 1000 个元素 // 公式capacity expectedSize / loadFactor 1 int capacity (int) Math.ceil(1000 / 0.75) 1; // 1334 → tableSizeFor 后为 2048 MapString, Object map new HashMap(capacity);2. 正确重写 hashCode 和 equals自定义对象作为 key 时必须同时重写hashCode()和equals()否则会出现 key 能 put 但 get 不到的诡异问题。// 错误示例只重写 equals不重写 hashCode class User { String name; Override public boolean equals(Object o) { if (o instanceof User) return name.equals(((User) o).name); return false; } // 缺少 hashCode使用 Object 的默认实现基于内存地址 } // 结果两个 name 相同的 User 对象hashCode 不同会被当成两个 key 核心提示Java 规范明确规定如果两个对象equals()返回 true则它们的hashCode()必须相同。违反这个约定HashMap 的行为将是未定义的。3. 遍历中删除使用 Iterator// 错误示例遍历时直接调用 map.remove() for (String key : map.keySet()) { if (key.startsWith(temp)) { map.remove(key); // ConcurrentModificationException! } } // 正确示例使用 Iterator.remove() IteratorString it map.keySet().iterator(); while (it.hasNext()) { if (it.next().startsWith(temp)) { it.remove(); } } // 或者使用 removeIfJava 8 map.keySet().removeIf(key - key.startsWith(temp));4. 大 key 对象导致内存泄漏HashMap 的 key 会长期持有对象的引用。如果 key 是重量级对象且 map 作为 static 字段长期存在会导致内存泄漏。建议使用WeakHashMap或者适时清理。// 使用 WeakHashMapkey 在 GC 时会被自动回收 MapBigObject, Value map new WeakHashMap();5. 高并发场景使用 ConcurrentHashMapHashMap 不是线程安全的。多线程并发put可能导致数据覆盖丢失更新size 不准确JDK 7 中并发扩容可能形成链表环Java 8 已修复此问题但并发数据不一致仍存在// 高并发推荐方案 MapString, Object map new ConcurrentHashMap(); // 如果需要统计访问顺序可以使用 ConcurrentHashMapString, Object map new ConcurrentHashMap(16, 0.75f, 1);6. 注意 Integer/Long 缓存陷阱// Integer 缓存范围-128 ~ 127 MapInteger, String map new HashMap(); map.put(128, a); map.put(128, b); // key 是同一个 Integer 对象自动装箱 // 但如果用 new Integer(128)会创建不同对象 // 不过 HashMap 通过 equals 判断 key 是否相同所以仍然正确 // 但作为 key 时务必确保 hashCode 和 equals 的一致性