非空字符串的哈希码是否可以为零？

string java hash integer-overflow

2022-09-01 14:16:07

通过“非空”，我的意思是在这个问题上一个字符串，它至少包含一个非零字符。

作为参考，以下是实现：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    }

并且算法在文档中指定。

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

理想情况下，我正在寻找的是数学演示（或指向一个演示的链接）或构造算法。

答案 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语句中字符串的实现）。

答案 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());
    }
}

很多字符串...