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

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

Для справки, вот 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    }

и алгоритм указан в документации.

Прежде чем произойдет целочисленное переполнение, ответ прост: нет. Но что я хотел бы знать, так это то, что из-за переполнения целых чисел непустая строка может иметь нулевой хеш-код? Вы можете построить один?

То, что я ищу, в идеале - математическая демонстрация (или ссылка на нее) или алгоритм построения.

Источник

3 ответа

Решение

Конечно. Например, строка 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), в основном выполняя алгоритм хеширования в обратном порядке.

Источник

Просто позаботься об этом 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());
    }
}

Много строк...

Источник

Вот код для поиска и печати любых желаемых строк. 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(" ") как и большой список английских слов для и, мы находим хорошо известные pollinating sandboxes а также revolvingly admissable, laccaic dephase, toxity fizzes, так далее.

Обратите внимание, что если вы дадите findStringsбольшой список размера N для обоих firstParts а также lastParts и краткий фиксированный список для midParts, он выполняется за время O(N) .

Источник
Другие вопросы по тегам