一个非空字符串能够具有零的哈希码吗？

Question

在这个问题中，“非空”指的是一个至少包含一个非零字符的字符串。

参考实现 hashCode：

1493    public int hashCode() {
1494        int h = hash;
1495        if (h == 0) {
1496            int off = offset;
1497            char val[] = value;
1498            int len = count;
1499
1500            for (int i = 0; i < len; i++) {
1501                h = 31*h + val[off++];
1502            }
1503            hash = h;
1504        }
1505        return h;
1506    }

算法在文档中有指定。

在发生整数溢出之前，答案很简单：不可能。但我想知道的是，由于整数溢出，非空字符串是否可能具有零的哈希码？你能构造一个吗？

我想要的理想情况是数学证明（或链接）或构造算法。

- Denys Séguret

---

什么是“null hashcode”？类型是int吗？ - Rohit Jain

不确定你所指的“long”是什么。hashCode()方法处理的是整数和字符。 - Taylor

我猜可能是可行的，但找到一个确切的案例会很头疼。 - Rohit Jain

这个问题为什么会被认为是“范围过大”的？ - Denys Séguret

@JoopEggen 请仔细阅读问题直到第一句话... - Denys Séguret

Answer 1

当然。例如，字符串f5a5a608的哈希码为零。

我通过简单的暴力搜索找到了这个结果：

public static void main(String[] args){
    long i = 0;
    loop: while(true){
        String s = Long.toHexString(i);
        if(s.hashCode() == 0){
            System.out.println("Found: '"+s+"'");
            break loop;
        }
        if(i % 1000000==0){
            System.out.println("checked: "+i);              
        }
        i++;
    }       
}

编辑：曾经在JVM上工作的Joseph Darcy甚至编写了一个程序，可以构造具有给定哈希码的字符串（以测试在switch/case语句中字符串实现）基本上通过反向运行哈希算法。

- Michael Borgwardt

---

亲爱的，从激励角度来看，我不会形成瓦片图案的混乱状态。哈希码归零。它们有很多。可以这样想，一个字符串哈希到零的概率大约为2的负64次方。再想想有多少可能的字符串存在。 - Obicere

@Obicere 我并不确定溢出是否能导致零值。 - Denys Séguret

@Obicere：并不是所有的哈希函数都会以相等的概率（或根本不会）使用所有哈希值，尽管当然你会期望一个好的哈希函数这样做。 - Michael Borgwardt

当然，字符越多，分布就越好。当接近无限字符时，它应该接近那个值。此外，随着字符数量的增加，由于字符串排列的指数增益，1或2个字符字符串对结果的影响越小。 - Obicere

我认为unhash函数不能用于此目的。它只能找到由零字符组成的字符串。 - Denys Séguret

Answer 2

请注意 int h; 可能会溢出，满足 h % 2^31 == 0 的每个字符串都可能导致这种情况发生。

public class HelloWorld {
    public static void main(String []args) {
       System.out.println("\u0001!qbygvW".hashCode());
        System.out.println("9 $Ql(0".hashCode());
        System.out.println(" #t(}lrl".hashCode());
        System.out.println(" !!#jbw}a".hashCode());
        System.out.println(" !!#jbw|||".hashCode());
        System.out.println(" !!!!Se|aaJ".hashCode());
        System.out.println(" !!!!\"xurlls".hashCode());
    }
}

很多字符串...

- Manasseh Zhou

Answer 3

以下是查找和打印任何所需hashCode值的代码：

public static int findIntInverse(int x) {
    // find the number y such that as an int (after overflow) x*y = 1
    // assumes x is odd, because without that it isn't possible.
    // works by computing x ** ((2 ** 32) - 1)
    int retval = 1;
    for (int i = 0; i < 31; i++) {
        retval *= retval;
        retval *= x;
    }
    return retval;
}

public static void findStrings(
        int targetHash,
        Iterable<String> firstParts,
        Iterable<String> midParts,
        Iterable<String> lastParts) {
    Map<Integer, String> firstHashes = new HashMap<>();
    for (String firstPart : firstParts) {
        firstHashes.put(firstPart.hashCode(), firstPart);
    }
    int maxlastlen = 0;
    int maxmidlen = 0;
    for (String midPart : midParts) {
        maxmidlen = Math.max(midPart.length(), maxmidlen);
    }
    for (String lastPart : lastParts) {
        maxlastlen = Math.max(lastPart.length(), maxlastlen);
    }
    List<Integer> hashmuls = new ArrayList<>();
    String baseStr = "\u0001";
    for (int i = 0; i <= maxmidlen + maxlastlen; i++) {
        hashmuls.add(baseStr.hashCode());
        baseStr += "\0";
    }
    // now change each hashmuls into its negative "reciprocal"
    for (int i = 0; i < hashmuls.size(); i++) {
        hashmuls.set(i, -findIntInverse(hashmuls.get(i)));
    }
    for (String lastPart : lastParts) {
        for (String midPart : midParts) {
            String tail = midPart + lastPart;
            Integer target = hashmuls.get(tail.length()) * (tail.hashCode() - targetHash);
            if (firstHashes.containsKey(target)) {
                System.out.print(firstHashes.get(target));
                System.out.println(tail);
            }
        }
    }
}

使用常见的英语单词列表来启动每个部分，发现了一些有趣的发现：

sand nearby chair
king concentration feeling
childhood dish tight
war defensive to
ear account virus

使用Arrays.asList(" ")作为midParts，并使用大型英语单词列表作为firstParts和lastParts，我们可以找到众所周知的pollinating sandboxes，以及revolvingly admissable，laccaic dephase，toxity fizzes等。

请注意，如果您向findStrings提供大小为N的大型列表作为firstParts和lastParts，并且提供一个短的固定列表作为midParts，则它将在O(N)时间内运行。

- Daniel Martin