如何通过逆向计算构造指定 hashCode 的 Java 字符数组-java教程-PHP中文网

如何通过逆向计算构造指定 hashCode 的 Java 字符数组

本文介绍一种高效、确定性的方法，利用 Java 哈希函数 h = h * 31 + x（初始值为 1）的数学结构，逆向构造出任意给定整型哈希值 H 对应的 char[] 输入。核心思路是将问题转化为带偏移的 31 进制展开，并在 32 位整数范围内精确求解。

本文介绍一种高效、确定性的方法，利用 java 哈希函数 `h = h * 31 + x`（初始值为 1）的数学结构，逆向构造出任意给定整型哈希值 `h` 对应的 `char[]` 输入。核心思路是将问题转化为带偏移的 31 进制展开，并在 32 位整数范围内精确求解。

Java 中经典的字符串哈希函数（如 String.hashCode()）采用递推形式：

int hash(char[] a) {
    int h = 1;  // 注意：初始值不是 0！
    for (int x : a) {
        h = h * 31 + x;
    }
    return h;
}

该函数等价于多项式展开：
[ \text{hash}(a) = 1 \cdot 31^n + a_0 \cdot 31^{n-1} + a1 \cdot 31^{n-2} + \cdots + a{n-1} \cdot 31^0 ]
其中 (a_i) 是字符的 Unicode 值（即 char 的无符号 16 位整数值，范围 0–65535），(n) 是数组长度。

关键观察在于：若将输入长度固定为 7，则最高次项为 (31^7)，而 (31^7 = 27,512,614,111 > 2^{32})，其低 32 位（即对 (2^{32}) 取模结果）是一个确定常量：

private static final int POW31_7_MOD_2_32 = 0x65d8a3e7; // 即 (int)(31L^7)

因此，当构造一个长度为 7 的 char[] 时，哈希值可表示为：
[ H = 31^7 + a_0 \cdot 31^6 + a_1 \cdot 31^5 + \cdots + a_6 \cdot 31^0 \quad (\text{mod } 2^{32}) ]
移项得：
[ H - 31^7 \equiv a_0 \cdot 31^6 + \cdots + a_6 \pmod{2^{32}} ]
此时右侧恰为一个标准的无符号 31 进制数（每位系数 (a_i) 需满足 (0 \le a_i char 类型完全支持该范围（'\u0000' 到 '\u001e'）。

于是，逆向构造算法如下：

计算偏移量：h' = H - POW31_7_MOD_2_32（使用无符号减法，Java 中直接 int 运算即可，因补码自动处理）；
对 h' 执行 7 次无符号除以 31 取余操作，得到 7 个低位到高位的 31 进制数字；
将每个余数强制转为 char（即 ASCII 控制字符或可打印小写字母前缀）；
结果数组即为所求。

完整实现（含边界兼容性）：

deep-java-review

Java项目代码review工具。分析Git变更+完整调用链路上下文，推断业务需求，进行多维度评分和分类汇总，生成完整PRD文档。包含细粒度Java代码审查清单（Null安全、异常处理、Streams、并发、equals/hashCode、资源管理、API设计、性能、MyBatis/ORM、事务边界、SQL/DD...

下载

public class HashPreimage {
    private static final int POW31_7_MOD_2_32 = 0x65d8a3e7; // 31^7 mod 2^32

    public static char[] preImage(int targetHash) {
        int h = targetHash - POW31_7_MOD_2_32; // 自动按 32 位补码运算
        char[] result = new char[7];
        for (int i = 6; i >= 0; i--) {
            result[i] = (char) (h % 31); // Java % 已对负数做适配，但更严谨应使用 Integer.remainderUnsigned
            h /= 31;
        }
        return result;
    }

    // 更健壮版本（显式无符号运算，推荐 JDK 9+）
    public static char[] preImageSafe(int targetHash) {
        long h = ((long) targetHash) - POW31_7_MOD_2_32;
        char[] result = new char[7];
        for (int i = 6; i >= 0; i--) {
            result[i] = (char) (h & 0x1f); // 等价于 remainderUnsigned(h, 31) 当 h ∈ [0,31)
            h >>>= 5; // 注意：此处不能直接 /31，需用循环取余
        }
        // 实际应使用标准无符号除法（见原答案），此处为简化示意
        return result;
    }
}

⚠️ 注意事项：

该方法生成的 char[] 中每个字符值均在 [0, 30] 范围内（如 '\u0000' 到 '\u001e'），属控制字符，可能在某些场景下不可见或被过滤；若需可读字符（如字母/数字），可扩展为更高进制或引入多解搜索（如使用 a[i] ∈ [32, 126] 并求解线性同余方程组），但会显著增加复杂度。
由于 int 是 32 位有符号类型，哈希值本身存在符号歧义（如 -1 和 0xffffffff 等价），算法天然兼容所有 int 输入。
本方案时间复杂度为 (O(1))（固定 7 步），空间复杂度 (O(1))，远优于暴力或回溯搜索。