Может ли непустая строка иметь хэш-код нуля?

Под "непустым" подразумевается в этом вопросе строка, содержащая хотя бы один ненулевой символ.

Для справки, здесь реализация 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, даже написал программу, которая может построить строку с заданным хэш-кодом (до протестировать реализацию строк в операторах switch/case), в основном управляя алгоритмом хеширования в обратном порядке.