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

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

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

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

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

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


java string hash integer-overflow
person Denys Séguret    schedule 11.09.2013    source источник
comment
Что вы подразумеваете под нулевым хэш-кодом? Тип int?   -  person Rohit Jain    schedule 11.09.2013
comment
@RohitJain Черт, мой английский меня подводит (по-французски nul означает ноль). Отредактировано.   -  person Denys Séguret    schedule 11.09.2013
comment
также не уверен, что долго вы имеете в виду. Метод hashCode() имеет дело с целыми числами и символами.   -  person Taylor    schedule 11.09.2013
comment
Я думаю, это возможно. но найти точный случай будет головной болью.   -  person Rohit Jain    schedule 11.09.2013
comment
Да, это возможно, но крайне маловероятно.   -  person Hovercraft Full Of Eels    schedule 11.09.2013
comment
вполне допустимо иметь хэш-код равным нулю, поскольку он не нарушает никаких правил хеш-кода.   -  person ankit    schedule 11.09.2013
comment
@ankit Класс String имеет дополнительную спецификацию (см. javadoc).   -  person Denys Séguret    schedule 11.09.2013
comment
Как этот вопрос может быть слишком широким?   -  person Denys Séguret    schedule 11.09.2013
comment
@dystroy вопрос значительно изменился с тех пор, как вы его задали, и теперь вы ищете математическую демонстрацию.   -  person Taylor    schedule 11.09.2013
comment
@JoopEggen Пожалуйста, прочитайте вопрос до первого предложения...   -  person Denys Séguret    schedule 11.09.2013
comment
Это напоминает мне о том, как некоторые сотрудники Google пытались найти String с Integer.MIN_VALUE в качестве хэш-кода для какой-то Java-головоломки.   -  person Dennis Meng    schedule 11.09.2013
comment
Почему тебе не все равно? Ваш код никогда не должен предполагать, что коллизии хешей невозможны.   -  person Raedwald    schedule 11.09.2013
comment
@Raedwald Для начала мне было любопытно предположить, что стоит за реализацией хеш-кэша. А дальше мне стало интересно. Я не научился программировать, не будучи любопытным.   -  person Denys Séguret    schedule 11.09.2013

Ответы (2)


arrow_upward
40
arrow_downward

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

person Michael Borgwardt    schedule 11.09.2013
comment
Incentively, my dear, I don't tessellate a derangement. Хэш-коды равны нулю. Их очень много. Подумайте об этом так: у вас есть примерно 2 ^ -64 шанса, что String будет хеширован до нуля. Затем подумайте, сколько существует возможных строк. - person Obicere; 11.09.2013
comment
@Obicere Я совсем не был уверен, что переполнение может привести к нулевому значению. - person Denys Séguret; 11.09.2013
comment
@Obicere: не обязательно верно, что хэш-функция будет использовать все хэш-значения с равной вероятностью (или вообще), хотя, конечно, вы ожидаете этого от хорошей хеш-функции. - person Michael Borgwardt; 11.09.2013
comment
@MichaelBorgwardt Конечно, но чем больше символов, тем лучше распределение. При приближении к бесконечным символам оно должно приближаться к этому значению. Кроме того, чем больше символов, тем меньше значимость строк из 1 или 2 символов влияет на результаты из-за экспоненциального усиления перестановок строк. - person Obicere; 11.09.2013
comment
Я не думаю, что функция unhash может работать для этой цели. Он найдет только строку, состоящую из нулевых символов. - person Denys Séguret; 11.09.2013
comment
@Obicere: я думал об искаженной хеш-функции, а не о вводе. О, и хэш-код - это целое число, так что это шанс 1 из 2 ^ 32. В противном случае мой подход грубой силы был бы довольно бесполезным. - person Michael Borgwardt; 12.09.2013
comment
@MichaelBorgwardt ах да, спасибо за исправление. Понятия не имею, почему я подумал, что это 64, ха-ха - person Obicere; 12.09.2013

arrow_upward
1
arrow_downward

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

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

person Manasseh Zhou    schedule 27.04.2018