八、哈希表（第 95-100 题）

95. 哈希表（散列表）的查找效率取决于( )

标签：【互联网/国企笔试超高频】

A. 哈希函数和装填因子 B. 数据量大小 C. 数据是否有序 D. 存储结构

答案：A

【结论】 查找效率取决于哈希函数和装填因子，选 A。

【逐项辨析】

• A 哈希函数和装填因子：正确。 两者共同决定冲突概率。
• B 数据量大小：影响的是绝对耗时，不是查找效率的本质因素。
• C 数据是否有序：哈希表不依赖有序性，与查找效率无关。
• D 存储结构：存储结构是哈希表的实现方式，不是影响效率的独立因素。

【知识点】 哈希表查找效率的影响因素（必背）：

因素	作用	说明
哈希函数	决定键值到地址的映射	好的哈希函数应均匀分布，减少聚集
装填因子 α	α = n / m（记录数 / 表长）	α 越大，冲突概率越高，查找效率越低
冲突处理方法	线性探测、二次探测、链地址法等	不同方法 ASL 不同

装填因子 α 与查找效率的关系:
  α 接近 0 → 表很空 → 冲突少 → ASL ≈ 1
  α 接近 1 → 表很满 → 冲突多 → ASL 急剧上升

通常阈值:α > 0.75 时触发扩容(Java HashMap 默认值)

【记忆锚点】 “哈希函数定分布，装填因子定冲突”——两者共同决定查找效率。

【易混对比】 注意“装填因子 α = 记录数 / 表长”，不是“表长 / 记录数”（见第 96 题）。α 越大表越满、冲突越多。与第 99 题连考：哈希表 ASL 与“数据的排序方式”无关。

【自测】 装填因子 α 越大，哈希表的查找效率越高还是越低？

答：越低。α 越大，表越满，冲突概率越高，平均查找长度 ASL 越大。与第 96 题连考。

【知识关联】

• 同库连考：与第 71 题（线性探测 ASL 计算）、第 96 题（装填因子定义）、第 97 题（冲突处理方法）、第 99 题（与数据是否有序无关）、第 105 题（查找失败 ASL 分母=表长）构成「哈希查找」完整网；与第 68 题（顺序查找 ASL）、第 67 题（二分次数）对比不同查找结构的代价来源。
• 工程实现：Java HashMap 平均 O(1) 的前提就是：①hash 扰动均匀；②负载因子默认 0.75，超过则扩容 rehash；③冲突用链表+红黑树。面试说「哈希查找 O(1)」必须补一句「平均，且与装填因子、哈希函数质量有关」，否则会被追问打穿。Redis dict、Go map 同理（增量 rehash 等工程细节不同）。
• 408 / 国企真题：408 与国网「哈希表查找效率取决于」标准答案「哈希函数、装填因子（及冲突处理方法）」；干扰项「数据量大小」「是否有序」——数据量大只影响绝对时间，有序与哈希无关。银行科技岗还常把该点与「二分取决于有序」对照出题。
• 面试追问:①「ASL 与哪些因素有关？」（哈希函数均匀性、α=n/m、冲突处理方法）；②「和关键字大小/是否有序有关吗？」（无直接关系）；③「α 从 0.5 到 0.9 会怎样？」（冲突与探测次数急剧上升，开放定址尤其敏感）。

【拓展延伸】

变式问法:①「查找效率取决于？」（哈希函数和装填因子，本题）；②「下列与哈希查找效率无关的是？」（数据是否有序）；③「完美哈希的条件？」（无冲突构造，ASL=1，但需静态关键字集）。

工程映射：缓存容量与命中率评估要盯装载率；布隆过滤器用空间换「可能误报」；分布式一致性哈希减少扩容时的 rehash 范围，都是「哈希函数 + 填充程度」决定效率的工业变体。

易错提醒：选 A 时注意多数标准答案还隐含冲突处理方法这一因素；若选项只给「哈希函数和装填因子」就选它。不要选「数据量大小」——那是结果层面的耗时，不是查找效率的结构因素。

---

96. 哈希表中，装填因子α的定义是( )

标签：【互联网/国企笔试超高频】

A. 记录数/表长 B. 表长/记录数 C. 冲突数/表长 D. 记录数/冲突数

答案：A

【结论】 装填因子 α = 记录数 / 表长，选 A。

【逐项辨析】

• B 表长 / 记录数：分子分母颠倒了。
• A 记录数 / 表长：正确。 α = n / m。
• C 冲突数 / 表长：冲突数不是装填因子的定义。
• D 记录数 / 冲突数：无依据。

【知识点】 装填因子的定义与意义

