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

Question

Значение 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 () совершенно не имеет значения в контексте этого вопроса.

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

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

Генеральный контракт hashCode:

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

EDIT Поскольку javadoc для String.hashCode () определяет способ вычисления хеш-кода String, любое нарушение этого может привести к нарушению спецификации общедоступного API.

Answer 4

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

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

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

Answer 5

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

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

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

Answer 6

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

Answer 7

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

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