Согласованность hashCode() в строке Java

Значение hashCode строки Java вычисляется как (String.hashCode()):

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

Существуют ли какие-либо обстоятельства (например, версия JVM, поставщик и т.д.), под которым следующее выражение будет оцениваться как false?

boolean expression = "This is a Java string".hashCode() == 586653468

Обновление # 1: Если вы утверждаете, что ответ "да, есть такие обстоятельства", то, пожалуйста, дайте конкретный пример того, когда "Это строка Java".hashCode()!= 586653468. Постарайтесь как можно более конкретным/конкретным.

Обновление # 2: Мы все знаем, что, опираясь на подробности реализации hashCode(), в общем случае плохо. Тем не менее, я говорю конкретно о String.hashCode() - поэтому, пожалуйста, держите ответ на String.hashCode(). Object.hashCode() совершенно не имеет отношения к контексту этого вопроса.

4b9b3361

Я вижу эту документацию еще в Java 1.2.

Хотя верно, что в целом вы не должны полагаться на реализацию хеш-кода, оставаясь тем же самым, теперь он документировал поведение для java.lang.String, поэтому его изменение будет считаться нарушением существующих контрактов.

По возможности, вы не должны полагаться на хеш-коды, оставаясь одинаковыми в разных версиях и т.д., но, на мой взгляд, java.lang.String - это особый случай просто потому, что алгоритм указан... пока вы готовы отказаться от совместимости с релизами до того, как был определен алгоритм.

83
ответ дан 24 апр. '09 в 12:25
источник

Я нашел что-то о JDK 1.0 и 1.1 и >= 1.2:

В JDK 1.0.x и 1.1.x hashCode функция для длинных строк, обработанных выборка каждого n-го символа. Эта довольно хорошо, что у вас будет многие строки хеширования к тому же значение, таким образом замедляя Hashtable Погляди. В JDK 1.2 функция имеет были улучшены, чтобы умножить результат пока 31, затем добавьте следующий символ в последовательности. Это немного медленнее, но намного лучше избегая столкновений. Источник: http://mindprod.com/jgloss/hashcode.html

Что-то другое, потому что вам, похоже, нужен номер: как насчет использования CRC32 или MD5 вместо хэш-кода, и вам хорошо идти - никаких обсуждений и вообще не беспокоиться...

18
ответ дан 24 апр. '09 в 15:17
источник

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

Общий контракт hashCode:

  • Всякий раз, когда он вызывается одним и тем же объектом более одного раза во время выполнения приложения Java, метод hashCode должен последовательно возвращать одно и то же целое число, если информация, используемая при равных сравнениях с объектом, не изменяется. Это целое число не должно оставаться согласованным с одним исполнением приложения на другое выполнение того же приложения.

ИЗМЕНИТЬ Поскольку javadoc для String.hashCode() указывает, как вычисляется хэш-код String, любое нарушение этого может нарушить публичную спецификацию API.

9
ответ дан 24 апр. '09 в 12:16
источник

Как было сказано выше, в общем случае вы не должны полагаться на хэш-код класса, который остается тем же. Обратите внимание, что даже последующие прогоны одного и того же приложения на одной виртуальной машине могут создавать разные значения хеширования. Функция AFAIK the Sun JVM вычисляет один и тот же хэш на каждом прогоне, но это не гарантируется.

Обратите внимание, что это не теоретическое. Хэш-функция для java.lang.String была изменена в JDK1.2 (у старого хэша были проблемы с иерархическими строками, такими как URL-адреса или имена файлов, поскольку он имел тенденцию создавать тот же хеш для строк, которые только отличались в конце).

java.lang.String - частный случай, так как алгоритм его hashCode() (сейчас) задокументирован, поэтому вы, вероятно, можете положиться на это. Я все равно считаю это плохой практикой. Если вам нужен хеш-алгоритм со специальными документальными свойствами, просто напишите: -).

4
ответ дан 24 апр. '09 в 12:23
источник

Еще одна проблема (!), о которой стоит беспокоиться, - это возможное изменение реализации ранних/поздних версий Java. Я не верю, что детали реализации заданы в камне, поэтому потенциально обновление до будущей версии Java может вызвать проблемы.

В нижней строке, я бы не полагался на реализацию hashCode().

Возможно, вы можете указать, какую проблему вы пытаетесь решить, используя этот механизм, и это подчеркнет более подходящий подход.

3
ответ дан 24 апр. '09 в 12:16
источник

Просто, чтобы ответить на ваш вопрос и не продолжать никаких обсуждений. Реализация Apache Harmony JDK, похоже, использует другой алгоритм, по крайней мере, он выглядит совершенно иначе:

Sun JDK

public int hashCode() {
    int h = hash;
    if (h == 0) {
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

Гармония Apache

public int hashCode() {
    if (hashCode == 0) {
        int hash = 0, multiplier = 1;
        for (int i = offset + count - 1; i >= offset; i--) {
            hash += value[i] * multiplier;
            int shifted = multiplier << 5;
            multiplier = shifted - multiplier;
        }
        hashCode = hash;
    }
    return hashCode;
}

Не стесняйтесь проверить это самостоятельно...

3
ответ дан 24 апр. '09 в 14:21
источник

Если вас беспокоят изменения и, возможно, несовместимые виртуальные машины, просто скопируйте существующую реализацию hashcode в свой собственный класс утилиты и используйте это для генерации ваших хэш-кодов.

2
ответ дан 24 апр. '09 в 18:27
источник