装填因子 α = 已存入的记录数 n / 哈希表长度 m

α 的取值范围:0 ≤ α ≤ 1(开放定址法)
            α 可 > 1(链地址法,因为链表可无限延长)

α 范围	表的状态	查找效率	处理建议
α < 0.5	较空	高(ASL ≈ 1~2)	正常
0.5 ≤ α ≤ 0.75	适中	中等	正常
α > 0.75	较满	低（ASL 明显上升）	扩容

扩容触发： 当 α 超过阈值（如 0.75）时，通常需要：1. 申请一个更大的哈希表（通常翻倍）； 2. 把所有已有元素重新哈希(rehash)到新表中。

【记忆锚点】 “α = 元素数 / 表长，越大越满越慢”——记住分子是“已存了多少”，分母是“总共多大”。

【易混对比】 装填因子与 Java HashMap 的“负载因子 0.75”是同一个概念（见第 73 题）。但注意：Java HashMap 的扩容阈值 = 容量 × 负载因子，而装填因子 α = 实际元素数 / 容量，两者在概念上完全一致。

【自测】 一个哈希表长度为 20，已存入 15 个元素，装填因子是多少？是否需要扩容？

答：α = 15/20 = 0.75。阈值 = 容量 × 负载因子 = 20 × 0.75 = 15，此时 size=15 尚未超过阈值，还不扩容——JDK 要到 size > threshold 才 resize（实测默认容量 16、threshold=12 时，放满 12 个 table.length 仍是 16，插入第 13 个才扩到 32）。再放第 16 个才会触发扩容。与第 73 题连考。

【知识关联】

• 同库连考：与第 73 题（Java HashMap 负载因子 0.75）是同一概念的「教材名 vs JDK 名」；与第 95 题（查找效率取决于哈希函数与 α）、第 71/105 题（ASL 计算，α 影响探测长度）串联；与第 97/99 题（冲突方法、与有序无关）同属哈希章。
• 工程实现：JDK8 HashMap：threshold = capacity * loadFactor，默认 loadFactor=0.75；当 size > threshold 时扩容为原容量 2 倍并 rehash。注意 α=装填因子=n/m，扩容阈值是「容量×负载因子」这个乘积，概念与本题一致。ConcurrentHashMap、Guava Cache 也有各自阈值策略。
• 408 / 国企真题：408 与国网「装填因子定义」必考，标准答案 α=记录数/表长=n/m；典型错选是分子分母颠倒。真题计算：「表长 20，已存 15，α？」→ 0.75，是否扩容看阈值。
• 面试追问:①「α=1.2 在开放定址可能吗？」（一般不能，表满无法再插；链地址可以，链变长）；②「为什么默认 0.75？」（冲突与空间的经验折中，再高探测代价陡增）；③「扩容为什么要 rehash？」（新表长度变了，H(key)=key mod m 的 m 变化，位置必须重算）。

【拓展延伸】

变式问法:①「装填因子定义？」（记录数/表长，本题）；②「表长 100、元素 60，α？」（0.6）；③「链地址法 α 可以大于 1 吗？」（可以）。

工程映射：内存哈希索引、Redis dict 的负载、布隆过滤器的误报率与填充位数、一致性哈希环上的节点负载，都是「已用量/总容量」这一 α 思想的推广。

易错提醒：①分子是 n（已存记录），分母是 m（表长），别颠倒；②α 不是「冲突数/表长」；③开放定址关心 α<1，链地址更关心平均链长。计算题先化简分数再对照选项。

---

97. 以下哪种不是哈希表的冲突解决方法？

标签：【互联网/国企笔试高频】

A. 开放定址法（线性探测、二次探测） B. 链地址法（拉链法） C. 二分查找法 D. 再哈希法

答案：C

【结论】 二分查找法不是冲突解决方法，选 C。

【逐项辨析】

• A 开放定址法：是冲突解决方法（线性探测、二次探测、双重哈希）。
• B 链地址法（拉链法）：是冲突解决方法（每个槽位挂一个链表）。
• C 二分查找法：不是冲突解决方法。 二分查找是查找算法，与冲突处理无关。
• D 再哈希法：是冲突解决方法（使用另一个哈希函数）。

【知识点】 哈希表三大冲突解决方法

方法	原理	特点
开放定址法	冲突时按某种探测序列找下一个空位	线性探测（易聚集）、二次探测（不易聚集）、双重哈希（探测步长由第二个哈希函数决定）
链地址法	每个槽位挂一个链表，冲突元素链在一起	简单高效，α 可 > 1,Java HashMap 采用此方法
再哈希法	冲突时用另一个哈希函数重新计算地址	减少聚集，但计算代价高

