当前位置：首页 > news >正文

浅显易懂HashMap的数据结构

news 2025/2/27 10:12:09

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, don't 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) {Node<K,V>[] tab; Node<K,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 {Node<K,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 = ((TreeNode<K,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，HashMap 会选择 扩容数组（而不是转树），减少哈希冲突。

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)  // 树形式（如果链表转成了红黑树）