如何找到对应指定哈希值H的char[]？基于给定Java哈希函数

针对这个初始值为h=1的哈希函数，我们可以通过两种核心思路构造目标char数组：

1. 逆向推导法 #

从目标哈希值H出发，反向拆解每一步的计算过程，逐步推出每个字符：

• 核心逻辑：原哈希过程是 h = h_prev *31 + x，逆向则是 x = H - h_prev*31，且x必须是合法char（0≤x≤65535），h_prev是前一步的哈希结果（最终要回到初始值1）。
• 步骤：
  • 对当前目标值H，计算x ≡ H mod31。若结果为负数（Java取模特性），则加上31的倍数调整到0-65535范围内。
  • 计算前一步哈希值h_prev = (H - x)/31（利用Java int的补码溢出特性做整数除法）。
  • 将x加入结果数组的开头（逆向推导，最后一个字符先确定）。
  • 重复上述步骤，直到h_prev等于1（对应空数组的哈希值），此时结果数组即为所求。
  • 若过程中出现循环，选择更大的x（如x = H mod31 +31*k，k取较大值）打破循环，由于int的取值有限，最终总能找到h_prev=1的情况。

2. 转化为初始h=0的已知问题 #

利用哈希函数的数学关联，将问题转化为你已掌握的初始值h=0的场景：

• 等价关系：原函数的hash(a)，完全等价于初始h=0的哈希函数计算数组[(char)1] + a的结果（即hash(a) = hash0(new char[]{(char)1} + a)，其中hash0是初始h=0的版本）。
• 解法：
  • 用你已掌握的方法找到任意数组c，使得hash0(c)=H。
  • 若c的第一个元素是(char)1，则去掉第一个元素即为所求的a；若不是，则调整构造逻辑：直接推导数组d使得hash(d)=H，等价于构造hash0([(char)1]+d)=H，反向拆解得到d。

关键注意点 #

Java的int是32位有符号补码，所有计算（包括溢出、除法）都遵循补码规则，逆向推导时需严格按照该规则处理数值。

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