数值哈希构造与空间映射

📖 算法原理：除留余数法与负数模处理

哈希（Hash，散列）是一种空间压缩映射。它通过散列函数把一个庞大的数域（如 32 位带符号整型）压缩映射到一个较小的紧凑数组区间 $[0, M-1]$ 中，实现稳定 $O(1)$ 复杂度的插入与检索。

📐 经典数值模哈希公式与负数修正断言

最主流的散列函数设计是除留余数法（Division Method）。对于任意整数键值 $key$，设哈希表大小为 $M$：

$H(key) = key \bmod M$

⚠️ 考点：C++ 负数取模修正 在 C++ 中，对于负数执行 % 取模时，结果仍为负数（如 -5 % 3 == -2）。因为哈希表索引必须是非负整数，所以必须通过以下数学变形保证结果稳定映射在 $[0, M-1]$ 区间内：

$H_{safe}(key) = (key \bmod M + M) \bmod M$

💡 模数 $M$ 的选取法则：模数 $M$ 建议选取为与 $2^p$ 尽量远的质数（Primes）。若 $M$ 为合数（如 10），其约数容易导致哈希散列极度偏向特定桶槽，极易引发哈希碰撞冲突！

输入整数 Key：

模数 M (除数)：

在上方输入一个正整数或负整数并点击"哈希插入"，观察它如何通过过滤器落入对应索引槽。

🌪️ 除留余数物理过滤器机器 (Residual Mod Filter Machine)

const int M = 7; // 哈希表大小(选择质数)
int hashTable[M];
bool occupied[M];

// 安全数值哈希映射函数(防负数溢出)
int getHash(int key) {
    return (key % M + M) % M; 
}

void insert(int key) {
    int idx = getHash(key);
    hashTable[idx] = key;
    occupied[idx] = true; // 槽位被占用
}

📋 空间哈希物理映射历史