Согласованность хэш-кода() в строке Java

StackOverflow https://stackoverflow.com/questions/785091

  •  16-09-2019
  •  | 
  •  

Вопрос

Значение хэш- кода строки Java вычисляется как (Строка.Хэш-код()):

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

Это было полезно?

Решение

Я вижу эту документацию еще в 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-го символа.Это довольно хорошо гарантировало, что у вас будет много строк, хэширующих одно и то же значение, что замедляет поиск в хэш-таблице .В JDK 1.2 функция была улучшена, чтобы умножать результат пока на 31, затем добавить следующий символ в последовательности.Это немного медленнее, но намного лучше позволяет избегать столкновений.Источник: http://mindprod.com/jgloss/hashcode.html

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

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

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

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

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

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

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

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

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

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

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

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

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

Солнце 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;
}

Апач Гармония

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

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

Хэш-код будет рассчитываться на основе значений 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.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top