图解算法通识讲义线性结构
哈希表与散列冲突图解
核心心智模型：建立「数值」到「下标」的常数映射引擎，用内存空间换取查找时间的降维打击。
核心交互式算法图解演练沙盒
哈希映射模型
两数之和哈希映射与常数探测演练
步骤 1 / 4
原始输入数组 nums:Target = 9
2nums[0]
7nums[1]
11nums[2]
15nums[3]
当前步算式探测
当前扫描数值:nums[0] = 2
所需互补数值:9 - 2 = 7
哈希表中尚无 Key=7，写入当前项并继续
模拟哈希表 Map<Key, Index>Size: 0
<哈希表初始为空 >
步骤 1：遍历 nums[0] = 2。计算目标互补数值：complement = target - num = 9 - 2 = 7。
关键操作与时空复杂度速查对照表
| 操作 / 算法阶段 | 平均时间 | 最坏时间 | 空间复杂度 | 核心底层机制 |
|---|---|---|---|---|
| 按键查找 (Get / Contains) | O(1) | O(n) | O(1) | 平均常数时间定位桶位；极端哈希全冲突时退化为链表遍历。 |
| 键值插入 (Put / Insert) | O(1) | O(n) | O(1) | 计算哈希放入对应桶位；若触及负载因子触发 Resize 扩容。 |
| 键值移除 (Remove / Erase) | O(1) | O(n) | O(1) | 定位桶位后在单链表或红黑树中解挂节点。 |
template.java
Map<Integer, Integer> map = new HashMap<>();
map.put(key, value);
if (map.containsKey(targetKey)) {
int val = map.get(targetKey);
}
map.put(num, map.getOrDefault(num, 0) + 1);解题核心心法提炼
- 核心哲学是「空间换时间」：牺牲稀疏存储与指针开销，规避嵌套循环。
- 两数之和核心破局点：遍历元素时哈希记录余数与其下标，单次线性遍历收工。
- 负载因子（Load Factor = 0.75）平衡了冲突几率与空间浪费。
常见踩坑警示与避坑指南
- 在遍历集合时直接调用 map.remove() 会导致 ConcurrentModificationException，应使用迭代器显式操作。
- 自定义类作为 Key 时，必须同时重写 equals() 与 hashCode()，否则同值异址对象无法寻找到对应 Value。
- 无节制使用大对象作为 Key 会导致散列计算过载与内存泄漏。
对应 Hot 100 实战题目突围
原理已掌握！立即进入沉浸式工作台开始实战演练，强化代码肌肉记忆