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

134

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

knorv
источник
2
Вам действительно нужна эта функция? Зачем вам точное значение?
Брайан Агнью,
26
@Brian: Я пытаюсь понять контракт String.hashCode ().
knorv
3
@Knorv Нет необходимости точно понимать, как это работает - важнее понимать контракт и его скрытый смысл.
мП
45
@mP: Спасибо за ваш вклад, но я думаю, это решать мне.
knorv
почему они дали первому персонажу наибольшую силу? когда вы хотите оптимизировать его по скорости, чтобы сохранить дополнительные вычисления, вы должны сохранить мощность предыдущего, но предыдущий будет от последнего символа к первому. это означает, что также будут промахи в кэше. не более эффективно иметь алгоритм: s [0] + s [1] * 31 + s [2] * 31 ^ 2 + ... + s [n-1] * 31 ^ [n-1 ]?
разработчик Android

Ответы:

101

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

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

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

Джон Скит
источник
7
Документированное поведение String было определено начиная с Java 1.2. В версии 1.1 API вычисление хэш-кода не указано для класса String.
Мартин ОКоннор,
В этом случае нам лучше написать свои собственные хэш-коды.
Felype
@Felype: Боюсь, я действительно не знаю, что вы пытаетесь здесь сказать.
Джон Скит,
@JonSkeet Я имею в виду, что в этом случае мы, возможно, можем написать наш собственный код для генерации нашего собственного хэша, чтобы обеспечить переносимость. Это?
Felype
@Felype: Совершенно непонятно, о какой переносимости вы говорите, и на самом деле, что вы подразумеваете под словом «в этом случае» - в каком конкретном сценарии? Подозреваю, вам следует задать новый вопрос.
Джон Скит
18

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

RENES
источник
8

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

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

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

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

Мартин Оконнор
источник
1
Ваш ответ действителен, но не касается конкретного заданного вопроса.
Knorv
6
Это общий контракт с хеш-кодом, но конкретный контракт для String дает подробную информацию об алгоритме и эффективно переопределяет этот общий контракт IMO.
Джон Скит,
4

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

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

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

sleske
источник
4
Но был ли алгоритм указан в документации до JDK 1.2? Если нет, то это другая ситуация. Алгоритм теперь изложен в документации, поэтому его изменение было бы критическим изменением публичного контракта.
Джон Скит,
(Я помню его как 1.1.) Исходный (худший) алгоритм был задокументирован. Некорректно. Документированный алгоритм фактически вызвал исключение ArrayIndexOutOfBoundsException.
Том Хотин - tackline
@Jon Skeet: Ах, я не знал, что алгоритм String.hashCode () задокументирован. Конечно, это меняет ситуацию. Обновил мой комментарий.
sleske
3

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

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

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

Брайан Агнью
источник
1
Спасибо за Ваш ответ. Вы можете привести конкретные примеры, когда «Это строка Java» .hashCode ()! = 586653468?
knorv
1
Нет извините. Я хочу сказать, что все, что вы тестируете, может работать так, как вы хотите. Но это все еще не гарантия. Так что, если вы работаете (скажем) над краткосрочным проектом, в котором у вас есть контроль над виртуальной машиной и т. Д., То вышеуказанное может сработать для вас. Но в остальном мире на это нельзя положиться.
Брайан Агнью,
2
«обновление до будущей версии Java может вызвать проблемы». Обновление до будущей версии Java может полностью удалить метод hashCode. Или сделайте так, чтобы он всегда возвращал 0 для строк. Это несовместимые изменения для тебя. Вопрос в том, сочтет ли Sun ^ Horacle ^ H JCP это радикальным изменением, которого стоит избегать. Поскольку алгоритм находится в контракте, можно надеяться, что они будут.
Стив Джессоп,
@SteveJessop хорошо, поскольку switchоператоры над строками компилируются в код, основанный на конкретном фиксированном хеш-коде, изменения в Stringалгоритме хеш-кода определенно нарушат существующий код…
Холгер
3

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

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

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

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

RENES
источник
23
Я думаю, они просто крутятся и оптимизируют его. :) "(multiplier << 5) - multiplier" это всего лишь 31 * множитель, в конце концов ...
раскрутите
Ладно, было лень это проверить. Спасибо!
ReneS
1
Но чтобы было понятно с моей стороны ... Никогда не полагайтесь на хэш-код, потому что хэш-код является чем-то внутренним.
ReneS
1
что означают переменные "смещение", "количество" и "хэш-код"? Я полагаю, что «хэш-код» используется в качестве кешированного значения, чтобы избежать будущих вычислений, и что «count» - это количество символов, но что такое «смещение»? Предположим, я хочу использовать этот код, чтобы он был согласованным, учитывая строку, что мне с ним делать?
разработчик Android
1
@androiddeveloper А теперь ЭТО интересный вопрос - хотя я должен был догадаться об этом, основываясь на вашем имени пользователя. Из документов Android похоже, что контракт такой же: s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]если я не ошибаюсь, это потому, что Android использует реализацию объекта String от Sun без изменений.
Kartik Chugh
2

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

Сэм Барнум
источник
Я собирался сказать это. Хотя другие ответы действительно отвечают на вопрос, написание отдельной функции hashCode, вероятно, является подходящим решением проблемы knorv.
Ник
1

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

Lourdes
источник