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

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

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


java hashmap hashtable string-hashing
person user1785771    schedule 03.11.2012    source источник
comment
Можете быть более конкретными? Покажите фрагмент кода, где вы столкнулись с этой проблемой.   -  person Rohit Jain    schedule 03.11.2012
comment
Почему вы ожидаете, что другой ключ даст те же результаты? Это не будет.   -  person user207421    schedule 04.11.2012

Ответы (5)


arrow_upward
12
arrow_downward

когда я использую строковый хэш-код в качестве ключа в 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 для каждого из двух объектов должен давать разные целочисленные результаты. Однако Программист должен знать, что создание различных целочисленных результатов для неравных объектов может повысить производительность хеш-таблиц.
person Jon Skeet    schedule 03.11.2012

arrow_upward
3
arrow_downward

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

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

person JB Nizet    schedule 03.11.2012
comment
Спасибо всем за ответы. Я пытаюсь не хранить ключ в виде строки, так как он будет потреблять больше памяти! - person user1785771; 03.11.2012
comment
Не делайте поспешных выводов без измерения. Зачем ему использовать больше памяти? Карта не делает копию ключа. Он просто использует ссылку на ключ. - person JB Nizet; 03.11.2012
comment
Я знаю. Но когда у меня будет более двух миллионов записей, хранение их строковых ключей будет иметь большое значение! @JB - person user1785771; 03.11.2012
comment
@ user1785771: Они используют больше памяти по уважительной причине: есть больше важных данных, чем просто 32 бита для хэш-кода. Если вам нужно хранить много строк, получите много памяти. Память дешевая; ошибки из-за неправильного использования хэш-карты могут быть очень дорогими. - person Jon Skeet; 03.11.2012

arrow_upward
3
arrow_downward

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

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

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

Вкратце: -

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

person Rohit Jain    schedule 03.11.2012
comment
Я бы использовал !obj.equals(obj1) в последней строке, так как это важная часть. - person Jon Skeet; 03.11.2012

arrow_upward
1
arrow_downward

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

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

person Atif Imran    schedule 03.11.2012

arrow_upward
0
arrow_downward

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

person Floris    schedule 01.02.2014