О Object.hashcode () и коллизиях

Я читал JavaDoc для Object.hashCode метод, он говорит, что

Насколько это разумно практично, метод hashCode, определенный классом Object, действительно возвращает отдельные целые числа для отдельных объектов. (Обычно это реализуется путем преобразования внутреннего адреса объекта в целое число [...])

Но какой бы ни была его реализация, метод hashCode всегда возвращает (допустим, положительное) целое число, поэтому при Integer.MAX+1 разных объектах два из них будут иметь одинаковый хэш-код.

Почему здесь JavaDoc «отрицает» коллизии? Это практический вывод, учитывая, что используется внутренний адрес и «да ладно, у вас никогда не будет Integer.MAX+1 объектов в памяти сразу, поэтому мы можем сказать, что он практически всегда уникален»?

РЕДАКТИРОВАТЬ

Эта запись об ошибке (спасибо, Sleiman Jneidi) дает точное представление о том, что я имею в виду (похоже, это обсуждение прошло более 10 лет):

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

Квалификации «настолько, насколько это разумно практично» на практике недостаточно, чтобы прояснить, что на практике хэш-коды не являются отдельными.


java hashcode hash-collision
person Luigi Cortese    schedule 17.12.2015    source источник
comment
Вы пропустили эту часть настолько, насколько это разумно практично. Конечно, если у вас более 2 ^ 32 объектов, у вас наверняка будут столкновения.   -  person JB Nizet    schedule 17.12.2015
comment
Это, и вы также пропустили часть, что если два объекта равны, они тоже должны иметь одинаковый хэш-код.   -  person fge    schedule 17.12.2015
comment
@JBNizet, значит, вы говорите, что я правильно понимаю?   -  person Luigi Cortese    schedule 17.12.2015
comment
@fge как это связано с этим? Если хэш-код всегда возвращает 1, равные объекты также имеют одинаковые хэш-коды.   -  person Luigi Cortese    schedule 17.12.2015
comment
hashCode может быть отрицательным, поэтому объекты Integer.MAX + 1 не обязательно означают два с одинаковым хэш-кодом. Я думаю, это должно быть 2 * Integer.MAX + 2 (или просто 2 ^ 32 + 1) объектов (потому что abs (Integer.MIN) -1 = abs (IntegerMax)). Но это уж больно придирчиво ...   -  person mixmastered    schedule 17.12.2015
comment
@mixmastered Я решил, что просто для простоты   -  person Luigi Cortese    schedule 17.12.2015
comment
Для меня JavaDoc просто означает, что реализация делает все возможное, чтобы избежать коллизий, насколько это разумно практично. Это не говорит о том, что они невозможны.   -  person Henry    schedule 17.12.2015
comment
@LuigiCortese, да. как говорит Генри, JVM делает все возможное, но не может изменить законы математики.   -  person JB Nizet    schedule 17.12.2015

Ответы (3)


arrow_upward
3
arrow_downward

Документы действительно вводят в заблуждение, и существует ошибка, обнаруженная много лет назад, которая говорит, что документы вводят в заблуждение, особенно то, что реализация JVM зависит, и на практике, особенно с огромными размерами кучи, очень вероятно возникновение коллизий при сопоставлении идентификаторов объектов с 32-битными целыми числами

person Sleiman Jneidi    schedule 17.12.2015
comment
Точно! В смысле, я бы написал что-нибудь вроде «обратите внимание!» Метод hashcode может возвращать одни и те же значения для разных объектов, а не да, он практически уникален - person Luigi Cortese; 17.12.2015
comment
@LuigiCortese В нем говорится, что: не требуется, что если два объекта не равны согласно методу equals(java.lang.Object), то вызов метода hashCode для каждого из двух объектов должен < b> производить отчетливые целочисленные результаты. - person Andreas; 17.12.2015
comment
@Andreas Я неправильно понял твой приговор. То, что вы процитировали, говорит о том, что это не ограничение, имеющее разные хэш-коды для разных объектов, и это не ограничение, потому что его невозможно удовлетворить, используя конечное (int) представление. Затем, написание [они уникальны] насколько это разумно практично, это как писать То, что я говорю, не всегда верно, но [они уникальны]. Это то, что я считаю неправильным / вводящим в заблуждение или что-то еще - person Luigi Cortese; 17.12.2015

arrow_upward
0
arrow_downward

здесь есть интересное обсуждение коллизий хэш-кода:

http://eclipsesource.com/blogs/2012/09/04/the-3-things-you-should-know-about-hashcode/

В частности, это подчеркивает, что ваш практический вывод «у вас никогда не будет объектов Integer.MAX + 1 в памяти сразу, поэтому мы можем сказать, что они практически всегда уникальны», далек от точного из-за парадокс дня рождения.

Вывод из ссылки состоит в том, что, предполагая случайное распределение хэш-кодов, нам нужно всего 77 163 объекта, прежде чем у нас будет 50/50 шанс столкновения хэш-кодов.

person mixmastered    schedule 17.12.2015
comment
Object.hashCode не производит случайного распределения. Сгенерированные хэш-коды не случайны. В javadoc говорится: насколько это разумно практично, метод hashCode, определенный классом Object, действительно возвращает отдельные целые числа для отдельных объектов. - person JB Nizet; 17.12.2015
comment
для меня это звучит действительно неправильно, используя разумно практичный в контексте языка программирования, хотя - person Luigi Cortese; 17.12.2015
comment
@LuigiCortese Почему? hashCode должен генерировать хорошо распределенные числа без ущерба для производительности. Реализация может пойти на полномасштабный крипто-безопасный алгоритм дайджеста, но он медленный, поэтому вместо этого следует использовать разумно практичную реализацию. Возможно, он не так хорошо распределен, но это нормально, потому что снижение производительности, наблюдаемое при возникновении коллизий, намного перевешивается более высокой производительностью метода hashCode. - person Andreas; 17.12.2015
comment
@Andreas для меня, допустимо рассматривать распределение как нечеткое свойство, можно сказать, что хэш-код практически хорошо распределен. Но не уникальность, вы не можете сказать, что хэш-код практически уникален, уникален он или нет, ничто не лежит посередине. В этом разница ИМХО - person Luigi Cortese; 17.12.2015

arrow_upward
0
arrow_downward

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

Так что обещание не очень сильное, но все же очень полезно. Например, при использовании хэш-кода в качестве быстрой индикации равенства перед выполнением полной проверки.

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

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

person Thirler    schedule 17.12.2015