Почему неизменяемые объекты в хэшмапах настолько эффективны?

Ответ 1

String#hashCode:

private int hash;

...

public int hashCode() {
    int h = hash;
    if (h == 0 && count > 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;
}

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

Ответ 2

Цитирование связанной записи в блоге:

конечный объект с правильной реализацией equals() и hashcode() будет выступать в качестве совершенных ключей Java HashMap и повысить производительность Java hashMap за счет уменьшения столкновения.

Я не вижу, как оба final и equals() имеют какое-либо отношение к хеш-коллизиям. Это предложение вызывает мое подозрение в достоверности статьи. Кажется, это коллекция догматических Java "wisdoms".

Неизменность также позволяет кэшировать hashcode из разных ключей, что делает процесс полного извлечения очень быстрым и предполагает, что String и различные классы-оболочки, например Integer, предоставленный API Java Collection, являются очень хорошими ключами HashMap.

Я вижу две возможные интерпретации этого предложения, оба из которых неверны:

• HashMap кэширует хэш-коды неизменяемых объектов. Это неверно. На карте нет возможности узнать, является ли объект "неизменным".
• Обязательность обязательна для того, чтобы объект кэшировал собственный хэш-код. В идеале, значение хеш-объекта должно всегда полагаться на не мутирующее состояние объекта, иначе объект не может быть разумно использован в качестве ключа. Таким образом, и в этом случае автор не может указать: если мы предположим, что наш объект не меняет свое состояние, нам также не нужно каждый раз пересчитывать значение хэша, даже если наш объект изменен!

Пример

Итак, если мы действительно сумасшедшие и на самом деле решили использовать List как ключ для HashMap и сделать значение хэша зависимым от содержимого, а не личность списка, мы могли бы просто принять решение о недействительности кешированное значение хэша при каждой модификации, тем самым ограничивая количество вычислений хэшей числом изменений в списке.

Ответ 3

Это очень просто. Поскольку неизменяемый объект не изменяется с течением времени, ему нужно только выполнить вычисление хэш-кода один раз. Вычисление его снова даст такое же значение. Поэтому обычно вычисляется хэш-код в конструкторе (или лениво) и сохраняется в поле. Функция hashcode возвращает только значение поля, которое действительно очень быстро.

Ответ 4

В Java практически неизменяемость достигается тем, что класс не расширяется, и все операции в объекте идеально не изменят состояние объекта. Если вы видите операции String как replace(), это не изменяет состояние текущего объекта, с которым вы манипулируете, а дает новый объект String с замененной строкой. Поэтому в идеале, если вы сохраняете такие объекты как ключи, состояние не изменяется и, следовательно, хеш-код также остается неизменным. Таким образом, кэширование хеш-кода будет эффективным во время поиска.

Ответ 5

Подумайте о хэшмапе как большом массиве пронумерованных ящиков. Число - это хэш-код, и ящики упорядочены по числу.

Теперь, если объект не может измениться, хеш-функция всегда будет воспроизводить одно и то же значение. Поэтому объект всегда останется в нем.

Теперь предположим переменный объект. Он изменяется после добавления его в хеш, так что теперь он сидит в неправильной коробке, как миссис Джонс, которая случайно вышла замуж за мистера Доу и которая теперь также называется Доу, но во многих регистрах по-прежнему называется Джонс.

Ответ 6

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

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

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

Если хэш-таблицы Java позволили клиентам поставлять EqualityComparer (как это делают словари .NET), код, который знает, что некоторые аспекты объектов в хеш-таблице не будут неожиданно меняться, может использовать хэш-код, который учитывал эти аспекты учетной записи, но единственный способ добиться этого в Java - это обернуть каждый элемент, хранящийся в хэш-коде, в обертку. Однако такая упаковка не может быть самой злой в мире, поскольку оболочка сможет кэшировать хеш-значения таким образом, который не мог бы EqualityComparer, и мог также кэшировать дополнительную информацию, связанную с равенством (например, если хранимые вещи являются вложенными коллекциями, может быть полезно вычислить несколько хеш-кодов и подтвердить, что все хэш-коды совпадают, прежде чем выполнять детальный осмотр элементов].