开放定址法 vs 链地址法:

开放定址法(线性探测):
  冲突 → 顺序找下一个空位
  优点:无指针开销
  缺点:易产生聚集(连续占用),删除需标记

链地址法:
  冲突 → 挂到该槽位的链表尾部
  优点:无聚集问题,删除简单
  缺点:需要额外指针空间

【记忆锚点】 “开放定址找空位，链地址挂链表，再哈希换函数”——三种方法一次记全。

【易混对比】 注意“二分查找法”是有序数组的查找算法，与哈希表冲突处理完全无关。容易混淆的是“再哈希法”——再哈希法是冲突解决方法（换一个哈希函数重新计算），而二分查找法是利用有序性进行折半搜索。两者名称中都有“查找/哈希”字样，但属于完全不同的技术领域。

【自测】 线性探测法和链地址法，哪种在装填因子 α > 1 时仍能正常工作？

答：链地址法。开放定址法要求 α ≤ 1（最多填满整个表），而链地址法通过链表延伸，α 可以大于 1。与第 96 题连考。

【知识关联】

• 同库连考：与第 71/105 题（线性探测 ASL 计算）、第 95 题（效率取决于哈希函数与 α）、第 96 题（装填因子）、第 98-100 题（HashMap 等）构成哈希章；与第 74 题（查找算法比较）中哈希 O(1) 前提相扣。
• 工程实现：Java HashMap=链地址+树化；Python dict=开放定址（扰动+删除墓碑）；Redis dict=链地址+渐进 rehash。面试常考「JDK 为何链地址」「开放定址删除为何不能置空」。
• 408 / 国企真题：408「哈希表冲突处理方法」分类题，标准三分：开放定址、链地址、再哈希；干扰项给「二分查找」「顺序查找」等无关算法。国网计算题常用线性探测（属开放定址）。
• 面试追问:①「再哈希 vs 二分查找？」（前者是冲突解决，后者是有序表查找算法，完全无关）；②「α>1 哪种方法可能？」（链地址）；③「聚集现象？」（线性探测一次聚集，二次探测缓解）。

【拓展延伸】

变式问法:①「不是冲突解决方法？」（二分查找法，本题）；②「开放定址包括？」（线性/二次探测、双重哈希）；③「拉链法优点？」（删除简单、α 可 >1）。

工程映射：缓存键冲突、布隆过滤器（用多重哈希而非冲突链）、一致性哈希环负载均衡，都是哈希冲突/分布问题的工程变体。

易错提醒：再哈希法是冲突解决，不要因为名字里有「哈希」以外的字就误判；二分查找依赖有序，与哈希「不依赖有序」的设计哲学相反。

---

98. 关于 Java 中的 HashMap、Hashtable 与 ConcurrentHashMap，下列说法正确的是( )

标签：【互联网 Java 笔试超高频】

A. 三者都是线程安全的，区别仅在于性能高低 B. ConcurrentHashMap 与 Hashtable 一样，读操作也需要加锁 C. ConcurrentHashMap 通过给整个哈希表加一把全局锁来保证线程安全 D. Hashtable 不允许 key 或 value 为 null,ConcurrentHashMap 同样不允许 null 键值

答案：D

【结论】 Hashtable 与 ConcurrentHashMap 都不允许 null 键值，该说法正确，选 D。

【逐项辨析】

• A错：HashMap 非线程安全，三者并非都线程安全。
• D 对:Hashtable 不允许 key 或 value 为 null,ConcurrentHashMap 同样不允许 null 键值。
• C错：JDK 1.8 起 ConcurrentHashMap 锁的是单个桶（synchronized 头结点），而非整表一把全局锁。
• B错：ConcurrentHashMap 读操作不加锁，依靠 volatile 保证可见性；而 Hashtable 读也要加锁。

【知识点】 三容器核心差异（互联网面试超高频，必背）：

特性	HashMap	Hashtable	ConcurrentHashMap
线程安全	❌ 否	✅ 是	✅ 是
锁机制	无	synchronized 方法级（整表锁）	JDK1.7 分段锁；JDK1.8 CAS+synchronized 桶级锁
null key	✅ 允许 1 个	❌ 不允许	❌ 不允许
null value	✅ 允许	❌ 不允许	❌ 不允许
读操作	无锁	加锁	不加锁
并发性能	低（单线程）	低（整表锁）	高（细粒度锁）
JDK1.7 扩容	头插法（可能成环）	-	段内扩容
JDK1.8 优化	红黑树（同桶链长超过 8 且表长≥64）	-	红黑树 + CAS

