学 Java 以来HashMap 是我听过最多、也最让我头疼的一个东西真正开始啃源码的时候我才发现 HashMap 的设计比我想的复杂得多也巧妙得多。这篇就写写我从会用到大概懂了的整个过程。从一个新手的视角把 HashMap 最核心的几个机制串一遍。开始之前Map 家族都有谁学 HashMap 之前我其实连 Map 这个概念都搞不太清楚。List 和 Set 我知道List 是一排数据Set 是一堆不重复的数据。但 Map 呢它存的是一对一对的东西每对有一个 key 和一个 value你可以通过 key 找到对应的 value。Java 里常见的 Map 实现有这么几个HashMap最常用的基于哈希表存键值对。它的问题是不保证顺序也不安全。LinkedHashMapHashMap 的小弟多了个双向链表能记住你插入的顺序或者按访问顺序排。TreeMap基于红黑树key 会按大小排序。你可以用自然排序也可以自己传个 Comparator。Hashtable老前辈了线程安全的但因为它的方法全用 synchronized 包了一层性能不太行现在已经不怎么用了。ConcurrentHashMap真正的线程安全选手性能比 Hashtable 好得多后面会单独讲。一开始我记不住这么多只知道最常用的就是 HashMap。但搞清楚它们之间的区别有个好处面试的时候问HashMap 和 Hashtable 有什么区别这种问题答案就藏在这里面。而且说实话日常开发 90% 的 Map 场景用 HashMap 就够了。剩下 10% 才需要考虑 LinkedHashMap 或者 ConcurrentHashMap。HashMap 的底层到底长什么样我之前以为 HashMap 里面就是一张简单的表key 存一格value 存一格像 Excel 那样。后来才知道完全不是这么回事。JDK 1.7 的时候在 JDK 1.7 及之前HashMap 的底层结构是数组加链表。怎么理解呢你可以把数组想象成一排桶每个桶有一个编号。你把一个键值对放进去的时候HashMap 会根据 key 的哈希值算出一个数字这个数字决定这个键值对应该丢到哪个桶里。但问题来了不同的 key 算出来的哈希值可能对应同一个桶。这就叫哈希冲突。怎么办那个桶里不止放一个元素而是放一个链表。冲突了就把新的元素挂在链表的后面。但这样有个问题如果一个桶里的链表变得很长比如几十个元素都挤到同一个桶里那我要找某个 key 的时候就得在这个链表里一个一个比速度就慢下来了。链表查找的时间复杂度是 O(n)。当时我还在想那如果 key 特别多链表特别长HashMap 不就废了吗这个担心是有道理的所以 JDK 1.8 做了改进。JDK 1.8 之后JDK 1.8 把结构改成了数组加链表加红黑树。核心变化是当某个桶的链表长度达到一定阈值默认为 8而且整个数组的长度也达到 64 的时候这个链表会转成一棵红黑树。红黑树查找的时间复杂度是 O(log n)比链表的 O(n) 快了不少。我第一次看到这个设计的时候心想这思路挺聪明的大多数情况下链表不长用链表就够了开销小万一真的有很多 key 冲突到一起就升级成红黑树补救一下。不搞一刀切。不过有个条件我一开始忽略了链表长度 ≥ 8 的时候它不会立刻树化还得看数组的长度有没有达到 64。如果数组长度还没到 64它会先做扩容把数组变大让元素分散开链表自然就短了。只有当数组长度也到 64 了链表还是太长才转为红黑树。反过来如果后面元素被删了红黑树的节点数 ≤ 6 的时候它又会退化回链表。这个 8 和 6 之间留了 2 的缓冲避免了频繁地在链表和红黑树之间切换。这个设计我当时琢磨了好一会儿才想通它其实是个分级应对的策略正常情况用链表冲突严重了点扩容扩容还不够再升级红黑树。put 方法到底做了啥先说说 put就是往 HashMap 里存数据的时候会发生什么。我第一次猜的是直接算个位置丢进去就完了。但看完源码发现步骤比我想象的多。第一步算位置HashMap 先把 key 的 hashCode 拿过来再做一次扰动处理就是把 hashCode 的高位和低位做个异或目的是让算出来的哈希值更均匀。然后通过(n - 1) hash算出这个 key 应该放在数组的哪个位置。n 是数组的长度。这里的是位运算比取模快得多。但有个前提数组长度必须是 2 的 n 次方后面会细说。第二步检查数组该位置是不是空的如果算出来的那个位置是空的太好了直接 new 一个 Node 放进去就行。这就是最简单的情况。第三步位置不为空开始比较如果那个位置已经有人占了那就需要判断了。先看占位的这个 Node 和我们要放的 key 是不是同一个比较哈希值和 equals。如果是同一个 key就直接替换 value。第四步遍历链表或者红黑树如果第一个节点不是我们要的 key就看后面还有没有。如果这个桶里面是链表结构就一个一个往后遍历找到相同的 key 就替换值没找到就在链表尾部追加。如果桶里面已经是红黑树了就走红黑树的查找逻辑去找。说到链表我顺便提一句JDK 1.7 的时候用的是头插法新节点插到链表头部JDK 1.8 改成了尾插法插到尾部。这是因为头插法在多线程扩容的时候可能产生环形链表导致 get 的时候死循环。JDK 1.8 改成尾插法以后这个 bug 就没了。第五步检查要不要树化如果刚才是在链表里追加了元素追加完后 HashMap 会检查这个链表的长度是不是 ≥ 8 了如果数组长度也 ≥ 64就会把链表转成红黑树。第六步检查要不要扩容最后HashMap 会检查目前存了多少个元素size有没有超过容量 × 负载因子。如果超过了就触发扩容把数组变成原来的 2 倍然后把老数据重新分配。我当时看完这个流程觉得最让我意外的是一个看起来简单的 put 操作背后竟然有这么多判断。但也正是因为这些设计HashMap 才能在大部分情况下保持 O(1) 的性能。get 方法怎么找到数据的get 方法比 put 简单一些。我还是会习惯性地先去找 getNode 方法因为 get 本身只是调了一下 getNode。过程大概是这样的先检查 table 数组有没有被初始化数组长度是不是大于 0算出来的那个位置是不是有节点。如果这些条件有一个不满足直接返回 null。检查位置上的第一个节点如果哈希值和 key 都匹配上了直接返回这个节点。如果第一个不是就看它有没有下一个节点。如果有判断当前桶是链表还是红黑树链表用 do-while 循环挨个比较 key找到了就返回。红黑树走红黑树的查找算法去找。如果整个走完都没找到返回 null。这个流程看完我最大的感受是HashMap 在每次 get 的时候都先检查第一个节点这个细节挺有实用性的如果每个桶里的元素不多这是大多数情况第一个节点往往就是你要找的一次比较就返回不需要再去判断是链表还是树。扩容机制我觉得最巧妙的部分HashMap 的扩容我第一次看源码的时候没太看懂后来画了几张图才弄明白。什么时候扩容当 HashMap 里的元素个数超过了容量 × 负载因子的时候就会触发扩容。比如默认容量是 16负载因子是 0.75那么当存到第 13 个元素的时候16 × 0.75 12也就是超过 12 个的时候就会触发扩容。怎么扩容扩容分两步第一步把数组扩大到原来的 2 倍。第二步把旧数组里的元素重新分配到新数组里。关键就在这个第二步。我原以为扩容就是把每个元素重新计算一遍哈希值然后放到新数组对应的位置上去。但 JDK 1.8 的 HashMap 没有这么做。它利用了一个很巧妙的设计因为新容量是旧容量的 2 倍而容量始终是 2 的 n 次方所以每个元素的新位置要么是原来的索引要么是原来的索引 旧容量。判断方法是看(e.hash oldCap)的结果。如果结果是 0就留在原位置如果不是 0就移动到原位置 oldCap。举个例子旧容量是 16某个 key 的 hash 值是 20它在旧数组的位置是 20 15 4。扩容后新容量是 32我们算一下 20 16结果是 16不是 0所以它应该去的位置是 4 16 20。我当时自己手算了一遍发现确实是这样。灵感来源是因为 2 倍扩容后n-1的二进制低 n 位就多了一位从 1111 变成 11111所以新索引其实就是看 hash 值新增的那一位是 0 还是 1。是 0 就不动是 1 就加 oldCap。这个设计的妙处在于两点不需要重新计算 hash省了一次哈希计算的开销。能把旧数组里同一个桶的元素均匀分散到两个位置。因为 hash 值新增的那一位是 0 还是 1 可以认为是随机的所以原来冲突的元素会被拆成两拨分别放在原位置和原位置 oldCap上。我看明白这个之后确实觉得这个设计很漂亮。一个简单的位运算把扩容时最麻烦的两个问题一起解决了。为什么容量必须是 2 的 n 次方这个其实上面已经提到了HashMap 里很多操作都依赖数组长度是 2 的 n 次方。我刚学的时候没太在意这个觉得是不是 2 的 n 次方能有多大区别后来仔细算了算才发现差别很大。主要原因有三个1. 用位运算代替取模HashMap 计算索引的核心公式是hash (length - 1)。当 length 是 2 的 n 次方时这个位运算等价于hash % length。但位运算比取模快得多位运算直接操作二进制位而取模需要做除法。如果 length 不是 2 的 n 次方length - 1 的二进制就不是全 1 的形式这个位运算就不等价于取模了。2. 让索引分布更均匀还是回到上面那个公式。当 length 是 2 的 n 次方时length - 1 的二进制低 n 位全是 1比如 length16 时15 的二进制是 1111这样 hash 值的低 n 位每一位都能参与决定最终索引的位置。如果 length 不是 2 的 n 次方比如 length15length-114二进制 1110最后一位是 0。这意味着不管 hash 的最后一位是 0 还是 1与运算的结果最后一位都是 0所以索引的奇数位永远用不到数组空间浪费了一半碰撞概率也高了很多。我当时看到这个例子的时候心想这个设计约束确实是有道理的。不是 2 的 n 次方的话损失太大了。3. 扩容时不用重新计算 hash这个上面扩容那节已经讲过了。正是因为容量一直是 2 的 n 次方扩容时才能用hash oldCap来判断新位置。这三个原因是环环相扣的为了让位运算生效所以必须是 2 的 n 次方因为必须是 2 的 n 次方所以扩容时可以用位运算优化。整个设计是自洽的。负载因子 0.75 为什么刚刚好HashMap 默认的负载因子是 0.75。学到这里的时候我就好奇为什么是 0.75不是 0.5 或者 1负载因子的本质是空间和时间之间的取舍。如果负载因子太小比如 0.5HashMap 里用的桶还没装多少东西就开始扩容了。好处是冲突少每个桶里的链表短查得快。坏处是很多空间是空的浪费内存。如果负载因子太大比如 1HashMap 要把桶几乎装满才扩容。好处是空间利用率高。坏处是冲突变多每个桶里的链表长查得慢。0.75 就是在空间和时间之间取了一个平衡点。在理想情况下当负载因子是 0.75 时HashMap 在时间性能和空间利用率上都能接受。我从一本书上看到说0.75 这个值是基于泊松分布算出来的。当负载因子是 0.75 时链表长度超过 8 的概率非常低小于千万分之一所以正常情况下红黑树其实很少会触发生效大多数时候链表就够了。这也解释了为什么 JDK 1.8 要把树化阈值设为 8正常情况下链表长度几乎不会到 8到了说明冲突已经很严重了是时候升级了。几个值得一提的小特性HashMap 还有一些小细节我当初看的时候觉得挺有意思的。第一个是null 作为 key。如果你用 null 做 keyHashMap 的处理方式是直接把 hash 值设成 0然后放到 0 号桶里。所以 null key 只能有一个因为每次都会覆盖到同一个桶但 null value 可以有多个。我当时问自己如果我不给 key 传 null调 get(null) 会怎么样答案是不会抛异常因为 HashMap 明确处理了这种情况。不像 Hashtable传 null 进去就直接抛 NullPointerException 了。第二个是默认容量。HashMap 默认初始容量是 16每次扩容变成原来的 2 倍。如果你在构造的时候指定了一个初始容量HashMap 会把它调整成大于等于这个数的 2 的 n 次方。比如你传 10它实际用的是 16你传 30它用 32。保证数组长度始终是 2 的 n 次方。我之前有个问题往 HashMap 里存 20 个元素会扩容几次答案是只扩一次。因为前 12 个元素不用扩第 13 个触发扩容到 32后面 7 个第 14 到第 20 个都在容量范围内。怎么遍历一个 Map最后说说遍历。Map 不像 List 那样直接用索引遍历它有几种不同的方式。我开始最常用的是增强 for 循环加 entrySetfor(Map.EntryString,Integerentry:map.entrySet()){System.out.println(entry.getKey() - entry.getValue());}这个写法最直接能同时拿到 key 和 value。如果只需要 key可以用 keySetfor(Stringkey:map.keySet()){System.out.println(key);}如果需要边遍历边删除元素就得用迭代器IteratorMap.EntryString,Integeritmap.entrySet().iterator();while(it.hasNext()){Map.EntryString,Integerentryit.next();if(someCondition){it.remove();}}这个和 List 的迭代器是同一个道理只能在迭代器自己的 remove 方法里删不能在循环里直接调 map.remove。JDK 8 以后多了 Lambda 表达式和 forEach 方法代码变得更短了map.forEach((key,value)-System.out.println(key - value));还有 Stream API 的方式如果你需要过滤或者做一些转换map.entrySet().stream().filter(entry-entry.getValue()10).collect(Collectors.toMap(Map.Entry::getKey,Map.Entry::getValue));这几种方式我平时用 entrySet 最多偶尔用 forEach 和 Stream。迭代器通常只在需要遍历时删除元素的时候才用。写在最后写这篇东西的时候我一直想着当初啃 HashMap 源码的自己。那时候看到 put 和 get 的源码一行一行地对着文档看好几处看了好几遍才看懂。HashMap 给我的感觉是它看起来是个简单的容器但你越往里挖越能发现设计者的用心。数据结构从数组 链表演进到数组 链表 红黑树扩容时用hash oldCap来决定元素新位置把容量设计为 2 的 n 次方来实现位运算代替取模这些设计不是孤立的它们互相配合形成了一个有机的整体。学完这些之后我再去用 HashMap 的时候感觉就不一样了。以前它就是一个能放键值对的东西现在我知道它背后做了什么、为什么这么做。当然这篇讲的主要是 HashMap 单线程下的工作机制。它的线程安全问题、红黑树为什么不用平衡二叉树、equals 和 hashCode 怎么重写这些话题也挺重要的下篇再聊。如果这篇文章让你对 HashMap 有了一点新的理解那就够了。毕竟我也是这么一点点啃过来的。
学 Java 以来HashMap 是我听过最多、也最让我头疼的一个东西真正开始啃源码的时候我才发现 HashMap 的设计比我想的复杂得多也巧妙得多。这篇就写写我从会用到大概懂了的整个过程。从一个新手的视角把 HashMap 最核心的几个机制串一遍。开始之前Map 家族都有谁学 HashMap 之前我其实连 Map 这个概念都搞不太清楚。List 和 Set 我知道List 是一排数据Set 是一堆不重复的数据。但 Map 呢它存的是一对一对的东西每对有一个 key 和一个 value你可以通过 key 找到对应的 value。Java 里常见的 Map 实现有这么几个HashMap最常用的基于哈希表存键值对。它的问题是不保证顺序也不安全。LinkedHashMapHashMap 的小弟多了个双向链表能记住你插入的顺序或者按访问顺序排。TreeMap基于红黑树key 会按大小排序。你可以用自然排序也可以自己传个 Comparator。Hashtable老前辈了线程安全的但因为它的方法全用 synchronized 包了一层性能不太行现在已经不怎么用了。ConcurrentHashMap真正的线程安全选手性能比 Hashtable 好得多后面会单独讲。一开始我记不住这么多只知道最常用的就是 HashMap。但搞清楚它们之间的区别有个好处面试的时候问HashMap 和 Hashtable 有什么区别这种问题答案就藏在这里面。而且说实话日常开发 90% 的 Map 场景用 HashMap 就够了。剩下 10% 才需要考虑 LinkedHashMap 或者 ConcurrentHashMap。HashMap 的底层到底长什么样我之前以为 HashMap 里面就是一张简单的表key 存一格value 存一格像 Excel 那样。后来才知道完全不是这么回事。JDK 1.7 的时候在 JDK 1.7 及之前HashMap 的底层结构是数组加链表。怎么理解呢你可以把数组想象成一排桶每个桶有一个编号。你把一个键值对放进去的时候HashMap 会根据 key 的哈希值算出一个数字这个数字决定这个键值对应该丢到哪个桶里。但问题来了不同的 key 算出来的哈希值可能对应同一个桶。这就叫哈希冲突。怎么办那个桶里不止放一个元素而是放一个链表。冲突了就把新的元素挂在链表的后面。但这样有个问题如果一个桶里的链表变得很长比如几十个元素都挤到同一个桶里那我要找某个 key 的时候就得在这个链表里一个一个比速度就慢下来了。链表查找的时间复杂度是 O(n)。当时我还在想那如果 key 特别多链表特别长HashMap 不就废了吗这个担心是有道理的所以 JDK 1.8 做了改进。JDK 1.8 之后JDK 1.8 把结构改成了数组加链表加红黑树。核心变化是当某个桶的链表长度达到一定阈值默认为 8而且整个数组的长度也达到 64 的时候这个链表会转成一棵红黑树。红黑树查找的时间复杂度是 O(log n)比链表的 O(n) 快了不少。我第一次看到这个设计的时候心想这思路挺聪明的大多数情况下链表不长用链表就够了开销小万一真的有很多 key 冲突到一起就升级成红黑树补救一下。不搞一刀切。不过有个条件我一开始忽略了链表长度 ≥ 8 的时候它不会立刻树化还得看数组的长度有没有达到 64。如果数组长度还没到 64它会先做扩容把数组变大让元素分散开链表自然就短了。只有当数组长度也到 64 了链表还是太长才转为红黑树。反过来如果后面元素被删了红黑树的节点数 ≤ 6 的时候它又会退化回链表。这个 8 和 6 之间留了 2 的缓冲避免了频繁地在链表和红黑树之间切换。这个设计我当时琢磨了好一会儿才想通它其实是个分级应对的策略正常情况用链表冲突严重了点扩容扩容还不够再升级红黑树。put 方法到底做了啥先说说 put就是往 HashMap 里存数据的时候会发生什么。我第一次猜的是直接算个位置丢进去就完了。但看完源码发现步骤比我想象的多。第一步算位置HashMap 先把 key 的 hashCode 拿过来再做一次扰动处理就是把 hashCode 的高位和低位做个异或目的是让算出来的哈希值更均匀。然后通过(n - 1) hash算出这个 key 应该放在数组的哪个位置。n 是数组的长度。这里的是位运算比取模快得多。但有个前提数组长度必须是 2 的 n 次方后面会细说。第二步检查数组该位置是不是空的如果算出来的那个位置是空的太好了直接 new 一个 Node 放进去就行。这就是最简单的情况。第三步位置不为空开始比较如果那个位置已经有人占了那就需要判断了。先看占位的这个 Node 和我们要放的 key 是不是同一个比较哈希值和 equals。如果是同一个 key就直接替换 value。第四步遍历链表或者红黑树如果第一个节点不是我们要的 key就看后面还有没有。如果这个桶里面是链表结构就一个一个往后遍历找到相同的 key 就替换值没找到就在链表尾部追加。如果桶里面已经是红黑树了就走红黑树的查找逻辑去找。说到链表我顺便提一句JDK 1.7 的时候用的是头插法新节点插到链表头部JDK 1.8 改成了尾插法插到尾部。这是因为头插法在多线程扩容的时候可能产生环形链表导致 get 的时候死循环。JDK 1.8 改成尾插法以后这个 bug 就没了。第五步检查要不要树化如果刚才是在链表里追加了元素追加完后 HashMap 会检查这个链表的长度是不是 ≥ 8 了如果数组长度也 ≥ 64就会把链表转成红黑树。第六步检查要不要扩容最后HashMap 会检查目前存了多少个元素size有没有超过容量 × 负载因子。如果超过了就触发扩容把数组变成原来的 2 倍然后把老数据重新分配。我当时看完这个流程觉得最让我意外的是一个看起来简单的 put 操作背后竟然有这么多判断。但也正是因为这些设计HashMap 才能在大部分情况下保持 O(1) 的性能。get 方法怎么找到数据的get 方法比 put 简单一些。我还是会习惯性地先去找 getNode 方法因为 get 本身只是调了一下 getNode。过程大概是这样的先检查 table 数组有没有被初始化数组长度是不是大于 0算出来的那个位置是不是有节点。如果这些条件有一个不满足直接返回 null。检查位置上的第一个节点如果哈希值和 key 都匹配上了直接返回这个节点。如果第一个不是就看它有没有下一个节点。如果有判断当前桶是链表还是红黑树链表用 do-while 循环挨个比较 key找到了就返回。红黑树走红黑树的查找算法去找。如果整个走完都没找到返回 null。这个流程看完我最大的感受是HashMap 在每次 get 的时候都先检查第一个节点这个细节挺有实用性的如果每个桶里的元素不多这是大多数情况第一个节点往往就是你要找的一次比较就返回不需要再去判断是链表还是树。扩容机制我觉得最巧妙的部分HashMap 的扩容我第一次看源码的时候没太看懂后来画了几张图才弄明白。什么时候扩容当 HashMap 里的元素个数超过了容量 × 负载因子的时候就会触发扩容。比如默认容量是 16负载因子是 0.75那么当存到第 13 个元素的时候16 × 0.75 12也就是超过 12 个的时候就会触发扩容。怎么扩容扩容分两步第一步把数组扩大到原来的 2 倍。第二步把旧数组里的元素重新分配到新数组里。关键就在这个第二步。我原以为扩容就是把每个元素重新计算一遍哈希值然后放到新数组对应的位置上去。但 JDK 1.8 的 HashMap 没有这么做。它利用了一个很巧妙的设计因为新容量是旧容量的 2 倍而容量始终是 2 的 n 次方所以每个元素的新位置要么是原来的索引要么是原来的索引 旧容量。判断方法是看(e.hash oldCap)的结果。如果结果是 0就留在原位置如果不是 0就移动到原位置 oldCap。举个例子旧容量是 16某个 key 的 hash 值是 20它在旧数组的位置是 20 15 4。扩容后新容量是 32我们算一下 20 16结果是 16不是 0所以它应该去的位置是 4 16 20。我当时自己手算了一遍发现确实是这样。灵感来源是因为 2 倍扩容后n-1的二进制低 n 位就多了一位从 1111 变成 11111所以新索引其实就是看 hash 值新增的那一位是 0 还是 1。是 0 就不动是 1 就加 oldCap。这个设计的妙处在于两点不需要重新计算 hash省了一次哈希计算的开销。能把旧数组里同一个桶的元素均匀分散到两个位置。因为 hash 值新增的那一位是 0 还是 1 可以认为是随机的所以原来冲突的元素会被拆成两拨分别放在原位置和原位置 oldCap上。我看明白这个之后确实觉得这个设计很漂亮。一个简单的位运算把扩容时最麻烦的两个问题一起解决了。为什么容量必须是 2 的 n 次方这个其实上面已经提到了HashMap 里很多操作都依赖数组长度是 2 的 n 次方。我刚学的时候没太在意这个觉得是不是 2 的 n 次方能有多大区别后来仔细算了算才发现差别很大。主要原因有三个1. 用位运算代替取模HashMap 计算索引的核心公式是hash (length - 1)。当 length 是 2 的 n 次方时这个位运算等价于hash % length。但位运算比取模快得多位运算直接操作二进制位而取模需要做除法。如果 length 不是 2 的 n 次方length - 1 的二进制就不是全 1 的形式这个位运算就不等价于取模了。2. 让索引分布更均匀还是回到上面那个公式。当 length 是 2 的 n 次方时length - 1 的二进制低 n 位全是 1比如 length16 时15 的二进制是 1111这样 hash 值的低 n 位每一位都能参与决定最终索引的位置。如果 length 不是 2 的 n 次方比如 length15length-114二进制 1110最后一位是 0。这意味着不管 hash 的最后一位是 0 还是 1与运算的结果最后一位都是 0所以索引的奇数位永远用不到数组空间浪费了一半碰撞概率也高了很多。我当时看到这个例子的时候心想这个设计约束确实是有道理的。不是 2 的 n 次方的话损失太大了。3. 扩容时不用重新计算 hash这个上面扩容那节已经讲过了。正是因为容量一直是 2 的 n 次方扩容时才能用hash oldCap来判断新位置。这三个原因是环环相扣的为了让位运算生效所以必须是 2 的 n 次方因为必须是 2 的 n 次方所以扩容时可以用位运算优化。整个设计是自洽的。负载因子 0.75 为什么刚刚好HashMap 默认的负载因子是 0.75。学到这里的时候我就好奇为什么是 0.75不是 0.5 或者 1负载因子的本质是空间和时间之间的取舍。如果负载因子太小比如 0.5HashMap 里用的桶还没装多少东西就开始扩容了。好处是冲突少每个桶里的链表短查得快。坏处是很多空间是空的浪费内存。如果负载因子太大比如 1HashMap 要把桶几乎装满才扩容。好处是空间利用率高。坏处是冲突变多每个桶里的链表长查得慢。0.75 就是在空间和时间之间取了一个平衡点。在理想情况下当负载因子是 0.75 时HashMap 在时间性能和空间利用率上都能接受。我从一本书上看到说0.75 这个值是基于泊松分布算出来的。当负载因子是 0.75 时链表长度超过 8 的概率非常低小于千万分之一所以正常情况下红黑树其实很少会触发生效大多数时候链表就够了。这也解释了为什么 JDK 1.8 要把树化阈值设为 8正常情况下链表长度几乎不会到 8到了说明冲突已经很严重了是时候升级了。几个值得一提的小特性HashMap 还有一些小细节我当初看的时候觉得挺有意思的。第一个是null 作为 key。如果你用 null 做 keyHashMap 的处理方式是直接把 hash 值设成 0然后放到 0 号桶里。所以 null key 只能有一个因为每次都会覆盖到同一个桶但 null value 可以有多个。我当时问自己如果我不给 key 传 null调 get(null) 会怎么样答案是不会抛异常因为 HashMap 明确处理了这种情况。不像 Hashtable传 null 进去就直接抛 NullPointerException 了。第二个是默认容量。HashMap 默认初始容量是 16每次扩容变成原来的 2 倍。如果你在构造的时候指定了一个初始容量HashMap 会把它调整成大于等于这个数的 2 的 n 次方。比如你传 10它实际用的是 16你传 30它用 32。保证数组长度始终是 2 的 n 次方。我之前有个问题往 HashMap 里存 20 个元素会扩容几次答案是只扩一次。因为前 12 个元素不用扩第 13 个触发扩容到 32后面 7 个第 14 到第 20 个都在容量范围内。怎么遍历一个 Map最后说说遍历。Map 不像 List 那样直接用索引遍历它有几种不同的方式。我开始最常用的是增强 for 循环加 entrySetfor(Map.EntryString,Integerentry:map.entrySet()){System.out.println(entry.getKey() - entry.getValue());}这个写法最直接能同时拿到 key 和 value。如果只需要 key可以用 keySetfor(Stringkey:map.keySet()){System.out.println(key);}如果需要边遍历边删除元素就得用迭代器IteratorMap.EntryString,Integeritmap.entrySet().iterator();while(it.hasNext()){Map.EntryString,Integerentryit.next();if(someCondition){it.remove();}}这个和 List 的迭代器是同一个道理只能在迭代器自己的 remove 方法里删不能在循环里直接调 map.remove。JDK 8 以后多了 Lambda 表达式和 forEach 方法代码变得更短了map.forEach((key,value)-System.out.println(key - value));还有 Stream API 的方式如果你需要过滤或者做一些转换map.entrySet().stream().filter(entry-entry.getValue()10).collect(Collectors.toMap(Map.Entry::getKey,Map.Entry::getValue));这几种方式我平时用 entrySet 最多偶尔用 forEach 和 Stream。迭代器通常只在需要遍历时删除元素的时候才用。写在最后写这篇东西的时候我一直想着当初啃 HashMap 源码的自己。那时候看到 put 和 get 的源码一行一行地对着文档看好几处看了好几遍才看懂。HashMap 给我的感觉是它看起来是个简单的容器但你越往里挖越能发现设计者的用心。数据结构从数组 链表演进到数组 链表 红黑树扩容时用hash oldCap来决定元素新位置把容量设计为 2 的 n 次方来实现位运算代替取模这些设计不是孤立的它们互相配合形成了一个有机的整体。学完这些之后我再去用 HashMap 的时候感觉就不一样了。以前它就是一个能放键值对的东西现在我知道它背后做了什么、为什么这么做。当然这篇讲的主要是 HashMap 单线程下的工作机制。它的线程安全问题、红黑树为什么不用平衡二叉树、equals 和 hashCode 怎么重写这些话题也挺重要的下篇再聊。如果这篇文章让你对 HashMap 有了一点新的理解那就够了。毕竟我也是这么一点点啃过来的。
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
