02.2.2.1 哈希表设计与冲突处理
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.2 数组、字符串与哈希 / 02.2.2 字符串与哈希表
02.2.2.1-001 哈希表为什么能平均 O(1) 查找?
一句话结论
哈希函数把键直接映射到桶下标,理想情况下每个键落在独立桶,存取只定位一次;平均 O(1),冲突时需在桶内进一步查找。
概念解释
- 键:用来定位的值。
- 桶:存储位置。
- 映射:
hash(key) mod 桶数。
原理流程
- 对键计算哈希值。
- 取模定位桶。
- 桶内命中即返回,未命中按冲突方案处理。
代码 / 图示
key → hash(key) → mod m → 桶下标
理想:桶内 0~1 个元素 → O(1)
常见误区
- 误区:哈希表无条件 O(1);正解:平均 O(1),最坏冲突退化 O(n)。
- 误区:哈希函数不影响性能;正解:分布不均会加剧冲突。
追问
- Q:哈希表平均复杂度前提? A:哈希均匀、负载因子合理。
- Q:最坏情况是什么? A:所有键映射到同一桶。
02.2.2.1-002 好的哈希函数有哪些要求?
一句话结论
均匀分布(相近键落到不同桶)、计算快速、确定性(同键同值)、充分混合位模式;常用除留余数、乘法哈希与扰动混合。
概念解释
- 均匀:减少冲突堆积。
- 快速:哈希本身不能成为瓶颈。
- 确定:相同输入必须得到相同哈希。
原理流程
- 提取键的位表示。
- 混合高位低位。
- 取模落到桶范围。
代码 / 示例
除留余数:h(k) = k mod m
扰动:高位移位后与低位异或,混合分布
常见误区
- 误区:哈希函数越复杂越好;正解:均匀与速度要平衡。
- 误区:相近键落相邻桶无所谓;正解:聚集会放大冲突。
追问
- Q:字符串哈希怎么算? A:滚动多项式哈希,逐字符加权累加。
- Q:自定义对象怎么做哈希? A:合并各字段哈希值,同时重写相等判断。
02.2.2.1-003 哈希冲突是怎么产生的?
一句话结论
桶数有限而键无限,不同键经哈希取模后落到同一桶即冲突;冲突不可避免,只能通过均匀哈希与冲突处理降低影响。
概念解释
- 鸽笼原理:键多于桶必然冲突。
- 冲突类型:相同桶不同键。
- 处理目标:冲突后仍可正确存取。
原理流程
- 桶数固定。
- 多键映射同一下标。
- 冲突方案在桶内组织元素。
代码 / 图示
m 个桶,n 个键
n > m 时必有冲突
常见误区
- 误区:设计好哈希函数就能消除冲突;正解:只能降低概率,不能消除。
- 误区:冲突意味着哈希表错误;正解:冲突是常态,结构负责正确处理。
追问
- Q:负载因子与冲突关系? A:因子越高桶越挤,冲突概率越大。
- Q:开放寻址冲突表现? A:探测序列变长,查找变慢。
02.2.2.1-004 链地址法怎么处理冲突?
一句话结论
每个桶挂一条链表(或树),冲突元素追加到桶内;查找/插入先定位桶,再遍历桶内链;实现简单,负载高时链变长。
概念解释
- 桶:数组槽位。
- 链:同桶元素串接。
- 扩容:桶数增加后重新分布。
原理流程
- 哈希定位桶。
- 桶内按相等判断查找。
- 未命中追加新节点。
代码 / 示例
桶 0: → k1 → k4
桶 1: → k2
桶 2: → k3 → k6 → k8
常见误区
- 误区:链地址法不会退化;正解:全冲突时链表 O(n)。
- 误区:桶内顺序无所谓;正解:热点键放链头可缩短平均查找。
追问
- Q:链地址法删除怎么做? A:桶内链表摘除节点,注意头节点。
- Q:Java HashMap 用哪种? A:链地址法,桶内链表过长转红黑树。
02.2.2.1-005 开放寻址法怎么处理冲突?
一句话结论
所有元素存在桶数组内,冲突时按探测序列找下一个空槽;常见线性探测、二次探测、双重哈希;删除需打墓碑标记。
概念解释
- 线性探测:步长 1,易聚集。
- 二次探测:步长平方,缓解聚集。
- 双重哈希:第二个哈希定步长。
原理流程
- 定位起始桶。
- 占用则沿探测序列找空槽。
- 查找沿同序列比对;删除留墓碑。
代码 / 图示
插入:h(k), h(k)+1, h(k)+2, …
线性探测相邻槽连成片(聚集)
常见误区
- 误区:开放寻址删除直接置空;正解:会打断后续探测链,需墓碑标记。
- 误区:负载高时探测仍快;正解:高负载下探测序列显著变长。
追问
- Q:线性探测缺点? A:一次冲突引发相邻聚集,性能连锁下降。
- Q:哪些结构用开放寻址? A:如 ThreadLocalMap、Python dict(具体实现以版本为准)。
02.2.2.1-006 Java HashMap 的内部结构是什么?
一句话结论
数组为桶表,桶内冲突用链表;链表长度达到阈值且桶数足够时转红黑树;查找平均 O(1),树化后桶内 O(log n)。
概念解释
- 桶数组:
Node[] table。 - 链表:冲突节点串接。
- 红黑树:退化保护。
原理流程
- 键哈希定位桶。
- 桶内链表遍历比较。
- 满足阈值树化。
代码 / 图示
table: [桶0] [桶1] [桶2] …
桶内:链表 → 长度达标 → 红黑树
常见误区
- 误区:HashMap 每个桶都是红黑树;正解:默认链表,达到条件才树化。
- 误区:树化后一定更快;正解:短链表遍历常数更小,树化是防退化保护。
追问
- Q:树化阈值是多少? A:链表长度 ≥ 8 且桶数 ≥ 64 才树化;桶数不足时先扩容(具体以 JDK 版本为准)。
- Q:什么时候去树化? A:树节点减少到阈值以下时退化回链表。
02.2.2.1-007 链表为什么转红黑树?
一句话结论
冲突严重时链表查找 O(n);红黑树桶内查找 O(log n),把最坏退化限制在对数级;代价是节点结构更复杂、常数更大。
概念解释
- 链表:顺序遍历。
- 红黑树:平衡二叉查找树。
- 权衡:防退化 vs 常数开销。
原理流程
- 链表长度超阈值。
- 桶数达标后转树。
- 桶内按键比较查找。
代码 / 图示
链表长度 k:查找 O(k)
红黑树高度 log k:查找 O(log k)
常见误区
- 误区:转树是为了提高平均性能;正解:主要防止极端冲突下的最坏退化。
- 误区:任意长度链表都该用树;正解:短链遍历常数更低。
追问
- Q:为什么不用 AVL 树? A:红黑树旋转更少,插入删除维护成本更低,权衡后更适合哈希桶。
- Q:树化需要哪些条件? A:链表长度阈值与桶容量阈值同时满足,具体数值以版本为准。
02.2.2.1-008 负载因子是什么?为什么默认 0.75?
一句话结论
负载因子 = 元素数 / 桶数,衡量拥挤程度;0.75 是空间利用率与冲突概率的折中:过高冲突增多,过低空间浪费。
概念解释
- 阈值:因子超过默认值触发扩容。
- 折中:时间与空间平衡。
- 经验值:泊松分布下 0.75 桶内节点数分布稳定。
原理流程
- 统计元素数与桶数。
- 因子超阈值扩容。
- 重哈希降低拥挤。
代码 / 图示
负载因子 = size / capacity
0.75:容量 16 时,12 个元素触发扩容
常见误区
- 误区:负载因子越低越好;正解:低因子浪费空间,桶数膨胀。
- 误区:0.75 是硬性数学最优;正解:是工程折中经验值。
追问
- Q:已知元素数怎么初始化? A:
new HashMap<>(预估容量),避免多次扩容。 - Q:负载因子可调吗? A:构造器可传,调小换速度、调大换空间。
02.2.2.1-009 扩容与 rehash 做了什么?
一句话结论
容量翻倍后把旧桶元素重新计算下标分布到新桶;扩容是 O(n) 单次操作,均摊到每次插入 O(1);扩容期间查询仍可用旧表(具体实现细节以版本为准)。
概念解释
- 翻倍:桶数 ×2。
- 重哈希:元素重新落桶。
- 均摊:昂贵扩容被前期插入平摊。
原理流程
- 因子超阈值。
- 新建两倍桶表。
- 旧元素迁移重定位。
代码 / 图示
旧容量 16 → 新容量 32
元素按新容量重新散列
常见误区
- 误区:扩容只扩桶不搬元素;正解:必须 rehash 迁移。
- 误区:扩容每次插入都发生;正解:触达阈值才扩容。
追问
- Q:为什么容量翻倍? A:几何增长保证均摊线性,且位运算取模高效。
- Q:预估容量为什么能提速? A:避免运行期多次 rehash 拷贝。
02.2.2.1-010 容量为什么取 2 的幂?
一句话结论
2 的幂时取模可由位与 hash & (n-1) 完成,比取模运算快;同时重哈希时元素位置规律可预测,便于拆分迁移。
概念解释
- 位与替代取模。
- 幂次容量分布均匀。
- 扩容迁移可按高位拆分。
原理流程
- 桶数 n = 2^k。
- 下标 =
hash & (n-1)。 - 扩容后按新增位决定位置。
代码 / 示例
n = 16 (10000),n-1 = 15 (01111)
下标 = hash & 15
常见误区
- 误区:任意容量都能位与取模;正解:只有 2 的幂成立。
- 误区:用户传入容量直接使用;正解:实现会把容量调整为最近的 2 的幂。
追问
- Q:非 2 的幂哈希表怎么取模? A:用
%运算,分布与性能另评估。 - Q:位与取模为什么依赖哈希低位均匀? A:扰动函数混合高低位,降低低位聚集冲突。
02.2.2.1-011 扰动函数(hash())起什么作用?
一句话结论
把键的哈希值高位移位后与低位混合,避免低位规律相近的键聚集到相邻桶;让位与取模后的分布更均匀。
概念解释
- 缺陷:低位可能规律性重复。
- 混合:高低位异或。
- 目标:桶分布均匀。
原理流程
- 取原始哈希码。
- 高 16 位与低 16 位异或。
- 再做位与定位。
代码 / 示例
static int hash(Object key) {
int h = key.hashCode();
return h ^ (h >>> 16);
}
常见误区
- 误区:直接用 hashCode 低位取模即可;正解:低位规律会造成聚集。
- 误区:扰动改变键的相等性;正解:扰动只影响分布,相等判断仍按 equals。
追问
- Q:自定义类要注意什么? A:equals 相等的对象 hashCode 必须相等。
- Q:哈希码冲突怎么办? A:桶内再按 equals 比较。
02.2.2.1-012 哈希表的插入、查找、删除流程是什么?
一句话结论
三者都先哈希定位桶,再在桶内按相等判断查找;插入未命中则新增,删除摘除节点;平均 O(1),桶内结构决定最坏代价。
概念解释
- 定位:哈希 + 取模。
- 桶内:链表遍历或树查找。
- 修改:命中更新值。
原理流程
- 计算桶下标。
- 桶内查找匹配键。
- 按操作命中或新增/删除。
代码 / 图示
put: 定位 → 桶内查 → 命中更新 / 未命中追加
get: 定位 → 桶内查 → 返回值
remove: 定位 → 桶内摘除
常见误区
- 误区:插入不查重复直接追加;正解:相同键应更新值而非重复存放。
- 误区:删除链表头节点与中间节点写法相同;正解:需前驱指针处理。
追问
- Q:哈希表允许 null 键吗? A:按实现而定,部分实现允许单个 null 键。
- Q:并发插入要注意什么? A:需加锁或用并发结构,避免桶链损坏。
02.2.2.1-013 设计哈希集合(LC 705)怎么做?
一句话结论
数组桶 + 链地址法:桶内用链表或动态数组存键;add/remove/contains 先定位桶再桶内查找;选质数桶数降低冲突。
概念解释
- 只存键不存值。
- 桶内去重。
- 基础版可用链表实现。
原理流程
- 定桶数与哈希函数。
- add:桶内无则加入。
- remove:桶内找到删除。
- contains:桶内查找。
代码 / 示例
class MyHashSet {
private final int BASE = 769;
private final List<Integer>[] buckets = new List[BASE];
public MyHashSet() {
for (int i = 0; i < BASE; i++) buckets[i] = new ArrayList<>();
}
private int hash(int key) { return key % BASE; }
public void add(int key) {
int h = hash(key);
if (!buckets[h].contains(key)) buckets[h].add(key);
}
public void remove(int key) {
buckets[hash(key)].remove(Integer.valueOf(key));
}
public boolean contains(int key) {
return buckets[hash(key)].contains(key);
}
}
常见误区
- 误区:
remove(int)按索引删;正解:集合存 Integer,需按对象删除。 - 误区:桶数取小质数;正解:质数减少取模后的规律聚集。
追问
- Q:桶内用链表还是数组? A:数组 contains O(k),链表需遍历;本题规模小均可。
- Q:如何扩容? A:元素增多后倍增桶数并 rehash,工程实现再加。
02.2.2.1-014 设计哈希映射(LC 706)怎么做?
一句话结论
桶内存键值对节点;查找按键定位节点并取值;更新命中节点的值,未命中新增;结构与哈希集合同构。
概念解释
- 节点:key + value。
- 命中:更新 value。
- 未命中:新增节点。
原理流程
- 哈希定位桶。
- 桶内按键查找节点。
- put 更新或新增,get 返回值,remove 摘除。
代码 / 示例
class MyHashMap {
private static class Node {
int key, value;
Node next;
Node(int k, int v) { key = k; value = v; }
}
private final int BASE = 769;
private final Node[] buckets = new Node[BASE];
private int hash(int key) { return key % BASE; }
public void put(int key, int value) {
int h = hash(key);
for (Node p = buckets[h]; p != null; p = p.next)
if (p.key == key) { p.value = value; return; }
Node n = new Node(key, value);
n.next = buckets[h]; buckets[h] = n;
}
public int get(int key) {
for (Node p = buckets[hash(key)]; p != null; p = p.next)
if (p.key == key) return p.value;
return -1;
}
public void remove(int key) {
int h = hash(key);
Node head = buckets[h], prev = null;
for (Node p = head; p != null; prev = p, p = p.next) {
if (p.key == key) {
if (prev == null) buckets[h] = p.next;
else prev.next = p.next;
return;
}
}
}
}
常见误区
- 误区:删除头节点未单独处理;正解:前驱为空时改桶头。
- 误区:put 重复键追加新节点;正解:先查命中再更新。
追问
- Q:get 未命中返回什么? A:按题目约定常见为 -1。
- Q:键可为对象? A:需自定义哈希与相等比较。
02.2.2.1-015 哈希表最坏复杂度是什么?为什么?
一句话结论
最坏 O(n):哈希函数失效使全部键落入同一桶,桶内链表退化为线性遍历;均匀分布假设被破坏时平均 O(1) 不成立。
概念解释
- 退化场景:恶意构造或哈希分布差。
- 链内遍历:O(n)。
- 树化可把最坏压到 O(log n)。
原理流程
- 所有键同桶。
- 桶内顺序查找。
- 时间与元素数同阶。
代码 / 图示
全部冲突:桶 0 → n 个节点链
get 最坏遍历整链 O(n)
常见误区
- 误区:面试报复杂度只说 O(1);正解:应说明平均 O(1)、最坏 O(n)。
- 误区:树化后最坏仍是 O(n);正解:树化桶内 O(log n)。
追问
- Q:如何降低最坏概率? A:均匀哈希、合理负载因子、冲突结构树化。
- Q:哈希表能保证最坏 O(1) 吗? A:不能,开放寻址/链地址都有退化可能。
02.2.2.1-016 哈希表、数组、链表怎么选型?
一句话结论
按键快速查找/去重选哈希;按下标连续访问、遍历选数组;频繁中间增删选链表;按操作类型与是否有序综合判断。
概念解释
- 哈希:键值映射,无序。
- 数组:随机访问,连续存储。
- 链表:插入删除灵活,随机访问慢。
原理流程
- 列出主要操作:查、插、删、遍历。
- 评估各结构代价。
- 按约束选主结构。
代码 / 图示
按键存在性 → 哈希
按下标访问 → 数组
中间增删 → 链表
有序遍历 → 平衡树/排序后数组
常见误区
- 误区:哈希表万能;正解:需要有序遍历、范围查询时哈希不适合。
- 误区:链表比数组省空间所以更快;正解:链表指针开销与缓存表现通常更差。
追问
- Q:需要有序键集合用什么? A:TreeMap/TreeSet 类平衡结构,O(log n)。
- Q:计数场景数组 vs 哈希? A:值域小用数组,范围散用哈希。
02.2.2.1-017 哈希表空间占用由什么决定?
一句话结论
空间 = 桶数组 + 桶内节点;负载因子越低桶越空,节点存键值与指针;实际占用通常大于元素数,预估容量时留余量。
概念解释
- 桶数组:固定槽位。
- 节点:键、值、链指针/树指针。
- 负载因子决定空闲比例。
原理流程
- 统计桶数与节点数。
- 计入每节点指针开销。
- 按负载因子估算总空间。
代码 / 图示
n 元素,因子 0.75 → 桶数 ≈ n/0.75
节点含 key/value/next 指针
常见误区
- 误区:哈希表空间等于元素数;正解:桶空位与节点结构额外占空间。
- 误区:桶数越多越省空间;正解:低因子放大桶数组占用。
追问
- Q:如何控制哈希表内存? A:调大负载因子、预估容量避免冗余扩容。
- Q:基本类型键值怎么省空间? A:专用基本类型集合减少装箱。
02.2.2.1-018 哈希分布不均与碰撞攻击是什么?
一句话结论
哈希函数若可预测,攻击者可构造大量同哈希键使桶退化,形成碰撞攻击;工程上用扰动、随机化种子缓解,敏感场景评估哈希随机性。
概念解释
- 可预测哈希:输入决定输出。
- 碰撞聚集:同桶元素激增。
- 缓解:混合位、随机种子。
原理流程
- 评估哈希是否对外可预测。
- 引入扰动或随机化。
- 监控桶长度分布。
代码 / 图示
攻击:构造 hash 相同的一批键
表现:单桶链过长,查询退化
常见误区
- 误区:哈希冲突只会偶然发生;正解:可被主动构造。
- 误区:树化能完全免疫攻击;正解:把 O(n) 降为 O(log n),仍有代价。
追问
- Q:字符串哈希被攻击怎么办? A:加盐随机化或换强哈希。
- Q:HashMap 遍历顺序可控吗? A:不保证,依赖结构与版本。
02.2.2.1-019 线程安全的哈希结构有哪些思路?
一句话结论
并发场景不能直接用普通 HashMap;可用加锁包装、分段/桶级锁、并发哈希结构;读多写少考虑不可变结构。
概念解释
- 竞态:并发 put 损坏桶链。
- 锁粒度:整表锁或桶级锁。
- 并发实现:专门的线程安全 Map。
原理流程
- 识别并发访问。
- 选同步包装或并发结构。
- 评估锁粒度与吞吐。
代码 / 图示
同步包装:整表锁
并发 Map:桶级/分段锁
不可变:发布后只读
常见误区
- 误区:普通 HashMap 多线程下只是慢;正解:可能出现链表成环、数据丢失等损坏。
- 误区:加方法级锁就够;正解:复合操作(先查后插)仍需整体原子性。
追问
- Q:迭代时结构被修改怎么办? A:快速失败或使用并发安全迭代器。
- Q:计数并发更新用什么? A:原子计数或并发 Map 的 merge 方法。
02.2.2.1-020 哈希表题有哪些常见误区?
一句话结论
常见误区:无条件宣称 O(1)、先放后查导致自匹配、计数忘记累加、键可变后哈希漂移、未判空桶;编码前先明确键口径与更新时机。
概念解释
- 时机:先查后放防自配。
- 计数:重复键累加次数。
- 可变键:改字段后哈希不一致。
原理流程
- 明确键与值语义。
- 确认先查还是先登记。
- 计数/存在性分支写清。
代码 / 图示
两数之和:先查 need,再放当前
计数:merge(key, 1, sum)
可变对象作键:修改后从哈希表移除/重放
常见误区
- 误区:哈希表可以存可变对象作键且随意修改;正解:字段变化会导致定位不到。
- 误区:contains 后 get 两次查找;正解:一次定位节点复用结果。
追问
- Q:键为数组怎么哈希? A:数组不能直接作键,转字符串或列表等可哈希表示。
- Q:哈希表遍历顺序有保证吗? A:普通哈希表不保证顺序,需要顺序用排序结构。