核心概述
“Codeforces 哈希”指在评测环境中强调常数、小内存与鲁棒性的字符串滚动哈希实践取舍，围绕参数选取与实现细节以获得稳定、高效的子串指纹比较能力。
原文引述
KACTL algorithms should be: useful, short, fast enough, well tested, and if relevant, readable and easy to modify. They should not be overly generic, since code is manually typed and that just adds overhead. ——摘自 kactl/README.md
展开阐述
-
定义与背景
- 面向在线判题（如 Codeforces）等评测环境，字符串哈希在确保高效的同时，需关注参数与实现细节避免被针对性数据“卡常”或构造碰撞。
- 本节点延续 119-字符串-字符串哈希 的通用语义，强调工程化细节；在容器层面可参考 005-数据结构-哈希表 的“更强位扩散与随机扰动”的思路。
-
接口与输入输出语义（按仓库约定）
- 典型接口（据约定风格）：
- build(s)：预处理生成前缀指纹与幂表（或等效状态）。
- get(l, r)：O(1) 返回 [l, r) 子串指纹；若采用双模/双通道，可返回 pair。
- 等价判断：hash1 == hash2 即判断等价（概率意义）。
- 语义
- 返回的指纹仅作高概率等价判定；关键路径可结合长度/下标做二次确认。
- 典型接口（据约定风格）：
-
核心流程与关键要点（工程取舍）
- 参数与混合
- 基数/模数/位宽的选择应兼顾常数与碰撞风险；在不引入仓库外实现细节的前提下，建议沿用“强位扩散+扰动”的思想（参见 005-数据结构-哈希表 中对 chash 的描述）。
- 若实现支持“双通道”（如两套参数/两套位混合），可进一步降低碰撞几率。
- 预处理与查询
- 预处理 O(n)，查询 O(1)；注意归一化处理，避免符号或溢出导致误判。
- 支持 concat 等组合操作时，注意长度维度的幂次同步与边界一致性。
- 端到端鲁棒性
- 数据规模大时，建议采用多通道/扰动种子；对重复模式与周期串，关注退化情形的指纹分布。
- 与容器结合：在集合判重、映射统计时，容器可选用 005-数据结构-哈希表，利用其位扩散与随机扰动策略。
- 参数与混合
-
复杂度与边界条件
- 时间：build O(n)，get O(1)；空间：O(n) 前缀与幂表。
- 边界：空串/空区间；字符集映射的稳定性；不同实现之间参数差异导致的不可比性（跨组件传递时需统一）。
-
与相邻技术的取舍对比
- 与 118-字符串-AC自动机：多模式匹配的最坏线性保证适用于大量模式的场景；哈希更适用于子串等价快速判定与集合判重。
- 与 119-字符串-字符串哈希：本节点强调评测环境下的工程细节与鲁棒实现取舍，二者可结合使用。