Day 15　哈希表

建议用时：15～25 分钟。请先完成自主学习，再独立提交本页答案。

今日学习资料

• 打开今日蓝白学习页
• 下载今日 PDF

学习目标：完成当天知识点阅读与易错清单自查，然后作答下方选择题。

今日练习

1. 下列关于哈希表的说法， 错误 的是（　）。

{{ select(1) }}

• 哈希表的基本思想是用哈希函数把关键字直接算成数组下标，从而用「算」代替「找」
• 只要关键字的取值范围大于表长，由鸽巢原理，冲突就一定无法避免
• 只要哈希函数设计得足够好，哈希表在最坏情况下的查找时间复杂度也是 O(1)
• 装填因子越大，哈希表越拥挤，发生冲突的可能性通常越大

2. 【CSP-J 2020 初赛】将 (2, 7, 10, 18) 分别存储到某个地址区间为 0～10 的哈希表中，如果哈希函数 h(x) = （　），将不会产生冲突（其中 a mod b 表示 a 除以 b 的余数）。

{{ select(2) }}

• x² mod 11
• 2x mod 11
• x mod 11
• ⌊x/2⌋ mod 11（⌊x/2⌋ 表示 x/2 下取整）

3. 用除留余数法 h(k) = k mod p 构造哈希表，下列关于模数 p 选取的说法，正确的是（　）。

{{ select(3) }}

• p 取 2 的整数次幂最好，既能用位运算加速取模，冲突也最少
• p 一般取不超过表长的最大质数，这样关键字能散得更均匀
• p 必须大于所有关键字，否则不同的关键字会算出相同的下标
• p 的取值只影响取模的计算速度，不影响冲突的次数

4. 某哈希表表长 m = 13，采用拉链法解决冲突，目前已存入 9 个元素，其中 3 个元素挂在同一条链上。该哈希表的装填因子 α 等于（　）。

{{ select(4) }}

• 9/13
• 13/9
• 3/13
• 1

5. 【CSP-S 2022 初赛·提高组】给定地址区间为 0～9 的哈希表，哈希函数为 h(x) = x mod 10，采用线性探测的冲突解决策略（冲突时向后探测第一个空地址，地址 9 冲突则从地址 0 继续往后）。哈希表初始为空表，依次存储 (71, 23, 73, 99, 44, 79, 89) 后，89 存储在哈希表的哪个地址中（　）。

{{ select(5) }}

• 9
• 0
• 1
• 2

6. 【CSP-S 2021 初赛·提高组】现有一个地址区间为 0～10 的哈希表，对于出现冲突的情况，会往后找第一个空的地址存储（到 10 冲突了就从 0 开始往后）。现在要依次存储 (0, 1, 2, 3, 4, 5, 6, 7)，哈希函数为 h(x) = x² mod 11。请问 7 存储在哈希表的哪个地址中（　）。

{{ select(6) }}

• 5
• 6
• 7
• 8

7. 沿用第四节的例子：表长 m = 11，哈希函数 h(k) = k mod 11，依次插入 22、41、53、46、30、13，采用 拉链法 解决冲突（新元素接在所在链的末尾）。若查找每个关键字的概率相同，则查找成功的平均查找长度 ASL 是（　）。

{{ select(7) }}

• 1
• 4/3
• 3/2
• 2

8. 下列关于 C++ STL 中 map 与 unordered_map 的说法，正确的是（　）。

{{ select(8) }}

• 两者底层实现完全相同，只是名字不同
• unordered_map 中的元素按键从小到大有序排列
• map 基于红黑树，单次查找 O(log n) 且元素有序；unordered_map 基于哈希表，单次查找平均 O(1) 但元素无序
• unordered_map 在任何情况下的查找都是 O(1)，因此任何场合都比 map 快

9. 【CSP-S 2024 初赛·提高组】在设计一个哈希表时，为了减少冲突，需要使用适当的哈希函数和冲突解决策略。已知某哈希表中有 n 个键值对，表的装填因子为 α（0 < α ≤ 1）。在使用开放地址法解决冲突的过程中，最坏情况下查找一个元素的时间复杂度为（　）

{{ select(9) }}

• O(1)
• O(log n)
• O(1/(1−α))
• O(n)

10. （判断题）采用拉链法解决冲突时，装填因子 α 可以大于 1；而采用开放定址法时，必须保证 α < 1。（　）

{{ select(10) }}

• 正确
• 错误