Хеширование ключей в Java

Question

В Java, когда я использую String в качестве ключа для Hashmap, я получаю немного другой результат, чем когда я использую хеш-код строки в качестве ключа в HashMap.

Любое понимание?

Answer 1

когда я использую строку хэш-кода в качестве ключа в HashMap.

Вы не должны использовать сам хэш-код в качестве ключа. Хеш-коды не предназначены для того, чтобы быть уникальными - вполне допустимо, чтобы два неравных значения имели одинаковый хеш-код. Вы должны использовать саму строку в качестве ключа. Затем карта сначала сравнивает хеш-коды (чтобы быстро сузить совпадения кандидатов), а затем сравнивает с equals для подлинного равенства строк.

Конечно, это предполагает, что ваш код действительно такой, каким его задает вопрос, например

HashMap<String, String> goodMap = new HashMap<String, String>();
goodMap.put("foo", "bar");

HashMap<Integer, String> badMap = new HashMap<Integer, String>();
badMap.put("foo".hashCode(), "bar");

Если это действительно так, как выглядит ваш код, просто используйте HashMap<String, String> вместо.

Из документов для Object.hashCode() (выделение мое):

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

• Всякий раз, когда он вызывается для одного и того же объекта более одного раза во время выполнения приложения Java, метод hashCode должен последовательно возвращать одно и то же целое число при условии, что никакая информация, используемая в сравнениях сравнения для объекта, не изменяется. Это целое число не должно оставаться согласованным от одного выполнения приложения к другому выполнению того же приложения.
• Если два объекта равны в соответствии с методом equals(Object), то вызов метода hashCode для каждого из двух объектов должен привести к одному и тому же целочисленному результату.
• Не требуется, чтобы, если два объекта были неравны в соответствии с методом equals(java.lang.Object), то вызов метода hashCode для каждого из двух объектов должен приводить к разным целочисленным результатам. Тем не менее, программист должен знать, что выдача различных целочисленных результатов для неравных объектов может улучшить производительность хеш-таблиц.

Answer 2

Проблема в том, что даже если два объекта различны, это не означает, что их хеш-коды также различны.

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

Кроме того, потому что хэш-коды возвращаются из Object.hashCode() метод имеет тип int, вы можете иметь только 2^32 разные значения. Вот почему у вас будут "коллизии" в зависимости от алгоритма хеширования для разных объектов.

Короче: -

!obj.equals(obj1) не гарантирует, что obj.hashCode() != obj1.hashCode(),

Answer 3

Конечно. Разные строки могут иметь один и тот же hashCode, поэтому, если вы храните две такие строки как ключи на карте, у вас будет две записи (поскольку строки разные). Если вы используете их hashCode в качестве ключа, у вас будет только одна запись (поскольку их hashCode такой же).

HashCode не используется, чтобы сказать, равны ли два ключа. Он используется только для назначения корзины ключу. Как только корзина найдена, каждый ключ, содержащийся в корзине, сравнивается с новым ключом с равными, и ключ добавляется в корзину, если не может быть найден равный ключ.

Answer 4

HashCodes может быть одинаковым или разным для одной и той же строки, поэтому будьте осторожны с этим. Может быть, поэтому вы получаете другой результат.

Вот еще один такой вопрос. Посмотрите принятый ответ Джона Скита.

Answer 5

Вы можете использовать хеш-код в качестве ключа, только если хеш-функция является идеальным хешем (см., Например, GPERF). Пока ваши ключевые объекты не находятся в памяти, вы правы в том, что вы сэкономите память.