# 1. CF 126B 在 KMP 失败函数与哈希的混合工程。 A 只用 KMP 一定无法解决，必须完全依赖哈希 B KMP 失败函数与哈希在此题中功能完全重复 C 哈希在此题中只能判断前缀与后缀相等，无法判断中间出现 D 哈希用于 O(1) 判断任意两段子串是否相等，KMP 用于枚举既是前缀又是后缀的候选长度 ✓ 正确答案
# 2. 双哈希在回文/子串相等判定中的工程实现。 A 双哈希一定比单哈希慢常数倍，工程上应避免使用 B 双哈希的 mod 必须取 2^64 才会正确 C 回文检测只需要正向哈希，不需要反向哈希 D 双哈希用两套独立参数，需两套哈希同时相等才判定相等，碰撞概率降至单模的平方级 ✓ 正确答案
# 3. CF 1200E 在子串哈希的工程实现。 A 必须对每个重叠长度做 O(n) 字符比较，总复杂度 O(n^2) B 滚动哈希无法用于"后缀与前缀匹配"这类问题 C 从大到小枚举重叠长度并用滚动哈希做 O(1) 比较，可在线合并并去重 ✓ 正确答案 D 合并时只需比较第一个字符即可确定重叠
# 4. 字符串哈希的碰撞概率中单模 vs 双模 vs 自然溢出（2^64）在对抗性输入下的安全性差异？ A 自然溢出（2^64）因为模数大，一定比双模更安全 B 单模固定模数在对抗性输入下无法被构造碰撞 C 双模碰撞概率约为单模的平方级，且随机 base 可进一步防御已知构造 ✓ 正确答案 D 碰撞概率与模数大小无关
# 5. Two-way 算法在最长周期与回文前缀的 O(n) 匹配。 A 它需要 O(m) 的额外空间存储失败表，与 KMP 相同 B 它的时间复杂度是 O(n+m) 但空间 O(n) C 它只能判断最长周期，不能用于普通匹配 D 它基于临界分解与周期性质，O(n) 匹配且仅 O(1) 额外空间、常数小 ✓ 正确答案
# 6. Boyer-Moore 在坏字符与好后缀的 O(n/m + m) 摊还工程实现。 A 从右向左匹配，坏字符与好后缀各给移动距离并取较大者，平均可达亚线性 ✓ 正确答案 B 坏字符与好后缀启发式取较小者以保证正确 C 它的最坏情况一定是 O(n) D 它不需要任何预处理表
# 7. Horspool 在简化坏字符表的 O(n) 工程实现。 A 它只用一张坏字符表，依据文本对齐字符决定跳跃，平均 O(n)、预处理 O(m) ✓ 正确答案 B 它同时使用坏字符与好后缀两张表 C 它的最坏情况也是 O(n) D 它从模式开头向右匹配
# 8. Sunday 在 skip 表的 O(n) 工程实现。 A 它依据文本窗口内最后一个字符决定跳跃，与 Horspool 相同 B 它依据窗口后下一个字符决定跳跃，用 skip 表记录最右出现位置，平均 O(n) ✓ 正确答案 C 它的最坏情况是 O(n) D 它不需要预处理
# 9. 单哈希在多项式滚动哈希的 O(n) 预处理与 O(1) 查询。 A 任意子串查询需要 O(n) 时间 B 预处理前缀哈希与幂表后，任意子串哈希可 O(1) 查询 ✓ 正确答案 C 单哈希在任何输入下都不会碰撞 D 子串哈希必须重算整段
# 10. 双哈希在两套 mod 与 base 抗碰撞的工程实现。 A 两套哈希只需其中一套相等即可判定相等 B 两套独立参数需同时相等才判定相等，碰撞概率降至平方级 ✓ 正确答案 C 双哈希比单哈希没有任何安全性提升 D 双哈希的两个 mod 必须相等
# 11. 哈希工程的核心概念中散列函数选择、冲突解决与扩容？ A 扩容时只需移动部分元素，均摊 O(1) B 散列函数越慢越安全，应故意牺牲性能 C 散列函数需均匀快速、冲突解决控制桶长、扩容按负载因子触发并 rehash 全部元素 ✓ 正确答案 D 哈希表扩容会导致所有元素丢失
# 12. 最小完美哈希（MPH，如 CHD/PTHash）在只读大键集合的工程实现中 O(n) 构造、零冲突、~2.5 bits/key 空间 A 它允许碰撞，靠开链解决 B 它必须支持动态插入删除 C 它对静态已知键集合构造无碰撞映射到 0..n-1，O(n) 构造、约 2.5 bits/key 空间 ✓ 正确答案 D 它查找需要 O(log n) 时间
# 13. 哈希与概率数据结构中布隆过滤器的假阳性率与位数组大小/哈希函数数的关系？ A 假阳性率约 (1-e^(-kn/m))^k，最优 k≈(m/n)ln2，位数组越大或元素越少则假阳性越低 ✓ 正确答案 B 哈希函数越多假阳性率越低，可以无限增加 C 布隆过滤器支持删除操作 D 布隆过滤器不会产生假阳性
# 14. 哈希表的拒绝服务攻击中如何利用哈希碰撞制造最坏情况，随机种子/哈希盐如何防御？ A 随机种子/哈希盐使哈希函数运行时不固定，攻击者无法预知碰撞，并可配合红黑树缓解 ✓ 正确答案 B 哈希函数越固定越好，便于攻击者预测 C 只要哈希函数足够快就一定能防 DoS D 增大桶数量即可完全消除碰撞
# 15. 一致性哈希的虚拟节点中负载均衡与最小迁移量的权衡？ A 增删节点需要迁移全部键 B 虚拟节点越多完全没有代价 C 虚拟节点让环上分布更均匀以改善负载均衡，但增加内存与查找开销 ✓ 正确答案 D 一致性哈希不需要虚拟节点也能均匀分布
# 16. 一致性哈希与虚拟节点在缓存分片的工程实现中 Ketama 算法的 160 个虚拟节点 per 物理节点 A 每个物理节点只映射一个虚拟位置 B 每个物理节点映射 160 个虚拟节点到环上，兼顾负载均衡与内存开销 ✓ 正确答案 C 虚拟节点越多一定越好，无任何开销 D Ketama 不支持增删节点
# 17. 正则到 NFA/DFA 的 Thompson 与 Glushkov 构造对比中 Thompson 构造简单但状态多，Glushkov 状态少但构造复杂，状态爆炸控制策略 A Glushkov 构造含有大量 ε 边，状态比 Thompson 多 B DFA 状态数一定不超过 NFA C Thompson 构造简单、状态 O(r) 但含 ε 边；Glushkov 无 ε、状态更紧凑但构造复杂；DFA 子集构造可能状态爆炸 ✓ 正确答案 D 正则引擎永远不需要处理状态爆炸
# 18. PCRE2 JIT 在正则表达式编译的工程实现。 A JIT 编译总是比解释执行慢 B JIT 会改变正则的匹配语义 C JIT 只适用于 DFA 型引擎 D JIT 把回溯型正则的字节码编译成机器码以提升运行速度，但可能失败时回退到解释执行 ✓ 正确答案
# 19. Pollard Rho 预因子化在抗哈希碰撞的工程实现。 A 它用于每次哈希查询时分解键 B 它用于预因子化候选模数，验证其素性或与 base 互素，避免合数模被构造碰撞 ✓ 正确答案 C 它与哈希函数本身完全无关 D 它保证哈希一定无碰撞
# 20. SipHash 在抗 Hash DoS 攻击的工程实现。 A 它是无密钥哈希，输出固定，攻击者仍可预知碰撞 B 它的输出取决于输入长度而不取决于密钥 C 它只用于加密，不适用于哈希表 D 它是带随机密钥的 PRF，攻击者无法预知碰撞，兼顾速度与安全以抗 Hash DoS ✓ 正确答案
# 21. 哈希工程在缓存、布隆过滤器、一致性哈希中的典型应用？ A 一致性哈希不需要任何哈希函数 B 布隆过滤器不需要哈希 C 缓存、布隆过滤器、一致性哈希都只是把键映射到固定空间，但各自对冲突、空间与一致性需求不同 ✓ 正确答案 D 三者对哈希的要求完全相同
# 22. 哈希使用有哪些常见误区（哈希碰撞 DoS、弱哈希函数）？ A 用固定无密钥的弱哈希处理对外输入，且不扩容，是典型误区且易被 DoS 攻击 ✓ 正确答案 B 哈希值可以作为绝对唯一标识，永远不会碰撞 C 加密哈希一定比快速哈希更适合哈希表 D 哈希碰撞与数据量无关
# 23. 滚动哈希在 64-bit 溢出自然模的取舍。 A 因为它无取模，一定比取模更安全 B 它按 2^64 回绕、速度快，但 2^64 是合数，对抗性输入下存在结构弱点，安全场景应改用素数双模 ✓ 正确答案 C 自然溢出永远不会碰撞 D 2^64 是素数，特别安全
# 24. 编译期 hash 模板在 constexpr 编译期哈希函数工程实现。 A 编译期哈希只能在运行时计算，对性能无帮助 B 编译期哈希必须用加密算法 C constexpr 哈希只适用于变量 D 它把字符串字面量的哈希在编译期算好，运行时零开销，适合字符串分派但会略增编译时间 ✓ 正确答案
# 25. Aho-Corasick 多模式匹配自动机与 Hyperscan 多模式引擎的关系中 Hyperscan 在 AC 基础上引入 SIMD 加速、Limex NFA 与 DFA 混合执行 A Hyperscan 在 AC 多模式框架上引入 SIMD、Limex NFA 与 NFA/DFA 混合执行以提升吞吐 ✓ 正确答案 B Hyperscan 完全抛弃 AC，改用纯 DFA C Hyperscan 只能匹配单个模式 D Hyperscan 需要回溯，无法一次扫描
# 26. Hyperscan block/streaming/vectored 三种扫描模式的工程取舍中 block 模式延迟低、streaming 支持跨包匹配、vectored 适合分散缓冲区 A vectored 模式必须把缓冲区拼接成一段 B 三种模式都要求输入是完整连续的一段 C streaming 模式因为要维护跨段状态，能支持跨包匹配但开销更高 ✓ 正确答案 D block 模式支持跨包匹配
# 27. Vectorscan 与 Hyperscan 在流式多模式匹配的工程实现。 A 两者算法完全不同，Vectorscan 不兼容 Hyperscan 语义 B Vectorscan 不支持 streaming 模式 C Vectorscan 是 Hyperscan 的社区分支，流式匹配语义一致，但补充了 ARM 等架构支持与持续维护 ✓ 正确答案 D Hyperscan 仍在持续发布新功能