ConcurrentHashMap 的演进:

JDK 1.7: 分段锁(Segment)
  - 把哈希表分成 16 段,每段一把锁
  - 并发度 = 16(默认)

JDK 1.8: CAS + synchronized(桶级锁)
  - 锁单个桶的头结点,粒度更细
  - 读完全不加锁,靠 volatile 保证可见性
  - 同一桶链长超过 8（实测第 9 个节点）且表长 ≥64 时转红黑树,查找从 O(n) 降到 O(log n)

为什么 ConcurrentHashMap 不允许 null?

并发环境下无法区分“key 不存在”与“key 存在但 value 为 null”——多线程下这种二义性会导致严重 bug。

【记忆锚点】 “HashMap 允许 null，线程安全的不允许；ConcurrentHashMap 读不加锁，Hashtable 全加锁”。

【易混对比】 HashMap vs ConcurrentHashMap 的“容量为 2 的幂”：两者都是，目的是让 (n-1) & hash 代替取模运算，加速定位桶位置（见第 78 题）。但 Hashtable 容量不要求为 2 的幂，它直接用 % 取模。

【自测】 三个容器中，哪个允许 null key 且非线程安全？哪个线程安全但读操作不加锁？

答：允许 null key 且非线程安全的是 HashMap；线程安全但读不加锁的是 ConcurrentHashMap。与第 73、78 题连考。

【知识关联】

• 同库连考：与第 73 题(HashMap)、第 78 题（2 的幂）、第 96 题(α)。
• 工程实现:CHM JDK7 分段锁，JDK8 CAS+synchronized 桶头；Hashtable 全表锁。
• 408 / 国企真题:Java 笔试超高频。
• 面试追问:①「CHM 为何不允许 null？」（get 返回 null 歧义）；②「size 怎么算？」（累加 counter cells）。

【拓展延伸】

完整对照已在原解析；面试常追问「ConcurrentHashMap 读要锁吗？」（JDK8 读基本不加锁）。

变式:Collections.synchronizedMap、ConcurrentSkipListMap。

工程应用：高并发缓存计数、注册表。

---

99. 哈希表的平均查找长度(ASL)与以下哪个因素无关？

标签：【互联网/国企笔试高频】

A. 哈希函数 B. 处理冲突的方法 C. 装填因子 D. 数据的排序方式

答案：D

【结论】 哈希表 ASL 与数据的排序方式无关，选 D。

【逐项辨析】

• A 哈希函数：影响冲突分布，与 ASL 有关。
• B 处理冲突的方法：线性探测 / 链地址等不同方法 ASL 公式不同，与 ASL 有关。
• C 装填因子：直接影响冲突概率，与 ASL 有关。
• D 数据的排序方式：哈希表不依赖有序性，与 ASL 无关。

【知识点】 哈希表 ASL(Average Search Length)的影响因素

哈希表的查找过程:
  1. 用哈希函数计算地址 H(key)
  2. 若该地址为空 → 查找失败,比较 1 次
  3. 若该地址有记录但 key 不匹配 → 按冲突处理方法继续查找
  4. 直到找到或确定不存在

ASL 取决于:
  - 哈希函数好坏(决定冲突多少)
  - 装填因子 α(决定表有多满)
  - 冲突处理方法(决定冲突后怎么找)

冲突处理方法	查找成功 ASL	查找失败 ASL
线性探测	≈ (1/2)(1 + 1/(1-α))	≈ (1/2)(1 + 1/(1-α)²)
二次探测	≈ -(1/α) ln(1-α)	≈ 1/(1-α)
链地址法	≈ 1 + α/2	≈ α + e^(-α)

失败 ASL 的计次口径说明（不是知识点对立）： 上表链地址法的 α + e^(-α) 按「空链判空算 1 次、非空链只数链上关键字比较」统计；若把「探测到链尾空指针」那一次也计入，则期望为 1 + α（另一本教材的常见写法）；若只数关键字比较、空链记 0 次，则为 α。三者在同一 α 下依次相差约 1 − e^(-α) 与 1。实测（表长 m=20000、α=0.75、20 万次随机失败查找）三种口径得 1.224 / 1.752 / 0.752，与 α + e^(-α)=1.222、1 + α=1.750、α=0.750 吻合——做题时先看题干按哪种口径，别把 1 + α 当成与 α + e^(-α) 矛盾的另一公式。

核心规律：ASL 只与 α 和冲突处理方法有关，与数据原始顺序完全无关——因为哈希函数把 key 直接映射到地址，不利用任何有序信息。

