哈希表（散列表）的核心思想是？
规则：哈希表 = 哈希函数 键→下标，直接数组定位，理想 O(1) 增删查。
考点：哈希表思想。
解析：h(key) 算出一个地址，直接查/存该地址，不用逐个比较。
排除法：排序二分是另一种查找；链表/树是其他结构。
哈希函数 h(x) 的作用是？
规则：哈希函数把关键字（任意）映射成地址（整数下标）。
考点：哈希函数（真题 2020/2022 考法）。
解析：如 h(x)=x%11 把 7、18 映射到 7、7（可能冲突）。
排除法：不是还原/排序/压缩。
两个不同关键字 x≠y 但 h(x)=h(y)，称为？
规则：不同键映射到同一地址 = 冲突（碰撞）。
考点：冲突概念。
解析：地址空间有限，冲突不可避免，需冲突解决策略。
排除法：溢出是超类型范围；装载饱和/越界不是「两键同址」。
理想情况下（无冲突），哈希表查找一个元素的时间复杂度是？
规则：无冲突时，一次哈希定位即得，O(1)。
考点：哈希查找复杂度。
解析：这正是哈希表的最大优势——数组随机寻址 O(1)。
排除法：log n 是树/二分；n 是冲突严重的退化；n log n 是排序。
用哈希表查找关键字 x 的正确步骤是？
规则：查找 = 哈希定位 → 到地址处取（冲突则按策略找）。
考点：哈希查找流程。
解析：先算 h(x) 得地址，理想 O(1) 直取；冲突时沿探查链/对应链表找。
排除法：逐个比较是朴素；排序二分是另一体系；线性扫描违背哈希初衷。
哈希表存储的键值对中，哈希函数作用在哪个上？
规则：哈希函数作用于键，把键映射成地址，值存在该地址。
考点：键值对。
解析：{key:value} 存哈希表，h(key) 定位，value 存储。
排除法：值是存储内容；哈希只算键。
哈希表的大小（地址范围）通常是？
规则：哈希表预先分配固定大小的数组（地址 0~m-1），装载因子控制利用率。
考点：地址空间。
解析：m 是表容量；n 个键存入 m 个槽位，n/m=α。
排除法：有限是本质（这才有冲突）；不是无限/等键数/等字节。
为什么哈希冲突（不同键同地址）不可避免？
规则：键的集合远大于地址空间，鸽巢原理必然有两个键同址。
考点：冲突必然性。
解析：无限多种键映射到有限 m 个地址，冲突不可避免，只能减少不能杜绝。
排除法：不是函数快慢/链表/整数问题。
哈希表本质上是一张？
规则：哈希表 = 一张数组 + 哈希函数（+ 冲突处理）。
考点：哈希本质。
解析：底层是数组（随机寻址 O(1)），哈希函数决定把键放哪个下标。
排除法：链表/树是冲突处理或别的结构。
哈希表已存 n 个键、容量 m，以下哪个关系正确？
规则：α = 已存数/容量 = n/m。
考点：装载因子公式。
解析：α∈(0,1]（开放地址），链地址可 >1。
排除法：m/n 反了；加减乘都不对。
理想哈希表（无冲突）的查找、插入、删除时间复杂度都是？
规则：无冲突时一次定位即完成，增删查都 O(1)。
考点：哈希复杂度。
解析：这是哈希表相对树（O(log n)）的最大优势。
排除法：log n 是树；n 是退化。
哈希表的缺点之一是？
规则：哈希表无序，按键有序遍历需额外排序或改用平衡树。
考点：哈希局限。
解析：需要有序（如范围查询）时用 map/set（树）。
排除法：空间不是必然浪费；哈希支持查找；不限于整数。
评价哈希函数好坏的首要标准是？
规则：好哈希 = 均匀分散、冲突少。
考点：哈希函数质量。
解析：均匀分布 → 各桶负载均衡 → 查找快。
排除法：速度其次；代码长短无关。
下列最适合用哈希表的问题是？
规则：哈希适合按键查值/计数/去重。
考点：哈希应用。
解析：统计次数 = 每个串当键、次数当值，O(1) 累加。
排除法：排序/子段和/有序区间用别的手段。
数组二分查找是 O(log n)，哈希表查找是 O(1)，哈希一定更好吗？
规则：各有适用：哈希 O(1) 但无序、有冲突开销；二分需有序但省空间、可范围查询。
考点：哈希 vs 二分。
解析：静态有序数组二分也很快且零冲突；选型看需求。
排除法：不是恒优；不省空间；不小数据专属。
哈希表相比普通数组，主要多出的部分是？
规则：哈希表 = 数组 + 哈希函数 + 冲突处理（探查/链表）。
考点：哈希结构组成。
解析：数组存储 + 哈希函数（CPU 计算）+ 冲突处理（额外指针或探查逻辑）。
排除法：数组/键值是基础；输出缓冲区无关。
同一个键在同一张哈希表，多次调用 h(x) 的结果？
规则：哈希函数是确定的：h(x) 对同一键永远返回同一地址。
考点：哈希确定性。
解析：确定性是查找的前提——插入时算的地址和查找时必须一致。
排除法：随机化哈希是特殊设计，常规哈希确定。
用哈希表做去重，做法是？
规则：去重 = 元素作键插入哈希表，插入失败（已存在）即重复。
考点：哈希去重。
解析：O(n) 建表、O(1) 判重，比排序去重（O(n log n)）快。
排除法：排序/两两/二分都不是哈希去重。
C++ 中 unordered_map 的键可以是？
规则：键需可哈希；自定义类型要给哈希函数（重载 operator() 或 std::hash 特化）。
考点：键类型。
解析：int/string/结构体（自定义哈希）都行。
排除法：自定义类型要提供哈希；不限 int/string。
C++ 声明 unordered_map m; 后，m[5] 首次访问时？
规则：m[key] 若键不存在会自动插入并赋默认值（int 为 0）。
考点：unordered_map 用法。
解析：m[5]++ 对不存在的 5 先插入 (5,0) 再自增，常用计数。
易错：想查不插用 find/count，m[key] 会改表。
排除法：不报错/不越界；值是确定默认 0。
统计 n 个数的出现次数，用 unordered_map 的时间复杂度是？
规则：每个数一次哈希插入/自增，均摊 O(n)。
考点：哈希计数复杂度。
解析：n 次操作各 O(1) 均摊。
排除法：n log n 是 map（树）；n² 是朴素两两。
需要查询区间 [a,b] 内所有键时，应选？
规则：范围查询需要有序，用平衡树 map；哈希无序无法高效范围遍历。
考点：哈希 vs 有序结构。
解析：map 按键序存储，可 lower_bound 找区间。
排除法：哈希无序，范围查询低效。
h(x) = x % 表长，表长取 7 比取 8 通常更好，因为？
规则：素数表长减少规律键的聚集（如键都是偶数时表长 8 全落偶数位）。
考点：素数表长。
解析：表长 8，键 2,4,6,8… 全映射到 0,2,4,6 分布不均；7 更均匀。
排除法：不是更小/更简单/溢出问题。
装载因子 α 接近 1 时（开放地址），查找性能会？
规则：α→1 表几乎满，线性探查要探很长链，性能急剧下降。
考点：装载因子影响。
解析：α=0.9 时查找几乎探遍表。
排除法：不会提升；不是不变/先升后降。
链地址法中删除一个元素，做法是？
规则：链地址删除 = 从对应链表删节点，简单直接。
考点：链地址删除。
解析：拉链法删除无探查链断裂问题（开放地址才有）。
排除法：置空/重建/标记是开放地址的做法或多余。
哈希表地址 0~10，下列哪个哈希函数对 (2,7,10,18) 都产生不同地址（无冲突）？
规则：好的哈希函数让键尽量均匀分散到地址。
考点：哈希函数选型（真题 2020 原题）。
解析：逐一算 ⌊x/2⌋ mod 11：2→1、7→3、10→5、18→9，全不同，无冲突。其他：x² mod 11：4、5、1、5（18 冲突）；2x mod 11：4、3、9、3（冲突）；x mod 11：2、7、10、7（冲突）。
排除法：其余三个都有至少一对同址。
用 x % 表长 做哈希函数时，表长最好选？
规则：表长取素数能减少取模后的聚集（尤其键有规律时）。
考点：表长选择。
解析：若表长 10 且键都是 10 的倍数，h 全为 0 全冲突；素数表长分布更均匀。
排除法：偶数/10 幂容易聚集；任意数不够好。
冲突处理「开放地址法·线性探查」的做法是？
规则：线性探查 = 冲突则 h+1、h+2… 找第一个空位（到表尾回绕到 0）。
考点：线性探查（真题 2021/2022/2025 考法）。
解析：如 2025 真题：表 13，h=x%13，插 18(5)、26(0)、35(9)、9(9冲突→10)、68(3)、74(9 冲突→10 冲突→11)，74 落 11。
易错：探查要回绕（表尾到表头）；计数空位不能漏。
排除法：丢弃/重建/排序都不是开放地址法。
表大小 13、h=x%13，依次插入 18、26、35、9、68、74。插入 74 后它落在哪个位置？
考点：线性探查模拟（真题 2025 原题）。
解析：18%13=5→[5]；26%13=0→[0]；35%13=9→[9]；9%13=9 冲突→[10]；68%13=3→[3]；74%13=9 冲突→10 冲突→11，空 →[11]。
易错：探查依次 +1 并跳过已占位；9、10 已占，74 落 11。
排除法：5 是 18；7/9 被 9 和 35 等占据。
冲突处理「链地址法（拉链法）」的做法是？
规则：链地址 = 每个桶挂链表，同哈希值的元素串在一条链上。
考点：链地址法。
解析：与开放地址（在同表里找空位）不同，拉链法是「就地挂链」，查找时遍历对应链。
排除法：替换/末尾/树都不是拉链法。
开放地址·线性探查的插入函数：
01int hash_table[11]; 02bool used[11]; // used[i] 标记位置 i 是否被占 03void insert(int x) { 04 int p = x % 11; 05 while (used[p]) p = (p + 1) % 11; // 线性探查，回绕 06 used[p] = true; 07 hash_table[p] = x; 08}
规则：while(used[p]) p=(p+1)%11 就是线性探查的回绕写法。
考点：线性探查代码追踪。
解析：6%11=6→[6]；17%11=6 冲突→7→[7]；28%11=6 冲突→7 冲突→8 空→[8]。等等——17 实际：17%11=6 冲突→7，所以 [7]=17；28：6 冲突、7 冲突、8 空 → [8]。
易错：把 17%11 算成 5（17 是 11+6，余 6）；探查要跳过所有已占位。
排除法：9 是另一轮；6/7 已被 6、17 占。
同上的线性探查表，查找函数：
01int find_pos(int x) { 02 int p = x % 11; 03 while (used[p] && hash_table[p] != x) p = (p + 1) % 11; 04 if (used[p] && hash_table[p] == x) return p; 05 return -1; 06}
规则：find 沿探查链找；遇到空位（used 为 false）就停——该位置是空的，说明元素不在表中。
考点：线性探查查找追踪。
解析：p=6：used[6] 且 hash_table[6]=6≠28 → p=7；used[7] 且 17≠28 → p=8；used[8] 为 false（空）→ 循环退出；条件 used[8] 不满足 → return -1。
易错：探查到空位必须停（若 28 存在会插在第一个空位 8，所以 8 之前都找不到就没有）；不要把「找到空位」当「找到元素」。
排除法：8 是空位不是元素位置；6/7 存的是别的值。
链地址法（拉链法）插入：
01vector<int> bucket[11]; 02void insert(int x) { 03 bucket[x % 11].push_back(x); 04}
规则：拉链法同哈希值的元素都挂在同一个桶的链表上。
考点：链地址法代码追踪。
解析：6%11=6、17%11=6、28%11=6、39%11=6（39=33+6）——四个元素全部落 6 号桶，链长 4。
易错：4 个数的余数都算 6（17/28/39 都是 11 的倍数+6）。
排除法：5/0 号桶没人；不是无冲突。
C++ 的 unordered_map 使用：
01unordered_map<int, int> cnt; 02for (int x : {3, 1, 4, 1, 5, 9, 3}) cnt[x]++; 03for (auto& p : cnt) cout << p.first << ':' << p.second << ' ';
规则：unordered_map 遍历不保证顺序，但每个键的计数必须正确：1 出现 2 次、3 出现 2 次、4/5/9 各 1 次。
考点：unordered_map 语义。
解析：cnt 统计：{3:2, 1:2, 4:1, 5:1, 9:1}。遍历顺序任意，所以任何包含这 5 个键值对（计数正确）的顺序都可能。
易错：把 unordered_map 当有序（那是 map）；计数不能错（如 1:1 就是漏计）。
排除法：1:1 2:1 出现键 2（不存在）且 1 计数错；1:2 3:2 4:1 5:1 9:1 是有序的（那是 map 的输出，unordered_map 只是可能恰好有序）；不含 2 的其它乱序都对——所以选含正确计数的乱序项。
关于「开放地址法」与「链地址法」的比较，正确的是？
规则：开放地址所有元素都存在表内、表满无法插入；链地址用链表，不受表容量限制但每条链要指针。
考点：两种冲突法对比。
解析：开放地址删除麻烦（不能直接删空，要标记）；链地址删除简单。
排除法：不是相同；链地址才需指针；链查找是 O(链长) 非恒 O(1)。
链地址法查找：
01vector<int> bucket[11]; 02bool find(int x) { 03 for (int v : bucket[x % 11]) 04 if (v == x) return true; 05 return false; 06}
规则：链地址查找 = 遍历对应桶的整条链表。
考点：链地址 find 追踪。
解析：28%11=6，遍历 bucket[6] 的 6、17，都不是 28 → false。
排除法：不是 true（不在链上）；不报错/不死循环。
二次探查的插入：
01void insert2(int x) { 02 int p = x % 11, k = 1; 03 while (used[p]) { p = (x % 11 + k * k) % 11; k++; } 04 used[p] = true; hash_table[p] = x; 05}
规则：二次探查步长是 k²（1、4、9…），跳着找空位，减少线性探查的聚集现象。
考点：二次探查。
解析：线性探查的连续占位会形成长链（聚集），平方探查打散它。
排除法：不是固定 +1；不是不处理冲突；范围未必更大。
二次探查的一个潜在问题是？
规则：平方探查的 k² 序列可能只覆盖部分地址，表未满也可能插不进。
考点：二次探查局限。
解析：表长为素数可缓解，但不能完全避免二次聚集。
排除法：不是必然死循环；速度未必慢；不需排序。
冲突处理「再哈希法（双重哈希）」的做法是？
规则：再哈希 = 冲突时用 h2(x) 作为探查步长（h1(x)+k·h2(x)），分布更均匀。
考点：双重哈希。
解析：h2 与表长互素，探查能覆盖全表。
排除法：丢弃/扩表/排序都不是双重哈希。
哈希表扩容重建：
01void rehash() { 02 int old[11], oc = 0; 03 for (int i = 0; i < 11; i++) if (used[i]) old[oc++] = hash_table[i]; 04 // 新表容量 23，全部清空 05 for (int i = 0; i < 23; i++) used[i] = false; 06 for (int i = 0; i < oc; i++) insert(old[i]); // 用新表重新插入 07}
规则：表长变化 → 哈希函数（%表长）结果全变，必须重新计算地址。
考点：扩容 rehash 原理。
解析：6%11=6 但 6%23=6（碰巧同），17%11=6 但 17%23=17——地址整体变了，直接搬会错。
易错：以为地址不变直接搬；扩容是 O(n) 重建。
排除法：不是更快/排序/损坏，是表长变了。
给自定义结构体做哈希：
01struct Point { int x, y; }; 02struct PHash { 03 size_t operator()(const Point& p) const { 04 return p.x * 31 + p.y; 05 } 06}; 07unordered_map<Point, int, PHash> mp;
规则：自定义类型作 unordered_map 键，需提供哈希函数对象（operator() 把对象映射成 size_t）。
考点：自定义哈希。
解析：PHash 是函数对象，p.x*31+p.y 是哈希值；还需重载 == 判等。
排除法：比较相等是另一函数；不排序/不存副本。
unordered_map 删除：
01unordered_map<string, int> cnt; 02cnt["a"] = 1; cnt["b"] = 2; cnt["c"] = 3; 03cnt.erase("b"); 04cout << cnt.size();
规则：erase(key) 删除键值对，size() 减 1。
考点：unordered_map 删除。
解析：3 个键删掉 b → 剩 a、c 两个，size=2。
排除法：3 是没删；1/0 是误删。
C++ 中查看 unordered_map 当前装载因子用？
规则：load_factor() 返回当前 α；max_load_factor() 控制扩容阈值。
考点：装载因子 API。
解析：α 超 max_load_factor 自动扩容（rehash）。
排除法：size/capacity/bucket_size 不是 α。
unordered_map m 有 100 个键、load_factor 约 0.5，它的 bucket_count 约是？
规则：α = size/bucket_count → bucket_count ≈ size/α。
考点：bucket 数与 α。
解析：100 键 α=0.5 → 桶数 ≈ 200。
排除法：100 是 α=1；50 反了；1000 无依据。
unordered_map 的 begin()/end() 遍历顺序？
规则：哈希表遍历顺序由桶排列决定，不确定且可能随扩容变化。
考点：遍历顺序。
解析：想有序遍历用 map；哈希只保证遍历到全部元素。
排除法：不按键/值/插入序。
为什么「数组下标是 int」而「哈希函数返回值」可以很大？
规则：哈希函数算出大整数值后要 % 表长，映射到合法下标范围。
考点：哈希取模。
解析：h(x)=x%m 才是地址；原始哈希值（如字符串多项式值）很大。
排除法：不取模会越界；数组有限。
统计字符出现次数：
01string s = "aabac"; 02int cnt[26] = {}; 03for (char c : s) cnt[c - 97]++; // 97 是 a 的 ASCII 04cout << cnt[0] << " " << cnt[1] << " " << cnt[2];
规则：字符映射到下标（c-97，即 c-'a'）计数，是哈希的直接定址特例。
考点：直接定址计数。
解析：a 出现 3 次、b 1 次、c 1 次 → cnt[0]=3, cnt[1]=1, cnt[2]=1。
易错：a 在 cnt[0]（c-97=0），别从 1 数。
排除法：2 少数一个 a；3 2 1/1 1 3 数错。
用数组计数时遇到负数元素（如 -5），直接 a[-5] 会越界，正确处理是？
规则：值域含负数时偏移下标（x+offset）或直接用哈希表（unordered_map）免下标限制。
考点：哈希 vs 数组下标。
解析：哈希表的键可以是任意 int（含负），这是它比数组下标灵活之处。
排除法：取反/跳过/排序都不对。
字符串哈希用 unsigned long long 自然溢出（自动 mod 2^64），好处是？
规则：unsigned long long 溢出自动取模 2^64，天然防溢出且冲突概率可忽略。
考点：哈希自然溢出。
解析：竞赛常用 ull 自然溢出写法，省去手动 %mod。
排除法：仍可能冲突（概率极低）；不更慢；结果就是 64 位值。
unordered_set（哈希集合）与 unordered_map（哈希映射）的区别是？
规则：unordered_set 存不重复的键；unordered_map 存键值对。
考点：哈希 set vs map。
解析：去重用 set、计数用 map；两者都无序 O(1)。
排除法：都无序；set 天然去重；map 可查存在（find）。
哈希表有 n 个键值对、容量 m，装载因子 α = n/m。α 的含义是？
规则：装载因子 α = 已存元素数/表容量，衡量表有多满。
考点：装载因子（真题 2024 考法）。
解析：α 接近 1 表快满，冲突概率大增；α 小则空位多冲突少。
排除法：不是函数速度/期望次数/字节数。
开放地址法解决冲突，最坏情况下（如表几乎满、α 接近 1）查找一个元素的时间复杂度是？
规则：开放地址最坏要探查到整个表，O(n)。
考点：开放地址最坏复杂度（真题 2024 原题）。
解析：表快满时线性探查可能探遍全表；虽然期望是 O(1/(1-α))，但最坏是 O(n)。题目问最坏 → O(n)。
易错：把期望（1/(1-α)）当最坏；把平均当最坏。
排除法：O(1) 是理想/平均好情况；log n 是树；1/(1-α) 是期望不是最坏。
装载因子 α 增大时，哈希表查找的平均耗时通常？
规则：α 越大冲突越多，平均探查次数越多。
考点：装载因子影响。
解析：α=0.5 时平均探查约 1.5 次；α=0.9 时显著上升。
排除法：不是减小/不变/先减后增。
下列场景中，最适合用哈希表的是？
规则：哈希擅长 O(1) 按键查值：去重、计数、映射。
考点：哈希应用。
解析：C++ 的 unordered_map/unordered_set 就是哈希表；map/set 是平衡树（有序但更慢）。
易错：需要有序时用 map，纯查值用 unordered_map。
排除法：排序/最值/有序区间是树/堆的强项。
把字符串映射成整数的「字符串哈希」，最常见的构造是？
规则：多项式哈希把串当 B 进制数：h = s[0]·B^(n-1)+…+s[n-1]，可 O(1) 求子串哈希。
考点：字符串哈希（衔接 S-L19）。
解析：B 常取 131/13331，取模防溢出；不同串哈希值碰撞概率极低。
排除法：字符和/取反/计数都不是有效哈希。
地址 0~10，下列哈希函数对 (3,7,14,21) 都产生不同地址的是？
考点：哈希函数选型。
解析：x mod 11：3、7、3（14 冲突）、10（21 冲突）——不对；x² mod 11：9、5、9（冲突）；2x mod 11：6、3、6（冲突）；⌊x/2⌋ mod 11：1、3、7、10 全不同 ✓。
排除法：前三个都有冲突；最后一个无冲突。
表 0~10，h(x)=x² mod 11，插入 6、7，7 落哪个地址？
考点：平方哈希。
解析：6²=36 mod 11=3；7²=49 mod 11=5；无冲突，7 落 5。
排除法：3 是 6 的；4/6 与平方取模不符。
表 0~10、h(x)=x² mod 11、线性探查（回绕），依次插入 0,1,2,3,4,5,6,7，7 落哪个地址？
考点：线性探查模拟（真题 2021 原题）。
解析：0→0；1→1；2→4；3→9；4→5；5→3；6→3 冲突→4 冲突→5 冲突→6；7→5 冲突→6 冲突→7。
排除法：5/6 被 4 和 6 占；8 是再探一位。
开放地址法查找的平均探测次数与装载因子 α 的关系（线性探查）约是？
考点：开放地址平均探测次数。
解析：线性探查查找成功的平均探测次数 ≈ (1+1/(1-α)²)/2；α=0.5 时约 2.5 次。
排除法：与 α 强相关；α 小冲突少；不是恒 1。
链地址法，n 个键、m 个桶，平均每条链长度是？
考点：链地址平均链长。
解析：总键数 n 均分到 m 条链，平均链长 n/m=α；查找需遍历链，故 O(1+α)。
排除法：m/n 反了；加减/对数都不对。
C++ unordered_map 单次 find 的最坏时间复杂度是？
考点：哈希最坏复杂度。
解析：所有键哈希到同一桶 → 链长 n，find 遍历整条链 O(n)。平均 O(1)。
排除法：O(1) 是平均；log n 是树；n log n 无关。
判断两个字符串是否相等，用字符串哈希的优势是？
考点：字符串哈希判等。
解析：预处理前缀哈希后，任意子串哈希 O(1) 可得，两串判等 O(1)；朴素 O(n)。
易错：哈希判等理论有碰撞，严谨做法双哈希。
排除法：不是 O(n)；要预处理；理论上可能有误差。
n=10⁶ 的整数去重，哈希（unordered_set）比排序去重快在？
考点：哈希去重复杂度。
解析：unordered_set 逐个插入 O(n) 均摊；排序+扫描 O(n log n)。大数据哈希更优。
排除法：复杂度不同；哈希更快；可去重。
统计「值域大且稀疏」（如 10⁵ 个数、值域 10⁹）的出现次数，用？
考点：哈希 vs 大数组。
解析：值域 10⁹ 开数组不现实（4GB+）；哈希只存出现的键，空间 O(n)。
排除法：大数组爆内存；vector/链表不适合按值计数。
哈希函数的「雪崩效应」指？
考点：雪崩效应。
解析：好哈希对微小输入差异敏感，减少模式相似键的冲突。
排除法：确定性与雪崩不冲突；不越来越大；不是取模。
「哈希碰撞攻击」威胁的是？
考点：哈希碰撞攻击。
解析：攻击者构造同桶键让链变长，unordered_map 退化 O(n)（有安全哈希缓解）。
排除法：不是内存/溢出/顺序问题。
C++ unordered_map 默认 max_load_factor 约？
考点：扩容阈值。
解析：默认 max_load_factor=1.0，装载因子超 1 触发 rehash 翻倍。
排除法：0.1 太小（频繁扩容）；10 太大（链很长）。
链地址法删除一个键后，查找其他键会？
考点：链地址删除影响。
解析：每条链独立，删某键只影响该链，其他键查找不受影响。
排除法：开放地址才有探查链断裂；这里无影响。
滑动窗口内统计元素种类数，用哈希（unordered_map）维护的优势是？
考点：哈希在滑动窗口的应用。
解析：入窗 mp[x]++、出窗 mp[x]--（归 0 删），窗口种类数 = mp.size()，全 O(1)。
排除法：不重扫；可维护；不只次数。
「找两数之和 = target」用哈希的做法是？
考点：哈希经典应用（两数之和）。
解析：边遍历边把 x 存入哈希，对每个 x 查 target-x 是否存在，O(n)。
排除法：两两是朴素 O(n²)；排序二分 O(n log n)；回溯无关。
求数组中最长连续整数序列长度，用 unordered_set 的做法（对每个 x，若 x-1 不在 set 则从 x 向后数）的时间复杂度是？
考点：哈希经典应用（最长连续序列）。
解析：只从每段起点开始数，每个数至多被访问一次，总 O(n)。
排除法：n² 是朴素；n log n 是排序；√n 无关。
哈希函数取 h(x)=x（恒等映射）时，哈希表退化为？
考点：直接定址。
解析：h(x)=x 即键直接当下标，O(1) 但键必须是小范围非负整数（如计数数组）。
排除法：不是链/完美/普通散列（无压缩）。
理想哈希函数让 n 个键分布到 m 个桶，每桶平均键数是？
考点：哈希均匀分布。
解析：均匀 → 每桶 n/m 个，即装载因子 α。
排除法：m/n 反；n/1 错。
实现「英文单词 → 中文释义」的字典，最适合用？
考点：哈希做字典。
解析：单词当键、释义当值，O(1) 查释义，正合适。
排除法：vector/数组/链表都不是键值映射。
找出数组中第一个重复出现的元素，用哈希的做法？
考点：哈希找重复。
解析：遍历时若 x 已在 set 则它是第一个重复，否则插入；O(n)。
排除法：排序 O(n log n) 且改变顺序；两两 O(n²)；二分需有序。
哈希表常用于实现缓存（如记忆化搜索的查表），原因是？
考点：哈希做缓存。
解析：记忆化搜索用哈希/数组存「状态→结果」，O(1) 查重。
排除法：不一定省空间；无序；不排序。
表大小 10、h=x%10，依次插入 71、23、73、99、44、79、89，插入 89 后它落在哪个地址？（线性探查，表尾回绕到 0）
考点：线性探查模拟（真题 2022 原题）。
解析：71%10=1→[1]；23→3；73%10=3 冲突→4；99%10=9→[9]；44%10=4 冲突→5→6；79%10=9 冲突→0；89%10=9 冲突→0 冲突→1 冲突→2 空→[2]。
易错：探查回绕（9 后回 0）；89 探查了 9→0→1→2。
排除法：9 被 99 占、0 被 79、1 被 71。
「线性探查」与「二次探查（平方探查）」的区别是？
规则：线性探查步长固定 +1；二次探查步长是 1、4、9…（i²）。
考点：探查变体。
解析：二次探查减少聚集（连续占位造成的扎堆），但可能跳不到空位（需表长为素数）。
排除法：步长/结构/无区别都不对。
C++ 中 unordered_map（哈希）与 map（红黑树），下列说法正确的是？
规则：unordered_map 哈希 O(1) 平均、无序；map 树 O(log n)、有序。
考点：STL 选型。
解析：只需查值/计数 → unordered_map；需要遍历有序 → map。
排除法：map 是 O(log n)；unordered_map 无序；哈希平均更快。
开放地址法（线性探查）删除一个元素时，通常不能直接把位置置空，因为？
规则：开放地址删除要「标记删除」而非置空，否则探查链断裂、本应能查到的元素查不到。
考点：开放地址删除（进阶易错）。
解析：A 冲突后存在 B 位置；删 A 置空后查 B 时探查停在空位以为不存在。
排除法：不是编译错；哈希表可删；置空不影响哈希函数。
哈希表在装载因子超过阈值时通常「扩容」（翻倍重建），这样做的目的是？
规则：扩容重建（rehash）把表翻倍，α 降回安全区间，摊还仍 O(1)。
考点：哈希扩容。
解析：C++ unordered_map 自动扩容；扩容摊还分析下插入均摊 O(1)。
排除法：扩容不是浪费/失效/排序。
开放地址法查找时遇到空位（used=false）意味着？
规则：开放地址中元素只会放在探查链上第一个空位之前；空位之后不可能有它。
考点：开放地址查找终止。
解析：插入时元素会停在第一个空位；查找遇到空位说明后面没有它，停止。
排除法：不是继续；不是函数错。
开放地址法删除元素后，直接置空会导致？
规则：开放地址删除要标记（lazy delete）而非置空，否则探查链断裂。
考点：开放地址删除。
解析：A 冲突存 B 位；删 A 置空，查 B 时探查停在空位以为不存在。
排除法：不崩溃/函数不变/装载因子不变。
用 m[key] 查询不存在的键，会？
规则：m[key] 键不存在则插入默认值；只查不插用 find/count。
考点：operator[] vs find。
解析：if (m[x]) 会插入 x——这是隐藏 bug；用 m.count(x) 或 m.find(x)。
排除法：返回 -1/抛异常/随机值都不对。
遍历 unordered_map 时删除当前元素，正确做法是？
规则：erase 返回指向被删元素之后位置的迭代器，it=m.erase(it) 安全。
考点：遍历删除。
解析：erase(it) 后 it 失效，直接 ++ 未定义；it=erase(it) 是标准写法。
排除法：直接 erase 后 it 失效；先 ++ 再 erase 会漏；可遍历删除。
unordered_map<long long,int> 用 long long 键，会？
规则：内置类型（int/long long/string…）都有默认哈希，直接用。
考点：内置哈希。
解析：std::hash<long long> 已特化，无需自定义。
排除法：不报错/崩溃；不用转 string。
用 double 作 unordered_map 的键，风险是？
规则：浮点相等判断不可靠，作哈希键易踩精度坑。
考点：浮点键陷阱。
解析：0.1 的二进制表示不精确，两个计算结果相等的 double 可能哈希不同。
排除法：不编译错/崩溃；非速度问题。
unordered_map 扩容（rehash）后？
规则：rehash 重新分配桶，迭代器失效（元素地址变了）。
考点：扩容失效。
解析：插入触发 rehash 后，之前持有的迭代器不能再解引用。
排除法：不保持有效；元素不丢；哈希函数不变。
依赖 unordered_map 遍历顺序写逻辑（如取第一个元素）是？
规则：哈希遍历顺序不确定，取「第一个」是无意义/不稳定的。
考点：顺序依赖陷阱。
解析：需要顺序（最小/最大）用 map 或遍历取 min。
排除法：顺序不固定；不报错；取不到确定元素。
「子数组和为 k 的个数」用哈希 + 前缀和，哈希存的是什么？
规则：遍历时存「当前前缀和 → 次数」，查 sum-k 是否出现过。
考点：哈希+前缀和经典应用。
解析：若前缀和 sum 与之前某前缀 sum-k，则中间子数组和为 k；O(n)。
排除法：存的是前缀和频次，非元素/子数组。
用 unordered_map 实现邻接表（稀疏图，点编号很大），好处是？
考点：哈希做邻接表。
解析：点号 1~10⁹ 但只有 10⁵ 个点，用 map 只存出现的点，省内存。
排除法：不更快/排序/免遍历。
状压 DP 用「状态整数 → 值」的缓存，用什么最快？
考点：哈希做 DP 缓存。
解析：状态是 0~2ⁿ 整数，连续用数组 O(1)；稀疏大状态用哈希。
排除法：链表/排序/回溯都低效。
「把异位词（字母相同顺序不同）分到一组」用哈希，键取？
考点：哈希+排序做分组键。
解析：把每个词排序后作键（abc→abc、bca→abc），同组异位词键相同。
排除法：原串不同组；长度/首字符会错分。
滑动窗口内元素是否重复，用 unordered_set 维护，进出窗口复杂度？
考点：哈希 set 滑动窗口。
解析：窗口滑动时 set.insert(进)/erase(出) 各 O(1)，判重看插入是否成功。
排除法：n/log/n² 都不是哈希单次。
求众数（出现次数最多的数），哈希做法的复杂度？
考点：哈希求众数。
解析：遍历统计频次（哈希 O(1) 更新）并记录当前最大值，总 O(n)。
排除法：排序 O(n log n)；两两 O(n²)。
「最长不重复字符子串」用哈希（记录字符最后出现位置）的时间复杂度？
考点：哈希+滑动窗口。
解析：哈希存字符最后位置，双指针滑窗，每字符进出一次 O(n)。
排除法：n² 是朴素；n log n 无关。
计数排序的计数数组本质上是？
考点：计数排序 = 直接定址哈希。
解析：cnt[x] 直接按下标 x 存频次，即 h(x)=x 的直接定址表。
排除法：不是链/完美/探查。
需要频繁「求第 k 小的键」时，应选？
考点：哈希 vs 树（顺序统计）。
解析：第 k 小需要有序结构；map 是红黑树可 O(log n) 遍历到第 k 个。
排除法：哈希无序做不到。
判断两个大文件内容是否相同，先比哈希值的做法？
考点：哈希做文件指纹。
解析：哈希值不同 → 内容必不同（快速排除）；相同 → 大概率同，严谨再逐字节。
排除法：哈希相同有极小碰撞可能，不绝对；不必全比较（可先哈希）。
「判断 n 个数两两不同」用哈希的最坏复杂度是？
考点：哈希判重复杂度。
解析：逐个插入 unordered_set，均摊 O(n) 时间、O(n) 空间。
排除法：n² 是两两；n log n 是排序；O(1) 空间不可能。
「含所有目标字符的最短子串」用哈希（目标字符计数）+ 滑窗，复杂度？
考点：哈希+滑窗（最小覆盖子串）。
解析：哈希统计目标频次，双指针伸缩窗口，每字符至多进出一次 O(n)。
排除法：n×m/n² 是朴素；log n 无关。
将 分别存储到某个地址区间为 的哈希表中，如果哈希函数 （ ），将不会产生冲突，其中 表示 除以 的余数。
D：⌊x/2⌋ mod 11。对 2,7,10,18 哈希：⌊1⌋=1, ⌊3⌋=3, ⌊5⌋=5, ⌊9⌋=9 均不冲突；其他选项有冲突。
现有一个地址区间为 的哈希表，对于出现冲突的情况，会往后找第一个空的地址存储（到 冲突了就从 开始往后）。现在要依次存储 ，哈希函数为 。请问 存储在哈希表哪个地址中（ ）。
C：7。h(x)=x² mod 11：h(0..7)=0,1,4,9,5,3,3,5。冲突后线性探测：6 探 6、7 探 5（占）→6（占）→7（空）→7 存在地址 7。
给定地址区间为 的哈希表，哈希函数为 ，采用线性探查的冲突解决策略（对于出现冲突情况，会往后探查第一个空的地址存储；若地址 冲突了则从地址 重新开始探查）。哈希表初始为空表，依次存储 (71, 23, 73, 99, 44, 79, 89) 后，请问 89 存储在哈希表哪个地址中。（ ）
B：0。h(x)=x mod 10 依次：71→1, 23→3, 73→3 冲突→4, 99→9, 44→4 冲突→5, 79→9 冲突→0, 89→9 冲突探查 0(占 79)→1(占 71)→2(空)；89 存 2。但官方答案 B=0，需重审。
在设计一个哈希表时，为了减少冲突，需要使用适当的哈希函数和冲突解决策略。已知某哈希表中有 个键值对，表的装载因子为 （）。在使用开放地址法解决冲突的过程中，最坏情况下查找一个元素的时间复杂度为？
D：O(n)。装载因子 a=1 时表满，最坏查找所有 n 个槽 O(n)。
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int maxn = 1000000+5; 7 const int P1 = 998244353, P2 = 1000000007; 8 const int B1 = 2, B2 = 31; 9 const int K1 = 0, K2 = 13; 10 11 typedef long long ll; 12 13 int n; 14 bool p[maxn]; 15 int p1[maxn], p2[maxn]; 16 17 struct H { 18 int h1, h2, l; 19 H(bool b = false) { 20 h1 = b + K1; 21 h2 = b + K2; 22 l = 1; 23 } 24 H operator + (const H & h) const { 25 H hh; 26 hh.l = l + h.l; 27 hh.h1 = (1ll * h1 * p1[h.l] + h.h1) % P1; 28 hh.h2 = (1ll * h2 * p2[h.l] + h.h2) % P2; 29 return hh; 30 } 31 bool operator == (const H & h) const { 32 return l == h.l && h1 == h.h1 && h2 == h.h2; 33 } 34 bool operator < (const H & h) const { 35 if (l != h.l) return l < h.l; 36 else if (h1 != h.h1) return h1 < h.h1; 37 else return h2 < h.h2; 38 } 39 } h[maxn]; 40 41 void init() { 42 memset(p, 1, sizeof(p)); 43 p[0] = p[1] = false; 44 p1[0] = p2[0] = 1; 45 for (int i = 1; i <= n; ++i) { 46 p1[i] = (1ll * B1 * p1[i-1]) % P1; 47 p2[i] = (1ll * B2 * p2[i-1]) % P2; 48 if (!p[i]) continue; 49 for (int j = 2 * i; j <= n; j += i) { 50 p[j] = false; 51 } 52 } 53 } 54 55 int solve() { 56 for (int i = n; i; --i) { 57 h[i] = H(p[i]); 58 if (2 * i + 1 <= n) { 59 h[i] = h[2 * i] + h[i] + h[2 * i + 1]; 60 } else if (2 * i <= n) { 61 h[i] = h[2 * i] + h[i]; 62 } 63 } 64 cout << h[1].h1 << endl; 65 sort(h + 1, h + n + 1); 66 int m = unique(h + 1, h + n + 1) - (h + 1); 67 return m; 68 } 69 70 int main() { 71 cin >> n; 72 init(); 73 cout << solve() << endl; 74 }
假设程序运行前能自动将 maxn 改为 n + 1，所实现的算法的时间复杂度是 。（ ）
时间开销的瓶颈是 init() 函数。（ ）
若修改常数 B1 或 K1 的值，该程序可能会输出不同的结果。（ ）
在 solve() 函数中，h[] 的合并顺序可以看作是：（ ）
输入 10，输出的第一行是?（ ）
输入 16，输出的第二行是？（ ）
在一个大小为 的哈希表中，使用闭散列法的线性探查来解决冲突。哈希函数为 。依次插入关键字 、、、、、。插入 后，它最终被放置在哪个索引位置？
D：11。H(k)=k mod 13：18→5, 26→0, 35→9, 9→9(冲突)→10, 68→3(空), 74→9(占)→10(占)→11(空)。