示范代码中的哈希算法和大质数是怎么选取的？

这是一个非常深入且具有实战意义的问题。在 NOI 竞赛中，哈希函数的设计（Hash Function）和模数（Modulo/Prime）的选择直接关系到你的程序是会 “AC” 还是被构造数据 “Hack” 到掉分。

作为教练，我带你从数学本质和竞赛经验两个维度来拆解这个选择逻辑。

一、 哈希算法的设计：寻找“不变量”

雪花问题的特殊性在于：同一片雪花有 12 种表示方式（6种旋转 $\times$ 2种翻转）。 设计的核心原则： 无论雪花如何旋转或翻转，计算出的哈希值 必须完全一致。

1. 为什么选择 Sum (和) 与 XOR (异或)？

在示范代码中，我使用了 (sum + xor_val) % MOD。

• 加法交换律：$a+b+c = c+a+b$。无论从哪个角开始读，6 个数字的和是不变的。
• 异或交换律：$a \oplus b \oplus c = c \oplus a \oplus b$。同理，异或值也不变。
• 为什么要叠加？
  • 只用 Sum：序列 [1, 5, 1, 1, 1, 1] 和 [2, 4, 1, 1, 1, 1] 的和都是 10，会碰撞。
  • 只用 XOR：序列 [1, 2, 3, 1, 2, 3] 的异或值是 0，很多对称序列异或值都是 0，碰撞极高。
  • 组合拳：Sum + XOR 大大降低了不同组合产生相同哈希值的概率。

2. 更高级的思路（进阶提示）

如果你追求更低的碰撞率，可以考虑 多重对称指纹：

• $H = (\sum a_i + \sum a_i^2) \pmod M$ （利用平方和进一步区分数字组合）
• 或者直接将 6 个数排序后做一个标准的字符串哈希（这样就彻底无视了旋转和翻转的顺序）。

二、 大质数的选择：为什么是 999,983？

在草稿纸上，我们要根据数据规模 $N$ 来推算模数。

1. 为什么要用“质数” (Prime)？

哈希表本质是取模运算：$index = key \pmod{MOD}$。

• 如果 $MOD$ 是合数（比如 $100,000$），那么如果你的 $key$ 恰好是 $MOD$ 因数的倍数（比如全是偶数），它们会大量挤在某些特定的位置上，导致“聚集”现象。
• 质数可以最大程度地让哈希值在桶中分布均匀，哪怕你的 $key$ 存在某种等差规律。

2. 为什么选 $1,000,000$ 左右？

• 数据规模 $N = 100,000$。
• 负载因子 (Load Factor)：通常建议哈希表的长度（桶数）是数据量的 5 到 10 倍。
• 如果 $MOD$ 太小（如 $100,007$），平均每个桶会有 1 个元素，冲突概率变大。
• 如果 $MOD$ 选在 $1,000,000$ 左右，每个桶的平均长度只有 $0.1$。这意味着绝大多数时候，你计算出哈希值后，对应的桶是空的或只有一个元素，查询时间接近 $O(1)$。

3. 竞赛常用“明星质数”表

在草稿纸的角落里，建议你记下这几个在 NOI 赛场上经过验证的、碰撞率低的质数：

• 10^5 级别：100003, 1313131 (常用作 Base), 999983
• 10^6 级别：1000003, 19260817 (非常有名的质数)
• 大模数（双哈希用）：10^9+7, 10^9+9, 998244353

三、 启发式图形化思考：哈希碰撞的代价

请在草稿纸上画出这两个场景的比对：

场景 A：垃圾哈希函数 / 模数选太小

Bucket[1]: [雪花A] -> [雪花B] -> [雪花C] -> [雪花D] ... (链表极长)
查找雪花E时：需要跟 A, B, C, D 逐一进行 12 次比对。
性能：接近 O(N^2)，瞬间 TLE。

场景 B：优秀的哈希函数 + 大质数模数

Bucket[1]: [雪花A]
Bucket[2]: (空)
Bucket[3]: [雪花B]
Bucket[4]: [雪花C]
查找雪花E时：计算 H(E)=2，发现 Bucket[2] 是空的，秒出结果。
性能：稳定 O(N)。

四、 读题关键词与底层防御

• 关键词：“可能相同”。这就在暗示你：哈希只是第一步筛选，最后必须通过 is_same 函数进行严格比对。哈希只是为了把“不可能相同”的绝大部分雪花先过滤掉。
• 防御式编程建议： 在 NOI 赛场上，为了防止题目数据故意针对你的哈希函数（即所谓 Hash Killer），你可以采取：
  1. 双哈希：计算两个不同的哈希值，只有当两个值都匹配时才进桶比对。
  2. 随机化：在哈希函数里加入一个随机种子（rand()），让攻击者无法预知你的碰撞点。

总结： 选择 999983 是因为它比 $N$ 大 10 倍左右，且是一个强质数。选择 Sum + XOR 是因为它计算极快且具有旋转不变性。在竞赛中，稳健性比极致的数学美感更重要。