【记忆锚点】 “哈希看映射，不看顺序；ASL 看 α，不看排序”——哈希表的本质是“散列”，不是“有序查找”。

【易混对比】 注意与“二叉排序树”和“二分查找”区分：后两者依赖有序性,ASL 与数据插入顺序有关（如 BST 退化成链表）；哈希表 ASL 与数据排序方式无关。与第 95 题连考：哈希表查找效率取决于哈希函数和装填因子，与数据是否有序无关。

【自测】 同一组数据，先排序再建哈希表，与不排序直接建哈希表，两者的 ASL 是否相同？

答：相同。哈希表 ASL 只与哈希函数、装填因子和冲突处理方法有关，与数据原始顺序无关。与第 95 题连考。

【知识关联】

• 同库连考：与第 95 题同型；与第 69 题（BST 与顺序有关）对照。
• 工程实现：哈希打乱顺序 → ASL 与输入顺序基本无关（除碰撞次序微小影响）。
• 408 / 国企真题：辨析题。
• 面试追问:①「BST 为何与顺序有关？」（形态依赖插入序）；②「哈希与 α？」（有关）。

【拓展延伸】

完整验算：同一集合不同插入序，链地址 ASL 期望相同。

变式：开放定址不同插入序探测路径可能不同，但 ASL 统计仍主要看 α。

工程应用：解释「哈希不适合有序遍历」。

---

100. 一个好的哈希函数应具备的特点不包括( )

标签：【互联网/国企笔试高频】

A. 计算简单快速 B. 哈希地址分布均匀 C. 保证不发生冲突 D. 减少冲突的可能性

答案：C

【结论】 “保证不发生冲突”不是哈希函数的要求，选 C。

【逐项辨析】

• A 是要求：计算简单快速，降低单次哈希开销。
• B 是要求：哈希地址分布均匀，减少聚集现象。
• C 不是要求：完全避免冲突是不可能的（除非是完美哈希，且需要事先知道所有关键字）。
• D 是要求：尽量减少冲突的可能性，这是哈希函数的设计目标之一。

【知识点】 好的哈希函数应满足的条件

条件	含义	原因
计算简单	哈希函数本身不能成为性能瓶颈	每次查找都要计算 H(key)
分布均匀	不同 key 尽量映射到不同地址	减少冲突和聚集
减少冲突	尽量降低冲突概率	冲突会降低查找效率

冲突的必然性:

- 哈希函数把无限(或大量)的 key 映射到有限的地址空间
- 根据鸽巢原理,冲突不可避免
- 因此哈希表必须配套"冲突处理方法"
- 完美哈希(无冲突)只能在"所有关键字事先已知"的特殊场景实现

常见哈希函数构造方法：1. 直接定址法:H(key) = a·key + b（适用于 key 分布连续） 2. 除留余数法:H(key) = key % p（p 为不大于表长的质数，最常用）。为什么取质数：p 为偶数时 key 的奇偶性直接决定 H(key) 的奇偶性、低位不参与混布，冲突显著增多；取质数可让 key 的各位都参与取模，散列更均匀。 3. 平方取中法：取 key² 的中间几位 4. 折叠法：把 key 分成若干段再叠加

【记忆锚点】 “简单、均匀、减冲突，不保证零冲突”——好哈希函数的三要一不要。

【易混对比】 “减少冲突”(D)与“保证不冲突”(C)是本质区别：前者是设计目标（尽量降低概率），后者是不可能完成的任务（除非完美哈希）。哈希表的核心设计思想就是“接受冲突、管理冲突”，而不是“消除冲突”。

【自测】 除留余数法中，为什么通常取 p 为质数而不是偶数？

答：若 p 为偶数，key 的奇偶性会直接决定 H(key) 的奇偶性，导致分布不均；取质数可使 key 的各位都参与运算，分布更均匀。与第 95 题连考。

【知识关联】

• 同库连考：与第 97 题（冲突方法）、第 95 题（效率因素）收束全库哈希模块；与第 65~78 题查找方法对比表（原库「五种查找」）。
• 工程实现：选型口诀已写在原解析；工程 HashMap≈哈希+树化。
• 408 / 国企真题：查找综述题。
• 面试追问:①「什么时候不用哈希？」（要范围查询/有序）；②「磁盘上为何 B+ 树？」（哈希随机 IO 差）。

【拓展延伸】

完整验算对照:

顺序 O(n) / 二分 O(log n) / BST 平均 log 最坏 n
哈希均 O(1) / 分块 ~√n

变式：布谷鸟哈希、跳表与平衡树对比。

工程应用：按场景选结构是架构基本功。

---