大连企业网站哪一家好,西安建设市场诚信信息平台网站,金堂县建设局网站,传奇做网站HashMap 就像一个大仓库#xff0c;里面有很多小柜子#xff08;数组#xff09;#xff0c;每个小柜子可以挂一串链条#xff08;链表#xff09;#xff0c;链条太长的时候会变成更高级的架子#xff08;红黑树#xff09;。下面用超简单的例子解释#xff1a; 壹…HashMap 就像一个大仓库里面有很多小柜子数组每个小柜子可以挂一串链条链表链条太长的时候会变成更高级的架子红黑树。下面用超简单的例子解释 壹. 排列方式
数组一排固定的小柜子比如柜子0、柜子1、柜子2...。链表如果多个东西要放在同一个柜子里它们会串成一条链子。红黑树当某个柜子的链子太长比如超过8个链子会变成一个小架子树结构找东西更快。 贰. 存数据的过程
假设我们要存一个键值对 (name, 小明)
找柜子先算 name 的哈希值类似身份证号比如得到柜子3。放数据 如果柜子3是空的直接放进去。如果柜子3已经有东西检查链条上的每个元素 如果有相同的键比如已经有 name替换它的值。如果没有把新键值对挂到链子末尾。 链条转架子如果链子长度超过8就把链子变成红黑树架子。 叁. 取数据的过程
假设要取 name 对应的值
找柜子算 name 的哈希值确定是柜子3。找数据 如果柜子3是链子遍历链子找 name。如果柜子3是架子红黑树用树的快速查找方法。 肆. 代码简化版Java
// 小柜子数组
Node[] table new Node[16];// 链表节点如果链子太长会变成 TreeNode
class Node {String key;String value;Node next; // 下一个节点
}// 红黑树节点架子结构
class TreeNode extends Node {TreeNode parent;TreeNode left;TreeNode right;
}// 存数据示例
void put(String key, String value) {int hash key.hashCode();int index hash % table.length; // 计算柜子位置if (table[index] null) {// 柜子是空的直接放进去table[index] new Node(key, value);} else {// 柜子非空挂到链子末尾或更新值// 如果链子太长转成红黑树}
} 伍. 一句话总结
HashMap 的数组是主干链表解决哈希冲突红黑树解决链表过长时的性能问题 陆. 源码HashMap的putVal()方法
/*** Implements Map.put and related methods** param hash hash for key* param key the key* param value the value to put* param onlyIfAbsent if true, dont change existing value* param evict if false, the table is in creation mode.* return previous value, or null if none*/final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;if ((tab table) null || (n tab.length) 0)n (tab resize()).length;if ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null);else {NodeK,V e; K k;if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;else if (p instanceof TreeNode)e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount 0; ; binCount) {if ((e p.next) null) {p.next newNode(hash, key, value, null);if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}if (e ! null) { // existing mapping for keyV oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);return oldValue;}}modCount;if (size threshold)resize();afterNodeInsertion(evict);return null;} 柒、我们来拆解 “哈希冲突时链表如何挂到数组上” 的详细过程用大白话 例子解释 1. 核心原理用链表串联冲突的键值对
当两个不同的键比如 name 和 age通过哈希计算后分配到 同一个数组位置同一个柜子 时就会发生 哈希冲突。此时HashMap 会用 链表 把这些冲突的键值对串起来挂在数组的这个位置上类似挂一串钥匙。 2. 具体挂链表的步骤逐行分析
假设数组的某个位置 index 已经有数据现在要存入新的键值对 (key2, value2) 检查是否重复遍历链表对比每个节点的 key 如果发现某个节点的 key 和 key2 相同用 equals() 判断直接覆盖它的值。如果链表中没有相同的 key则把新节点 挂到链表末尾Java 8 之后是尾插法。 链表挂载示意图 // 数组的某个位置 index 已经有一个节点 Node1
table[index] Node1(key1, value1) - null;// 存入新节点 Node2冲突
Node1.next Node2(key2, value2); // 挂到链表尾部
table[index] Node1 - Node2 - null; 代码逻辑简化版 Node existingNode table[index]; // 获取数组当前位置的链表头// 遍历链表检查是否已有相同的 key
while (existingNode ! null) {if (existingNode.key.equals(newKey)) {existingNode.value newValue; // 覆盖旧值return;}existingNode existingNode.next;
}// 如果没有重复 key把新节点挂到链表末尾
Node newNode new Node(newKey, newValue);
newNode.next table[index]; // Java 8 之前是头插法新节点变成链表头
table[index] newNode; // Java 8 之后是尾插法直接挂在链表尾部 3. 关键细节头插法 vs 尾插法
Java 8 之前新节点插入链表头部头插法。 问题多线程下可能导致链表成环死循环。示例table[index] 新节点 - 旧节点 - null。 Java 8 之后新节点插入链表尾部尾插法。 改进避免多线程下的链表成环问题。示例旧节点 - 新节点 - null。 4. 链表转红黑树的条件
当链表长度 超过 8且 数组总长度 ≥ 64 时链表会转换成红黑树。如果数组长度 64即使链表长度 8HashMap 也会优先选择 扩容数组而不是转树因为扩容能直接减少哈希冲突的概率成本更低。这正说明 HashMap 的设计是 先尝试扩容解决冲突实在不行再转树。 为什么这样设计 小数组时扩容更高效 数组较小时哈希冲突可能只是因为数组容量不足直接扩容能快速缓解问题。红黑树结构复杂维护成本高小规模数据下不如扩容划算。 大数组时优化查询 数组足够大≥64后如果仍有长链表说明哈希冲突难以通过扩容解决如多个 key 哈希值相同。此时转为红黑树将查询复杂度从 O(n) 降为 O(logn)。 5. 完整流程示例
假设存入 (name, 小明) 和 (age, 18)它们的哈希值冲突都映射到数组位置 3 存入第一个节点 table[3] Node(name, 小明) - null; 存入第二个节点冲突 // 检查链表发现没有重复 key挂到链表末尾
table[3] Node(name, 小明) - Node(age, 18) - null; 查找时遍历链表逐个对比 key找到对应值。 6.总结
链表挂在数组上通过节点的 next 指针串联冲突的键值对。插入位置Java 8 之后用尾插法避免多线程问题。转红黑树链表过长时优化查找速度从 O(n) 优化到 O(log n)。 捌、再帮你用 “仓库管理员” 的比喻 总结一下确保彻底理解 终极傻瓜版总结
仓库数组管理员有一排柜子比如16个每个柜子有编号0到15。存东西键值对 管理员用 哈希函数比如 key.hashCode() % 16算出东西应该放哪个柜子。如果柜子空直接放进去。 柜子冲突哈希冲突 如果柜子已经有东西管理员会拿一根 链条链表 把新东西和旧东西绑在一起挂在柜子里。链条的挂法新东西挂在链条的尾部Java 8之后。 链条太长怎么办 如果链条长度超过8管理员会把链条换成 高级货架红黑树这样找东西更快。但如果仓库的柜子总数太少比如小于64个管理员会直接 扩建仓库扩容数组而不是换货架。 关键逻辑图示
// 数组柜子列表
Node[] table [柜子0, 柜子1, ..., 柜子15];// 柜子里的内容链表或树
柜子3 - Node1(name, 小明) - Node2(age, 18) - null // 链表形式
柜子5 - TreeNode(id, 1001) // 树形式如果链表转成了红黑树 容易混淆的点
覆盖值如果两次存同一个 key比如两次存 name会直接覆盖旧值。哈希函数hashCode() 决定柜子位置但不同对象可能算出相同的哈希值冲突。扩容当仓库的柜子被填满超过一定比例默认75%管理员会扩建仓库数组长度翻倍重新分配所有东西的位置。 玖、结合 面试被问 Java中hashmap数据结构 URL 地基Java中hashmap数据结构面试被问-CSDN博客 兄弟们理解好了。rt.jar包里的hashmap源码的putval方法的方式有厉害的同学可以学以致用哈向大家致敬
望各位潘安、各位子健/各位彦祖、于晏不吝赐教多多指正 -----分界线----------------------------------------------------------------------------------------------------
兄弟们上面的足以应付面试了如何还想更深入可以看下面的。 拾. 为什么数组长度 ≥64 时不扩容而是转树
1 扩容的局限性**
扩容的本质通过扩大数组长度将节点分散到新数组中减少哈希冲突。局限性如果多个键的哈希值本身就冲突例如哈希算法导致碰撞即使扩容也无法分散它们。 // 例如键A和键B的哈希值不同但取模后仍落在同一个桶
hash(A) % 64 5;
hash(B) % 64 5; // 即使数组扩容到128依然可能 hash(A) % 128 5hash(B) % 128 5
2) 转树的优势**
解决哈希碰撞当哈希冲突无法通过扩容避免时如多个键哈希值相同红黑树将查询复杂度从链表O(n)降到O(logn)。成本权衡 扩容成本高需新建数组、重新哈希所有节点时间复杂度O(n)。转树成本低只处理单个冲突严重的桶其他桶不受影响。
3) 阈值为什么是64**
经验值基于测试和性能权衡 数组长度较小时64哈希冲突可能因数组容量不足优先扩容更高效。数组长度≥64时认为哈希冲突更可能是哈希算法导致而非数组容量问题转树更合理。 4. 源码逻辑验证
HashMap的treeifyBin()方法中会先检查数组长度是否≥64再决定转树或扩容
// HashMap 源码片段
final void treeifyBin(NodeK,V[] tab, int hash) {int n, index; NodeK,V e;if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY) { // MIN_TREEIFY_CAPACITY64resize(); // 数组长度64时选择扩容} else {// 数组长度≥64时将链表转为红黑树TreeNodeK,V hd null, tl null;// ...具体转树逻辑}
} 5. 举例说明
场景1数组长度16链表长度9
数组长度16 64 → 触发扩容数组扩大到32而不是转树。
场景2数组长度64链表长度9
数组长度≥64 → 链表转为红黑树不再扩容。 6、总结
转树的条件链表长度8 且 数组长度≥64。转树的目的针对哈希算法导致的不可分散冲突用空间换时间红黑树优化查询。扩容的优先级数组较小时扩容是更经济的解决方案。 拾壹、数组扩容是否重新计算哈希值
在 HashMap 中当数组长度小于 64 时触发扩容哈希值本身不会重新计算但元素在数组中的位置索引会根据新的数组长度重新确定。以下是具体机制 1. 哈希值如何生成 哈希值来源 HashMap 中每个键Key的哈希值由以下两步生成 调用键对象的 hashCode() 方法得到原始哈希值。通过 扰动函数位运算对原始哈希值进行二次处理增加随机性减少哈希冲突。 // HashMap 的扰动函数实现
static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
} 哈希值的存储 这个最终哈希值会在键值对被插入 HashMap 时计算一次并存储在 Node 或 TreeNode 对象中后续不再重新计算。 2. 扩容时如何确定新位置
当数组长度从 oldCap例如 16扩容到 newCap例如 32时元素的索引位置会按以下规则重新分配 索引计算公式 新索引 hash (newCap - 1) newCap - 1 是新的掩码例如 32 → 0b11111。 优化计算技巧 由于扩容是翻倍newCap oldCap 1新掩码比旧掩码多出一个高位 1例如 16 → 0b111132 → 0b11111。 因此新索引只需判断哈希值中新增的高位是 0 还是 1 如果高位是 0新索引 原位置。如果高位是 1新索引 原位置 oldCap。 源码逻辑 // 遍历旧数组中的每个桶
for (int j 0; j oldCap; j) {NodeK,V e;if ((e oldTab[j]) ! null) {// 检查哈希值高位是 0 还是 1if ((e.hash oldCap) 0) {// 高位为 0 → 留在原位置j} else {// 高位为 1 → 移动到新位置j oldCap}}
} 3. 示例说明
假设原数组长度 oldCap 16二进制 0b10000扩容后 newCap 32二进制 0b100000。
键的哈希值假设为 0b10101。旧索引计算 hash (oldCap - 1) 0b10101 0b1111 0b00101 → 索引 5。新索引计算 hash (newCap - 1) 0b10101 0b11111 0b10101 → 索引 21。 或者直接通过高位判断 hash oldCap 0b10101 0b10000 0b10000 ≠ 0 → 高位为 1新索引 5 16 21。 4. 为什么哈希值不重新计算
性能优化哈希值的计算涉及 hashCode() 方法和扰动函数重新计算会带来额外开销。一致性保障哈希值在键的生命周期内应保持不变除非键对象被修改但这违反 HashMap 的设计前提。 5、总结
哈希值固定在键插入时计算一次后续不再变更。索引重新分配扩容时利用原哈希值的高位判断新位置无需重新计算哈希值。设计目标以最小成本重新分布元素同时减少哈希冲突。 兄弟辛苦♂️。 点烟
望各位潘安、各位子健/各位彦祖、于晏不吝赐教多多指正
