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

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

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

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

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

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

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

Источник

7 ответов

Решение

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

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

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

Источник

Я нашел кое-что о 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 вместо хеш-кода, и вы готовы к работе - никаких обсуждений и никаких забот...

Источник

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

Генеральный договор hashCode:

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

РЕДАКТИРОВАТЬ Так как javadoc для String.hashCode() определяет, как вычисляется хеш-код строки, любое нарушение этого будет нарушать спецификацию публичного API.

Источник

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

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

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

Источник

Просто чтобы ответить на ваш вопрос, а не продолжать какие-либо обсуждения. В реализации 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 Harmony

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;
}

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

Источник

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

Суть в том, что я бы не стал полагаться на реализацию hashCode(),

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

Источник

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

Источник

Хеш-код будет рассчитываться на основе значений ASCII символов в строке.

Это реализация в классе String выглядит следующим образом

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        hash = h = isLatin1() ? StringLatin1.hashCode(value)
                              : StringUTF16.hashCode(value);
    }
    return h;
}

Столкновения в хэш-коде неизбежны. Например, строки "Ea" и "FB" дают тот же хеш-код, что и 2236

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