文档教程后端【免费下载链接】CodeGuide:books: 本代码库是作者小傅哥多年从事一线互联网 Java 开发的学习历程技术汇总旨在为大家提供一个清晰详细的学习教程侧重点更倾向编写Java核心内容。如果本仓库能为您提供帮助请给予支持(关注、点赞、分享)项目地址https://gitcode.com/gh_mirrors/code/CodeGuide点击查看免费下载本篇技术指南以 CodeGuide 仓库《面经手册》系列中关于 HashMap 核心数据结构的讲解为主体结合散列算法、初始化容量、负载因子、扩容元素拆分等知识点用理论推导 实验数据 源码印证的方式带你彻底吃透 JDK 1.8 中 HashMap 前五项核心设计。阅读并动手验证后你将能够徒手写出一个可用的散列存放雏形解释扰动函数为何能提升散列均匀性看懂tableSizeFor为什么能寻找 2 的幂次方最小值理解负载因子 0.75 的取舍逻辑以及扩容时如何借助e.hash oldCap免重算哈希完成链表拆分。一、前言为什么 HashMap 值得深度学习得益于Doug Lea老爷子的操刀让HashMap成为使用和面试最频繁的 API没办法设计的太优秀了HashMap 最早出现在 JDK 1.2 中底层基于散列算法实现。它允许 null 键和 null 值在计算键的哈希值时null 键哈希值为 0。HashMap 并不保证键值对的顺序这意味着在进行某些操作后键值对的顺序可能会发生变化。另外需要注意HashMap 是非线程安全类在多线程环境下可能会存在问题。随着几代版本的优化更新JDK 1.8 中的 HashMap 源码已经比较复杂涉及的知识点也非常多包括1、散列表实现、2、扰动函数、3、初始化容量、4、负载因子、5、扩容元素拆分、6、链表树化、7、红黑树、8、插入、9、查找、10、删除、11、遍历、12、分段锁等。因涉及知识点较多需要分开讲解本篇聚焦前五项也就是数据结构层面的核心设计。数据结构相关往往与数学分不开学习过程中建议下载相应源码进行实验验证。这个过程可能有点烧脑但学会后不用死记硬背就可以理解这部分知识。阅读提示本篇是《面经手册》系列的续篇此前已在 第2篇《数据结构HashCode为什么使用31作为乘数》 中验证过字符串hashCode选择 31 作为乘数的散列效果本篇将承接这一前提继续深入 HashMap。HashCode 本身是散列表的第一道散列而 HashMap 的扰动函数则是第二道散列两道散列叠加才构成最终的索引定位。二、散列表实现写一个最简单的 HashMap学习 HashMap 前最好的方式是先了解这是一种怎样的数据结构来存放数据。HashMap 经过多个版本迭代后乍一看代码还是很复杂的。就像你原来只穿个裤衩现在还有秋裤和风衣。所以我们先来看看最根本的 HashMap 是什么样也就是只穿裤衩是什么效果之后再分析它的源码。问题假设我们有一组 7 个字符串需要存放到数组中但要求在获取每个元素的时候时间复杂度是 O(1)。也就是说你不能通过循环遍历的方式进行获取而是要定位到数组 ID 直接获取相应的元素。方案如果说我们需要通过 ID 从数组中获取元素那么就需要把每个字符串都计算出一个在数组中的位置 ID。一个字符串最直接的获取跟数字相关的信息就是 HashCode可 HashCode 的取值范围太大了[-2147483648, 2147483647]不可能直接使用。那么就需要使用 HashCode 与数组长度做与运算得到一个可以在数组中出现的位置。如果说有两个元素得到同样的 ID那么这个数组 ID 下就存放两个字符串。1. 代码实现// 初始化一组字符串 ListString list new ArrayList(); list.add(jlkk); list.add(lopi); list.add(小傅哥); list.add(e4we); list.add(alpo); list.add(yhjk); list.add(plop); // 定义要存放的数组 String[] tab new String[8]; // 循环存放 for (String key : list) { int idx key.hashCode() (tab.length - 1); // 计算索引位置 System.out.println(String.format(key值%s Idx%d, key, idx)); if (null tab[idx]) { tab[idx] key; continue; } tab[idx] tab[idx] - key; } // 输出测试结果 System.out.println(JSON.toJSONString(tab));这段代码整体看起来非常简单主要包括以下内容初始化一组字符串集合这里初始化了 7 个。定义一个数组用于存放字符串注意这里的长度是 8也就是 2 的 3 次幂。这样的数组长度才会出现一个0111除高位以外都是 1 的特征也是为了散列。接下来就是循环存放数据计算出每个字符串在数组中的位置key.hashCode() (tab.length - 1)。在字符串存放到数组的过程中如果遇到相同的元素进行连接操作模拟链表的过程。最后输出存放结果。测试结果key值jlkk Idx2 key值lopi Idx4 key值小傅哥 Idx7 key值e4we Idx5 key值alpo Idx2 key值yhjk Idx0 key值plop Idx5 测试结果[yhjk,null,jlkk-alpo,null,lopi,e4we-plop,null,小傅哥]在测试结果中首先是计算出每个元素在数组的 Idx也有出现重复的位置。最后是测试结果的输出1、3、6 位置是空的2、5 位置有两个元素被链接起来如e4we-plop。这就达到了最基本的要求将串元素散列存放到数组中最后通过字符串元素的索引 ID 进行获取。这就是 HashMap 的一个最基本原理有了这个基础后面就更容易理解 HashMap 的源码实现。2. 这个简单的 HashMap 有哪些问题以上实现还只能算做一个散列数据存放的雏形放在实际使用中会暴露出一系列问题所有元素存放都需要获取一个索引位置如果元素位置不够散列、碰撞严重就失去了散列表存放的意义达不到预期性能。在获取索引 ID 的计算公式中需要数组长度是 2 的幂次方那么怎么进行初始化这个数组大小。数组越小碰撞越大数组越大碰撞越小时间与空间如何取舍。目前存放 7 个元素已经有两个位置都存放了 2 个字符串链表越来越长怎么优化。随着元素不断添加数组长度不足扩容时怎么把原有的元素拆分到新的位置上去。这些问题可以归纳为扰动函数、初始化容量、负载因子、扩容方法以及链表和红黑树转换的使用等。接下来逐个问题进行分析。源码印证这个数组 链表的雏形正是散列表的核心形态。仓库中 哈希表(散列) Hash 数据结构文档 给出了更完整的演化实验——从最初无碰撞处理、后写覆盖前写的HashMap01到引入拉链寻址LinkedList存放碰撞元素的HashMap02BySeparateChaining再到开放寻址、合并散列、杜鹃散列、跳房子散列、罗宾汉哈希等多种冲突解决策略可以对照理解 HashMap 最终为什么选择拉链寻址 红黑树这条路线。三、扰动函数让散列更均匀的第一道优化在 HashMap 存放元素时有这样一段代码来处理哈希值这是 Java 8 的散列值扰动函数用于优化散列效果static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }1. 为什么使用扰动函数理论上来说字符串的hashCode是一个 int 类型值可以直接作为数组下标且不会出现碰撞。但是这个hashCode的取值范围是 [-2147483648, 2147483647]有将近 40 亿的长度谁也不能把数组初始化得这么大内存也放不下。HashMap 默认初始化的 Map 大小是 16 个长度DEFAULT_INITIAL_CAPACITY 1 4所以获取的 Hash 值并不能直接作为下标使用需要与数组长度进行取模运算得到一个下标值也就是上面做的散列例子。HashMap 源码不只是直接获取哈希值还进行了一次扰动计算(h key.hashCode()) ^ (h 16)。把哈希值右移 16 位也就正好是自身长度的一半之后与原哈希值做异或运算这样就混合了原哈希值中的高位和低位增大了随机性。通俗地说使用扰动函数就是为了增加随机性让数据元素更加均衡地散列减少碰撞。数组长度为 2 的幂次方时(n - 1) hash实际只使用了 hash 的低位例如长度 16 只用低 4 位而高 16 位完全不参与索引计算。若两个对象的 hashCode 高位不同、低位相同就会产生碰撞扰动函数把高位折叠到低位正是为了解决这类碰撞。2. 实验验证扰动函数从上面的分析可以看出扰动函数使用了哈希值的高半区和低半区做异或混合原始哈希码的高位和低位以此加大低位区的随机性。但看不到实验数据的话这终究是一段理论所以这里做一个实验选取 10 万个单词词库定义 128 位长度的数组格子分别计算在扰动和不扰动下10 万单词的下标分配到 128 个格子的数量统计各个格子数量生成波动曲线。如果扰动函数下的波动曲线相对更平稳那么证明扰动函数有效果。扰动函数对比方法public class Disturb { public static int disturbHashIdx(String key, int size) { return (size - 1) (key.hashCode() ^ (key.hashCode() 16)); } public static int hashIdx(String key, int size) { return (size - 1) key.hashCode(); } }disturbHashIdx扰动函数下下标值计算。hashIdx非扰动函数下下标值计算。单元测试// 10万单词已经初始化到words中 Test public void test_disturb() { MapInteger, Integer map new HashMap(16); for (String word : words) { // 使用扰动函数 int idx Disturb.disturbHashIdx(word, 128); // 不使用扰动函数 // int idx Disturb.hashIdx(word, 128); if (map.containsKey(idx)) { Integer integer map.get(idx); map.put(idx, integer); } else { map.put(idx, 1); } } System.out.println(map.values()); }以上分别统计两种函数下的下标值分配最终将统计结果放入 excel 中生成图表。实验数据为10 万个不重复的单词、128 个格子相当于 128 长度的数组。从两种对比结果可以明确看到在使用了扰动函数后数据分配得更加均匀了数据分配均匀也就是散列的效果更好减少了 hash 碰撞让数据存放和获取的效率更佳。源码印证扰动函数并非 HashMap 独有。仓库中 基于Hash散列数据库路由组件设计 展示了一个真实的生产级应用场景——在实现分库分表路由中间件时切面拦截逻辑里直接复用了与 HashMap 相同的扰动函数写法int idx (size - 1) (dbKeyAttr.hashCode() ^ (dbKeyAttr.hashCode() 16));随后把总索引折算到第几个库、第几张表并通过 ThreadLocal 传递。这说明散列算法 寻址方式正是 HashMap 源码中最值得提炼并落地复用的部分。四、初始化容量与负载因子从模仿 HashMap 的例子以及 HashMap 默认的初始化大小都可以知道散列数组需要一个 2 的幂次方的长度因为只有 2 的幂次方减 1 的时候才会出现01111这样的值。那么这里就有一个问题在初始化 HashMap 的时候如果传一个 17 的值new HashMap(17);它会怎么处理呢1. 寻找 2 的幂次方最小值在 HashMap 的初始化中有这样一段方法public HashMap(int initialCapacity, float loadFactor) { ... this.loadFactor loadFactor; this.threshold tableSizeFor(initialCapacity); }阈值threshold通过方法tableSizeFor进行计算是根据初始化容量来计算的。这个方法也就是要寻找比初始值大的、最小的那个 2 进制数值。比如传了 17应该找到的是 322 的 4 次幂是 16 17所以找到 2 的 5 次幂 32。计算阈值大小的方法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; }MAXIMUM_CAPACITY 1 30这是临界范围也就是最大的 Map 集合。乍一看可能有点晕怎么都在向右移位 1、2、4、8、16这主要是为了把二进制的各个位置都填上 1。当二进制的各个位置都是 1 以后就是一个标准的 2 的幂次方减 1 了最后把结果加 1 再返回即可。以传 17 为例推算一遍cap 17n 16二进制0001 0000。经过n | n 1得到0001 1000再n | n 2得到0001 1110再n | n 4得到0001 1111后续右移 8、16 已经全部是 1 不再变化最后n 1 32。整个过程就是先把低 5 位全部填成 1再加 1 进位从而得到 2 的幂次方。2. 为什么必须是 2 的幂次方static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16散列数组必须是 2 的幂次方根本原因在于索引计算的优化(n - 1) hash等价于hash % n但位运算比取模运算高效得多。更关键的是只有n是 2 的幂次方时n - 1才会是低位全 1 的掩码运算结果才恰好落在[0, n-1]区间内。这一点在第 5 章扩容元素拆分中还会再次体现——2 的幂次方长度正是免重算哈希拆分设计能够成立的前提。3. 负载因子static final float DEFAULT_LOAD_FACTOR 0.75f;负载因子是做什么的负载因子可以理解成一辆车可承重重量超过某个阈值时把货放到新的车上。在 HashMap 中负载因子决定了数据量达到多少以后进行扩容。这里要提到上面做的 HashMap 例子准备了 7 个元素但最后还有 3 个位置空余2 个位置存放了 2 个元素。所以可能即使数据比数组容量大时也不一定能正正好好的把数组占满而是在某些下标位置出现大量碰撞只能在同一个位置用链表存放这样就失去了 Map 数组的性能。所以要选择一个合理的大小下进行扩容。默认值 0.75 就是说当阈值容量占了 3/4 时赶紧扩容减少 Hash 碰撞。同时 0.75 是一个默认构造值在创建 HashMap 时也可以调整。比如你希望用更多的空间换取时间可以把负载因子调得更小一些减少碰撞反之调大负载因子则可以减少空间占用但会增加碰撞与链表长度。源码印证负载因子与扩容阈值的关系在resize()中有明确体现——调用无参构造方法时数组桶容量为默认容量1 416阈值是默认容量与负载因子的乘积newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);即 16 * 0.75 12。当元素个数size threshold时触发扩容。这部分完整源码位于 第4篇《HashMap数据插入、查找、删除、遍历源码分析》 的扩容机制小节。五、扩容元素拆分免重算哈希的巧妙设计为什么扩容因为数组长度不足了。扩容最直接的问题就是需要把元素拆分到新的数组中。拆分元素的过程中原 JDK 1.7 中需要重新计算哈希值但到 JDK 1.8 中已经进行优化不再需要重新计算提升了拆分的性能设计得非常巧妙。1. 测试数据Test public void test_hashMap() { ListString list new ArrayList(); list.add(jlkk); list.add(lopi); list.add(jmdw); list.add(e4we); list.add(io98); list.add(nmhg); list.add(vfg6); list.add(gfrt); list.add(alpo); list.add(vfbh); list.add(bnhj); list.add(zuio); list.add(iu8e); list.add(yhjk); list.add(plop); list.add(dd0p); for (String key : list) { int hash key.hashCode() ^ (key.hashCode() 16); System.out.println(字符串 key \tIdx(16) ((16 - 1) hash) \tBit值 Integer.toBinaryString(hash) - Integer.toBinaryString(hash 16) \t\tIdx(32) ((32 - 1) hash)); System.out.println(Integer.toBinaryString(key.hashCode()) Integer.toBinaryString(hash) Integer.toBinaryString((32 - 1) hash)); } }测试结果字符串jlkk Idx(16)3 Bit值1100011101001000010011 - 10000 Idx(32)19 1100011101001000100010 1100011101001000010011 10011 字符串lopi Idx(16)14 Bit值1100101100011010001110 - 0 Idx(32)14 1100101100011010111100 1100101100011010001110 1110 字符串jmdw Idx(16)7 Bit值1100011101010100100111 - 0 Idx(32)7 1100011101010100010110 1100011101010100100111 111 字符串e4we Idx(16)3 Bit值1011101011101101010011 - 10000 Idx(32)19 1011101011101101111101 1011101011101101010011 10011 字符串io98 Idx(16)4 Bit值1100010110001011110100 - 10000 Idx(32)20 1100010110001011000101 1100010110001011110100 10100 字符串nmhg Idx(16)13 Bit值1100111010011011001101 - 0 Idx(32)13 1100111010011011111110 1100111010011011001101 1101 字符串vfg6 Idx(16)8 Bit值1101110010111101101000 - 0 Idx(32)8 1101110010111101011111 1101110010111101101000 1000 字符串gfrt Idx(16)1 Bit值1100000101111101010001 - 10000 Idx(32)17 1100000101111101100001 1100000101111101010001 10001 字符串alpo Idx(16)7 Bit值1011011011101101000111 - 0 Idx(32)7 1011011011101101101010 1011011011101101000111 111 字符串vfbh Idx(16)1 Bit值1101110010111011000001 - 0 Idx(32)1 1101110010111011110110 1101110010111011000001 1 字符串bnhj Idx(16)0 Bit值1011100011011001100000 - 0 Idx(32)0 1011100011011001001110 1011100011011001100000 0 字符串zuio Idx(16)8 Bit值1110010011100110011000 - 10000 Idx(32)24 1110010011100110100001 1110010011100110011000 11000 字符串iu8e Idx(16)8 Bit值1100010111100101101000 - 0 Idx(32)8 1100010111100101011001 1100010111100101101000 1000 字符串yhjk Idx(16)8 Bit值1110001001010010101000 - 0 Idx(32)8 1110001001010010010000 1110001001010010101000 1000 字符串plop Idx(16)9 Bit值1101001000110011101001 - 0 Idx(32)9 1101001000110011011101 1101001000110011101001 1001 字符串dd0p Idx(16)14 Bit值1011101111001011101110 - 0 Idx(32)14 1011101111001011000000 1011101111001011101110 1110这里随机使用一些字符串计算它们分别在 16 位长度和 32 位长度数组下的索引分配情况观察哪些数据被重新路由到了新的地址。同时可以观察出一个非常重要的信息原哈希值与扩容新增出来的长度 16 进行 运算如果值等于 0则下标位置不变如果不为 0那么新的位置则是原来位置上加 16。这样一来就不需要重新计算每一个数组中元素的哈希值了。2. 数据迁移e.hash oldCap 的判断原理对 31 取模保留低 5 位对 15 取模保留低 4 位两者的差异就在于第 5 位是否为 1是 1 则需要加上增量是 0 则不需要改变。其中元素zuio因计算结果hash oldCap低位第 5 位为 1被迁移到下标位置 24同时使用重新计算哈希值的方式验证确实分配到 24 的位置。因为这是在二进制计算中补 1 的过程所以可以通过上面简化的方式确定哈希值的新位置。那么为什么e.hash oldCap 0可以判断当前节点是否需要移位而不是再次计算 hash以原始长度 16 为例old: 10: 0000 1010 15: 0000 1111 : 0000 1010 new: 10: 0000 1010 31: 0001 1111 : 0000 1010从上面的示例可以很轻易地看出两次indexFor()的差别只是第二次参与与运算时比第一次左边有一位从 0 变为 1而这个变化的 1 刚好是oldCap。那么只需要判断原 key 的 hash 这个位上是否为 1若是 1则需要移动至oldCap i的槽位若为 0则不需要移动。这也是 HashMap 的长度必须保证是 2 的幂次方的原因。正因为这种环环相扣的设计HashMap 的loadFactor选值为 3/4 也就能理解了table.length * 3/4可以被优化为位运算形式table.length - (table.length 2)JAVA 的位运算比乘除的效率更高所以取 3/4 在保证 hash 冲突小的情况下兼顾了效率。3. 源码中的拆分实现扩容拆分的完整实现在 JDK 1.8 的resize()方法中其链表拆分核心逻辑如下完整代码见 第4篇《HashMap数据插入、查找、删除、遍历源码分析》 的扩容机制小节// 这里是链表如果当前是按照链表存放的则将链表节点按原顺序进行分组 NodeK,V loHead null, loTail null; NodeK,V hiHead null, hiTail null; NodeK,V next; do { next e.next; if ((e.hash oldCap) 0) { // 第5位为0留在原下标位置组成lo链表 if (loTail null) loHead e; else loTail.next e; loTail e; } else { // 第5位为1迁移到 原位置oldCap组成hi链表 if (hiTail null) hiHead e; else hiTail.next e; hiTail e; } } while ((e next) ! null); // 将分组后的链表映射到桶中 if (loTail ! null) { loTail.next null; newTab[j] loHead; // 低位链表留在原下标 } if (hiTail ! null) { hiTail.next null; newTab[j oldCap] hiHead; // 高位链表迁移到 j oldCap }扩容时一次遍历仅凭一次e.hash oldCap位运算就把一个桶上的链表一分为二低位链表lo原地不动高位链表hi整体平移到j oldCap既保留了链表元素的原始顺序又避免了 O(n) 次哈希重算。若是红黑树节点则调用((TreeNodeK,V)e).split(this, newTab, j, oldCap)进行树拆分本质也是按照(e.hash oldCap) 0分成 lo/hi 两组再按需untreeify转回链表或重建树。源码印证为什么链表过长的兜底手段不是树化而是扩容在 第4篇 的treeifyBin分析中指出链表树化有两个条件链表长度大于等于 8TREEIFY_THRESHOLD且桶容量大于 64MIN_TREEIFY_CAPACITY。如果桶容量小于 64treeifyBin会先resize()扩容而不是树化——因为扩容后链表数据会被拆分到不同的桶节点上链表长度自然缩短这正好呼应了本篇扩容元素拆分的设计价值。六、总结如果坚持看完这部分内容并按照文中的例子进行相应的实验验证那么一定可以学会这五项知识点1、散列表实现、2、扰动函数、3、初始化容量、4、负载因子、5、扩容元素拆分。散列表实现核心是HashCode 计算索引 2 的幂次方数组 冲突链表存放一切后续优化都围绕减少碰撞、提升定位效率展开。扰动函数(h key.hashCode()) ^ (h 16)把高 16 位折叠到低 16 位10 万单词实验证明扰动后散列分布显著更均匀。初始化容量tableSizeFor通过 5 次右移或运算把任意容量规整到最近的 2 的幂次方为位运算索引与免重算扩容奠定基础。负载因子0.75 是时间与空间的折中同时 3/4 可用位运算table.length - (table.length 2)表达兼顾效率。扩容元素拆分利用e.hash oldCap一次位运算即可判定元素留原地还是迁移到j oldCapJDK 1.8 相比 1.7 省去了全部元素的哈希重算。对本篇提到的链表树化、红黑树以及插入、查找、删除、遍历等剩余知识点可以继续深入阅读仓库中的系列文档第4篇《HashMap数据插入、查找、删除、遍历源码分析》插入流程、扩容机制、链表树化treeifyBin、红黑树转链untreeify、查找删除遍历源码第5篇《看图说话讲解2-3平衡树「红黑树的前身」》 与 第6篇《带着面试题学习红黑树操作原理》从 2-3-4 树模型推导红黑树五条规则与染色、旋转原理红黑树 Red Black Tree 数据结构文档 与 哈希表(散列) Hash 数据结构文档提供完整的代码级数据结构实现基于Hash散列数据库路由组件设计把扰动函数、哈希寻址落地到分库分表中间件是源码学习到造火箭的完整范例。赞分享文档教程后端【免费下载链接】CodeGuide:books: 本代码库是作者小傅哥多年从事一线互联网 Java 开发的学习历程技术汇总旨在为大家提供一个清晰详细的学习教程侧重点更倾向编写Java核心内容。如果本仓库能为您提供帮助请给予支持(关注、点赞、分享)项目地址https://gitcode.com/gh_mirrors/code/CodeGuide点击查看免费下载相关推荐hello-algo 链式地址哈希表实现指南HashMapChaining、负载因子与再哈希扩容hello algo 链式地址哈希表实现指南HashMapChaining、负载因子与再哈希扩容 本文基于 hello algo 仓库中 链式地址哈希表的 P教程文档示例工程教育Java 面经手册第4篇HashMap 数据插入、查找、删除、遍历源码深度分析含链表树化与遍历顺序Java 面经手册第4篇HashMap 数据插入、查找、删除、遍历源码深度分析含链表树化与遍历顺序 本文是《Java 面经手册》系列的第 4 篇延续第文档教程后端面经手册 · 第16篇《码农会锁ReentrantLock 之公平锁讲解和实现》面经手册 · 第16篇《码农会锁ReentrantLock 之公平锁讲解和实现》 本篇技术指南聚焦于 Java 并发编程中 ReentrantLock 公平锁文档教程后端上一篇ToolJet Tags 组件完全指南用数组数据渲染标签、配置样式与动态数据下一篇Lucide 图标字体配色指南用 CSS color 属性自定义图标颜色创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 面经手册第3篇实践精讲：HashMap 散列表实现、扰动函数、负载因子与扩容链表拆分全解析
文档教程后端【免费下载链接】CodeGuide:books: 本代码库是作者小傅哥多年从事一线互联网 Java 开发的学习历程技术汇总旨在为大家提供一个清晰详细的学习教程侧重点更倾向编写Java核心内容。如果本仓库能为您提供帮助请给予支持(关注、点赞、分享)项目地址https://gitcode.com/gh_mirrors/code/CodeGuide点击查看免费下载本篇技术指南以 CodeGuide 仓库《面经手册》系列中关于 HashMap 核心数据结构的讲解为主体结合散列算法、初始化容量、负载因子、扩容元素拆分等知识点用理论推导 实验数据 源码印证的方式带你彻底吃透 JDK 1.8 中 HashMap 前五项核心设计。阅读并动手验证后你将能够徒手写出一个可用的散列存放雏形解释扰动函数为何能提升散列均匀性看懂tableSizeFor为什么能寻找 2 的幂次方最小值理解负载因子 0.75 的取舍逻辑以及扩容时如何借助e.hash oldCap免重算哈希完成链表拆分。一、前言为什么 HashMap 值得深度学习得益于Doug Lea老爷子的操刀让HashMap成为使用和面试最频繁的 API没办法设计的太优秀了HashMap 最早出现在 JDK 1.2 中底层基于散列算法实现。它允许 null 键和 null 值在计算键的哈希值时null 键哈希值为 0。HashMap 并不保证键值对的顺序这意味着在进行某些操作后键值对的顺序可能会发生变化。另外需要注意HashMap 是非线程安全类在多线程环境下可能会存在问题。随着几代版本的优化更新JDK 1.8 中的 HashMap 源码已经比较复杂涉及的知识点也非常多包括1、散列表实现、2、扰动函数、3、初始化容量、4、负载因子、5、扩容元素拆分、6、链表树化、7、红黑树、8、插入、9、查找、10、删除、11、遍历、12、分段锁等。因涉及知识点较多需要分开讲解本篇聚焦前五项也就是数据结构层面的核心设计。数据结构相关往往与数学分不开学习过程中建议下载相应源码进行实验验证。这个过程可能有点烧脑但学会后不用死记硬背就可以理解这部分知识。阅读提示本篇是《面经手册》系列的续篇此前已在 第2篇《数据结构HashCode为什么使用31作为乘数》 中验证过字符串hashCode选择 31 作为乘数的散列效果本篇将承接这一前提继续深入 HashMap。HashCode 本身是散列表的第一道散列而 HashMap 的扰动函数则是第二道散列两道散列叠加才构成最终的索引定位。二、散列表实现写一个最简单的 HashMap学习 HashMap 前最好的方式是先了解这是一种怎样的数据结构来存放数据。HashMap 经过多个版本迭代后乍一看代码还是很复杂的。就像你原来只穿个裤衩现在还有秋裤和风衣。所以我们先来看看最根本的 HashMap 是什么样也就是只穿裤衩是什么效果之后再分析它的源码。问题假设我们有一组 7 个字符串需要存放到数组中但要求在获取每个元素的时候时间复杂度是 O(1)。也就是说你不能通过循环遍历的方式进行获取而是要定位到数组 ID 直接获取相应的元素。方案如果说我们需要通过 ID 从数组中获取元素那么就需要把每个字符串都计算出一个在数组中的位置 ID。一个字符串最直接的获取跟数字相关的信息就是 HashCode可 HashCode 的取值范围太大了[-2147483648, 2147483647]不可能直接使用。那么就需要使用 HashCode 与数组长度做与运算得到一个可以在数组中出现的位置。如果说有两个元素得到同样的 ID那么这个数组 ID 下就存放两个字符串。1. 代码实现// 初始化一组字符串 ListString list new ArrayList(); list.add(jlkk); list.add(lopi); list.add(小傅哥); list.add(e4we); list.add(alpo); list.add(yhjk); list.add(plop); // 定义要存放的数组 String[] tab new String[8]; // 循环存放 for (String key : list) { int idx key.hashCode() (tab.length - 1); // 计算索引位置 System.out.println(String.format(key值%s Idx%d, key, idx)); if (null tab[idx]) { tab[idx] key; continue; } tab[idx] tab[idx] - key; } // 输出测试结果 System.out.println(JSON.toJSONString(tab));这段代码整体看起来非常简单主要包括以下内容初始化一组字符串集合这里初始化了 7 个。定义一个数组用于存放字符串注意这里的长度是 8也就是 2 的 3 次幂。这样的数组长度才会出现一个0111除高位以外都是 1 的特征也是为了散列。接下来就是循环存放数据计算出每个字符串在数组中的位置key.hashCode() (tab.length - 1)。在字符串存放到数组的过程中如果遇到相同的元素进行连接操作模拟链表的过程。最后输出存放结果。测试结果key值jlkk Idx2 key值lopi Idx4 key值小傅哥 Idx7 key值e4we Idx5 key值alpo Idx2 key值yhjk Idx0 key值plop Idx5 测试结果[yhjk,null,jlkk-alpo,null,lopi,e4we-plop,null,小傅哥]在测试结果中首先是计算出每个元素在数组的 Idx也有出现重复的位置。最后是测试结果的输出1、3、6 位置是空的2、5 位置有两个元素被链接起来如e4we-plop。这就达到了最基本的要求将串元素散列存放到数组中最后通过字符串元素的索引 ID 进行获取。这就是 HashMap 的一个最基本原理有了这个基础后面就更容易理解 HashMap 的源码实现。2. 这个简单的 HashMap 有哪些问题以上实现还只能算做一个散列数据存放的雏形放在实际使用中会暴露出一系列问题所有元素存放都需要获取一个索引位置如果元素位置不够散列、碰撞严重就失去了散列表存放的意义达不到预期性能。在获取索引 ID 的计算公式中需要数组长度是 2 的幂次方那么怎么进行初始化这个数组大小。数组越小碰撞越大数组越大碰撞越小时间与空间如何取舍。目前存放 7 个元素已经有两个位置都存放了 2 个字符串链表越来越长怎么优化。随着元素不断添加数组长度不足扩容时怎么把原有的元素拆分到新的位置上去。这些问题可以归纳为扰动函数、初始化容量、负载因子、扩容方法以及链表和红黑树转换的使用等。接下来逐个问题进行分析。源码印证这个数组 链表的雏形正是散列表的核心形态。仓库中 哈希表(散列) Hash 数据结构文档 给出了更完整的演化实验——从最初无碰撞处理、后写覆盖前写的HashMap01到引入拉链寻址LinkedList存放碰撞元素的HashMap02BySeparateChaining再到开放寻址、合并散列、杜鹃散列、跳房子散列、罗宾汉哈希等多种冲突解决策略可以对照理解 HashMap 最终为什么选择拉链寻址 红黑树这条路线。三、扰动函数让散列更均匀的第一道优化在 HashMap 存放元素时有这样一段代码来处理哈希值这是 Java 8 的散列值扰动函数用于优化散列效果static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }1. 为什么使用扰动函数理论上来说字符串的hashCode是一个 int 类型值可以直接作为数组下标且不会出现碰撞。但是这个hashCode的取值范围是 [-2147483648, 2147483647]有将近 40 亿的长度谁也不能把数组初始化得这么大内存也放不下。HashMap 默认初始化的 Map 大小是 16 个长度DEFAULT_INITIAL_CAPACITY 1 4所以获取的 Hash 值并不能直接作为下标使用需要与数组长度进行取模运算得到一个下标值也就是上面做的散列例子。HashMap 源码不只是直接获取哈希值还进行了一次扰动计算(h key.hashCode()) ^ (h 16)。把哈希值右移 16 位也就正好是自身长度的一半之后与原哈希值做异或运算这样就混合了原哈希值中的高位和低位增大了随机性。通俗地说使用扰动函数就是为了增加随机性让数据元素更加均衡地散列减少碰撞。数组长度为 2 的幂次方时(n - 1) hash实际只使用了 hash 的低位例如长度 16 只用低 4 位而高 16 位完全不参与索引计算。若两个对象的 hashCode 高位不同、低位相同就会产生碰撞扰动函数把高位折叠到低位正是为了解决这类碰撞。2. 实验验证扰动函数从上面的分析可以看出扰动函数使用了哈希值的高半区和低半区做异或混合原始哈希码的高位和低位以此加大低位区的随机性。但看不到实验数据的话这终究是一段理论所以这里做一个实验选取 10 万个单词词库定义 128 位长度的数组格子分别计算在扰动和不扰动下10 万单词的下标分配到 128 个格子的数量统计各个格子数量生成波动曲线。如果扰动函数下的波动曲线相对更平稳那么证明扰动函数有效果。扰动函数对比方法public class Disturb { public static int disturbHashIdx(String key, int size) { return (size - 1) (key.hashCode() ^ (key.hashCode() 16)); } public static int hashIdx(String key, int size) { return (size - 1) key.hashCode(); } }disturbHashIdx扰动函数下下标值计算。hashIdx非扰动函数下下标值计算。单元测试// 10万单词已经初始化到words中 Test public void test_disturb() { MapInteger, Integer map new HashMap(16); for (String word : words) { // 使用扰动函数 int idx Disturb.disturbHashIdx(word, 128); // 不使用扰动函数 // int idx Disturb.hashIdx(word, 128); if (map.containsKey(idx)) { Integer integer map.get(idx); map.put(idx, integer); } else { map.put(idx, 1); } } System.out.println(map.values()); }以上分别统计两种函数下的下标值分配最终将统计结果放入 excel 中生成图表。实验数据为10 万个不重复的单词、128 个格子相当于 128 长度的数组。从两种对比结果可以明确看到在使用了扰动函数后数据分配得更加均匀了数据分配均匀也就是散列的效果更好减少了 hash 碰撞让数据存放和获取的效率更佳。源码印证扰动函数并非 HashMap 独有。仓库中 基于Hash散列数据库路由组件设计 展示了一个真实的生产级应用场景——在实现分库分表路由中间件时切面拦截逻辑里直接复用了与 HashMap 相同的扰动函数写法int idx (size - 1) (dbKeyAttr.hashCode() ^ (dbKeyAttr.hashCode() 16));随后把总索引折算到第几个库、第几张表并通过 ThreadLocal 传递。这说明散列算法 寻址方式正是 HashMap 源码中最值得提炼并落地复用的部分。四、初始化容量与负载因子从模仿 HashMap 的例子以及 HashMap 默认的初始化大小都可以知道散列数组需要一个 2 的幂次方的长度因为只有 2 的幂次方减 1 的时候才会出现01111这样的值。那么这里就有一个问题在初始化 HashMap 的时候如果传一个 17 的值new HashMap(17);它会怎么处理呢1. 寻找 2 的幂次方最小值在 HashMap 的初始化中有这样一段方法public HashMap(int initialCapacity, float loadFactor) { ... this.loadFactor loadFactor; this.threshold tableSizeFor(initialCapacity); }阈值threshold通过方法tableSizeFor进行计算是根据初始化容量来计算的。这个方法也就是要寻找比初始值大的、最小的那个 2 进制数值。比如传了 17应该找到的是 322 的 4 次幂是 16 17所以找到 2 的 5 次幂 32。计算阈值大小的方法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; }MAXIMUM_CAPACITY 1 30这是临界范围也就是最大的 Map 集合。乍一看可能有点晕怎么都在向右移位 1、2、4、8、16这主要是为了把二进制的各个位置都填上 1。当二进制的各个位置都是 1 以后就是一个标准的 2 的幂次方减 1 了最后把结果加 1 再返回即可。以传 17 为例推算一遍cap 17n 16二进制0001 0000。经过n | n 1得到0001 1000再n | n 2得到0001 1110再n | n 4得到0001 1111后续右移 8、16 已经全部是 1 不再变化最后n 1 32。整个过程就是先把低 5 位全部填成 1再加 1 进位从而得到 2 的幂次方。2. 为什么必须是 2 的幂次方static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16散列数组必须是 2 的幂次方根本原因在于索引计算的优化(n - 1) hash等价于hash % n但位运算比取模运算高效得多。更关键的是只有n是 2 的幂次方时n - 1才会是低位全 1 的掩码运算结果才恰好落在[0, n-1]区间内。这一点在第 5 章扩容元素拆分中还会再次体现——2 的幂次方长度正是免重算哈希拆分设计能够成立的前提。3. 负载因子static final float DEFAULT_LOAD_FACTOR 0.75f;负载因子是做什么的负载因子可以理解成一辆车可承重重量超过某个阈值时把货放到新的车上。在 HashMap 中负载因子决定了数据量达到多少以后进行扩容。这里要提到上面做的 HashMap 例子准备了 7 个元素但最后还有 3 个位置空余2 个位置存放了 2 个元素。所以可能即使数据比数组容量大时也不一定能正正好好的把数组占满而是在某些下标位置出现大量碰撞只能在同一个位置用链表存放这样就失去了 Map 数组的性能。所以要选择一个合理的大小下进行扩容。默认值 0.75 就是说当阈值容量占了 3/4 时赶紧扩容减少 Hash 碰撞。同时 0.75 是一个默认构造值在创建 HashMap 时也可以调整。比如你希望用更多的空间换取时间可以把负载因子调得更小一些减少碰撞反之调大负载因子则可以减少空间占用但会增加碰撞与链表长度。源码印证负载因子与扩容阈值的关系在resize()中有明确体现——调用无参构造方法时数组桶容量为默认容量1 416阈值是默认容量与负载因子的乘积newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);即 16 * 0.75 12。当元素个数size threshold时触发扩容。这部分完整源码位于 第4篇《HashMap数据插入、查找、删除、遍历源码分析》 的扩容机制小节。五、扩容元素拆分免重算哈希的巧妙设计为什么扩容因为数组长度不足了。扩容最直接的问题就是需要把元素拆分到新的数组中。拆分元素的过程中原 JDK 1.7 中需要重新计算哈希值但到 JDK 1.8 中已经进行优化不再需要重新计算提升了拆分的性能设计得非常巧妙。1. 测试数据Test public void test_hashMap() { ListString list new ArrayList(); list.add(jlkk); list.add(lopi); list.add(jmdw); list.add(e4we); list.add(io98); list.add(nmhg); list.add(vfg6); list.add(gfrt); list.add(alpo); list.add(vfbh); list.add(bnhj); list.add(zuio); list.add(iu8e); list.add(yhjk); list.add(plop); list.add(dd0p); for (String key : list) { int hash key.hashCode() ^ (key.hashCode() 16); System.out.println(字符串 key \tIdx(16) ((16 - 1) hash) \tBit值 Integer.toBinaryString(hash) - Integer.toBinaryString(hash 16) \t\tIdx(32) ((32 - 1) hash)); System.out.println(Integer.toBinaryString(key.hashCode()) Integer.toBinaryString(hash) Integer.toBinaryString((32 - 1) hash)); } }测试结果字符串jlkk Idx(16)3 Bit值1100011101001000010011 - 10000 Idx(32)19 1100011101001000100010 1100011101001000010011 10011 字符串lopi Idx(16)14 Bit值1100101100011010001110 - 0 Idx(32)14 1100101100011010111100 1100101100011010001110 1110 字符串jmdw Idx(16)7 Bit值1100011101010100100111 - 0 Idx(32)7 1100011101010100010110 1100011101010100100111 111 字符串e4we Idx(16)3 Bit值1011101011101101010011 - 10000 Idx(32)19 1011101011101101111101 1011101011101101010011 10011 字符串io98 Idx(16)4 Bit值1100010110001011110100 - 10000 Idx(32)20 1100010110001011000101 1100010110001011110100 10100 字符串nmhg Idx(16)13 Bit值1100111010011011001101 - 0 Idx(32)13 1100111010011011111110 1100111010011011001101 1101 字符串vfg6 Idx(16)8 Bit值1101110010111101101000 - 0 Idx(32)8 1101110010111101011111 1101110010111101101000 1000 字符串gfrt Idx(16)1 Bit值1100000101111101010001 - 10000 Idx(32)17 1100000101111101100001 1100000101111101010001 10001 字符串alpo Idx(16)7 Bit值1011011011101101000111 - 0 Idx(32)7 1011011011101101101010 1011011011101101000111 111 字符串vfbh Idx(16)1 Bit值1101110010111011000001 - 0 Idx(32)1 1101110010111011110110 1101110010111011000001 1 字符串bnhj Idx(16)0 Bit值1011100011011001100000 - 0 Idx(32)0 1011100011011001001110 1011100011011001100000 0 字符串zuio Idx(16)8 Bit值1110010011100110011000 - 10000 Idx(32)24 1110010011100110100001 1110010011100110011000 11000 字符串iu8e Idx(16)8 Bit值1100010111100101101000 - 0 Idx(32)8 1100010111100101011001 1100010111100101101000 1000 字符串yhjk Idx(16)8 Bit值1110001001010010101000 - 0 Idx(32)8 1110001001010010010000 1110001001010010101000 1000 字符串plop Idx(16)9 Bit值1101001000110011101001 - 0 Idx(32)9 1101001000110011011101 1101001000110011101001 1001 字符串dd0p Idx(16)14 Bit值1011101111001011101110 - 0 Idx(32)14 1011101111001011000000 1011101111001011101110 1110这里随机使用一些字符串计算它们分别在 16 位长度和 32 位长度数组下的索引分配情况观察哪些数据被重新路由到了新的地址。同时可以观察出一个非常重要的信息原哈希值与扩容新增出来的长度 16 进行 运算如果值等于 0则下标位置不变如果不为 0那么新的位置则是原来位置上加 16。这样一来就不需要重新计算每一个数组中元素的哈希值了。2. 数据迁移e.hash oldCap 的判断原理对 31 取模保留低 5 位对 15 取模保留低 4 位两者的差异就在于第 5 位是否为 1是 1 则需要加上增量是 0 则不需要改变。其中元素zuio因计算结果hash oldCap低位第 5 位为 1被迁移到下标位置 24同时使用重新计算哈希值的方式验证确实分配到 24 的位置。因为这是在二进制计算中补 1 的过程所以可以通过上面简化的方式确定哈希值的新位置。那么为什么e.hash oldCap 0可以判断当前节点是否需要移位而不是再次计算 hash以原始长度 16 为例old: 10: 0000 1010 15: 0000 1111 : 0000 1010 new: 10: 0000 1010 31: 0001 1111 : 0000 1010从上面的示例可以很轻易地看出两次indexFor()的差别只是第二次参与与运算时比第一次左边有一位从 0 变为 1而这个变化的 1 刚好是oldCap。那么只需要判断原 key 的 hash 这个位上是否为 1若是 1则需要移动至oldCap i的槽位若为 0则不需要移动。这也是 HashMap 的长度必须保证是 2 的幂次方的原因。正因为这种环环相扣的设计HashMap 的loadFactor选值为 3/4 也就能理解了table.length * 3/4可以被优化为位运算形式table.length - (table.length 2)JAVA 的位运算比乘除的效率更高所以取 3/4 在保证 hash 冲突小的情况下兼顾了效率。3. 源码中的拆分实现扩容拆分的完整实现在 JDK 1.8 的resize()方法中其链表拆分核心逻辑如下完整代码见 第4篇《HashMap数据插入、查找、删除、遍历源码分析》 的扩容机制小节// 这里是链表如果当前是按照链表存放的则将链表节点按原顺序进行分组 NodeK,V loHead null, loTail null; NodeK,V hiHead null, hiTail null; NodeK,V next; do { next e.next; if ((e.hash oldCap) 0) { // 第5位为0留在原下标位置组成lo链表 if (loTail null) loHead e; else loTail.next e; loTail e; } else { // 第5位为1迁移到 原位置oldCap组成hi链表 if (hiTail null) hiHead e; else hiTail.next e; hiTail e; } } while ((e next) ! null); // 将分组后的链表映射到桶中 if (loTail ! null) { loTail.next null; newTab[j] loHead; // 低位链表留在原下标 } if (hiTail ! null) { hiTail.next null; newTab[j oldCap] hiHead; // 高位链表迁移到 j oldCap }扩容时一次遍历仅凭一次e.hash oldCap位运算就把一个桶上的链表一分为二低位链表lo原地不动高位链表hi整体平移到j oldCap既保留了链表元素的原始顺序又避免了 O(n) 次哈希重算。若是红黑树节点则调用((TreeNodeK,V)e).split(this, newTab, j, oldCap)进行树拆分本质也是按照(e.hash oldCap) 0分成 lo/hi 两组再按需untreeify转回链表或重建树。源码印证为什么链表过长的兜底手段不是树化而是扩容在 第4篇 的treeifyBin分析中指出链表树化有两个条件链表长度大于等于 8TREEIFY_THRESHOLD且桶容量大于 64MIN_TREEIFY_CAPACITY。如果桶容量小于 64treeifyBin会先resize()扩容而不是树化——因为扩容后链表数据会被拆分到不同的桶节点上链表长度自然缩短这正好呼应了本篇扩容元素拆分的设计价值。六、总结如果坚持看完这部分内容并按照文中的例子进行相应的实验验证那么一定可以学会这五项知识点1、散列表实现、2、扰动函数、3、初始化容量、4、负载因子、5、扩容元素拆分。散列表实现核心是HashCode 计算索引 2 的幂次方数组 冲突链表存放一切后续优化都围绕减少碰撞、提升定位效率展开。扰动函数(h key.hashCode()) ^ (h 16)把高 16 位折叠到低 16 位10 万单词实验证明扰动后散列分布显著更均匀。初始化容量tableSizeFor通过 5 次右移或运算把任意容量规整到最近的 2 的幂次方为位运算索引与免重算扩容奠定基础。负载因子0.75 是时间与空间的折中同时 3/4 可用位运算table.length - (table.length 2)表达兼顾效率。扩容元素拆分利用e.hash oldCap一次位运算即可判定元素留原地还是迁移到j oldCapJDK 1.8 相比 1.7 省去了全部元素的哈希重算。对本篇提到的链表树化、红黑树以及插入、查找、删除、遍历等剩余知识点可以继续深入阅读仓库中的系列文档第4篇《HashMap数据插入、查找、删除、遍历源码分析》插入流程、扩容机制、链表树化treeifyBin、红黑树转链untreeify、查找删除遍历源码第5篇《看图说话讲解2-3平衡树「红黑树的前身」》 与 第6篇《带着面试题学习红黑树操作原理》从 2-3-4 树模型推导红黑树五条规则与染色、旋转原理红黑树 Red Black Tree 数据结构文档 与 哈希表(散列) Hash 数据结构文档提供完整的代码级数据结构实现基于Hash散列数据库路由组件设计把扰动函数、哈希寻址落地到分库分表中间件是源码学习到造火箭的完整范例。赞分享文档教程后端【免费下载链接】CodeGuide:books: 本代码库是作者小傅哥多年从事一线互联网 Java 开发的学习历程技术汇总旨在为大家提供一个清晰详细的学习教程侧重点更倾向编写Java核心内容。如果本仓库能为您提供帮助请给予支持(关注、点赞、分享)项目地址https://gitcode.com/gh_mirrors/code/CodeGuide点击查看免费下载相关推荐hello-algo 链式地址哈希表实现指南HashMapChaining、负载因子与再哈希扩容hello algo 链式地址哈希表实现指南HashMapChaining、负载因子与再哈希扩容 本文基于 hello algo 仓库中 链式地址哈希表的 P教程文档示例工程教育Java 面经手册第4篇HashMap 数据插入、查找、删除、遍历源码深度分析含链表树化与遍历顺序Java 面经手册第4篇HashMap 数据插入、查找、删除、遍历源码深度分析含链表树化与遍历顺序 本文是《Java 面经手册》系列的第 4 篇延续第文档教程后端面经手册 · 第16篇《码农会锁ReentrantLock 之公平锁讲解和实现》面经手册 · 第16篇《码农会锁ReentrantLock 之公平锁讲解和实现》 本篇技术指南聚焦于 Java 并发编程中 ReentrantLock 公平锁文档教程后端上一篇ToolJet Tags 组件完全指南用数组数据渲染标签、配置样式与动态数据下一篇Lucide 图标字体配色指南用 CSS color 属性自定义图标颜色创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考