刻意构造哈希碰撞：满足特定条件的简易哈希算法需求问询

要满足的三个关键约束 #

• 对于任意十位数整数n（比如1234567890），n的哈希值必须和它所有左对齐子串（像1、123、12345这类）的哈希值完全一致
• 子串"1"的哈希映射方式不能只有一种，得规避信息守恒定律的问题
• 非左对齐子串的字符串（比如和123仅末位不同的1235），和目标串/其子串哈希值撞车的概率要能调，而且必须存在撞不上的可能；另外随着这类字符串的位数变长，撞车概率要趋近于0

你提出的素数乘积方案分析 #

你提到的思路是给每个子串分配唯一素数，再把这些素数相乘得到哈希值：

比如n=123，子串是{1,12,123}，分别对应素数2、37、677，乘积是50098。这样所有目标子串对应的素数都是这个哈希值的因数，非目标串（比如13、124）对应的素数则不是，以此保证约束。

这个方案确实能满足所有要求，但算不上最优——最大的问题是哈希值会爆炸式增长：十位数的n有10个子串，最大的子串是十位数，对应的素数本身就很大，乘积结果会远远超过原数的量级，不管是存储还是计算都很不划算。

关于你的两个疑问 #

1. 素数乘积方案是不是最优解？ #

不是。它只是一种直观的实现，但效率很低。我们可以设计更紧凑的方案，比如模运算分层映射：

• 先选一个足够大的质数P，把任意数字串转成整数后取模P，得到初始哈希值
• 定义规则：如果字符串s是t的左对齐子串，那么hash(s) = hash(t) mod K，其中K是P的一个因数（可根据需求调整）
• 为了满足"1"的多映射要求，给"1"额外设置2-3个备用哈希值，当输入的"1"不是某个更长左对齐子串的一部分时，随机选一个备用值输出

这个方案的哈希值范围可以控制在[0, P)，完全不需要比原数大，同时满足所有约束：

• 左对齐子串通过模运算保证哈希值一致
• "1"有多个可选哈希值，规避信息守恒问题
• 调整P和K的大小就能控制碰撞概率，而且随着非目标串位数增加，碰撞概率会因为模运算的离散性自然趋近于0

另外还有个更轻量的思路：前缀特征哈希

• 生成哈希时，先提取字符串的所有左对齐前缀的特征（比如前缀长度+末尾数字的组合），再对这个特征集合做哈希
• 左对齐子串的特征集合共享核心前缀，所以哈希值相同；非目标串的特征集合和目标串差异会随着位数增加越来越大，碰撞概率趋近于0

2. 必须用比n大得多的哈希值吗？ #

完全不需要。上面提到的两种方案，哈希值的大小都可以控制在和原数相当甚至更小的范围，只要选合适的模值或者特征编码方式就行。

内容的提问来源于stack exchange，提问作者EternalPropagation