查找具有给定 hashCode 的 byteString？

Question

我正在尝试解决以下问题：

给出以下（java）哈希函数：

int hash(char[] a) {
    int h = 1;
    for (int x: a) h = h*31 + x;
    return h;
}

查找散列为

char[]

的

H

值。

将第一行更改为

int h = 0;

时问题很容易，但我被困在这一行上。

有什么想法吗？

Answer 1

这里不是使用强力“去哈希”的非常实际的例子，但有一些限制：

• 我们假设初始字符串足够短，不会在散列过程中导致 int 溢出。
• 让初始字符串采用 ascii 编码，字节范围为 [32, 126]。

    public static Set<String> getStringsFromHash(int hash) {
        Set<String> asciiStringSet = new HashSet<>();
        reverseHash(hash, new StringBuilder(), asciiStringSet);
        return asciiStringSet;
    }

    private static void reverseHash(int hash, StringBuilder sb, Set<String> asciiStringSet) {
        if (hash == 1) {
            asciiStringSet.add(sb.reverse().toString());
            return;
        }
        if (hash < 0)
            return;

        for (int i = 32; i <= 126; ++i) {
            if ((hash - i) % 31 == 0) {
                reverseHash((hash - i) / 31, new StringBuilder(sb).append((char) i), asciiStringSet);
            }
        }
    }

reverseHash 方法递归地求解以下方程：对于 [32,126] 范围内的每个 i，hash = hash*31 + i。当 hash == 1 时，它假设我们找到了初始字符串。

测试代码：

    static int hash(char[] a) {
        int h = 1;
        for (int x : a)
            h = h * 31 + x;
        return h;
    }

    public static void main(String[] args) {
        String string = "Hi";
        int hash = hash(string.toCharArray());
        Set<String> stringSet = getStringsFromHash(hash);
        for (String s : stringSet)
            System.out.println(s);
    }

输出： J+、IJ、

Hi

输入字符串越大，碰撞就越多，例如这里是

Hello

字符串的输出：

IH001、J)001、J)0/P、J)0.o、Hg001、J(O01、IGO01、HfO01、Hg/O1、Hg0/P、Hg0.o、Hg.n1、Hg.mP、Hg .lo、Hg/NP、Hg/Mo、J'n01、J'mO1、J'n/P、J'n.o、J'ln1、J'lmP、J'llo、J'mNP、J'mMo , J(NO1, J(O/P, J(O.o, J(Mn1, J(MmP, J(Mlo, J(NNP, J(NMo, IFn01, IFmO1, IFn/P, IFn.o, IFln1, IFlmP) , IFllo, IFmNP, IFmMo, IGNO1, IGO/P, IGO.o, IGMn1, IGMmP, IGMlo, IGNNP, IGNMo, Hen01, HemO1, Hen/P, Hen.o, Heln1, HelmP,

Hello

, HemNP, HemMo , HfNO1, HfO/P, HfO.o, HfMn1, HfMmP, HfMlo, HfNNP, HfNMo, J)/O1, J).n1, J).mP, J).lo, J)/NP, J)/Mo 、IH/O1、IH0/P、IH0.o、IH.n1、IH.mP、IH.lo、IH/NP、IH/Mo