Хэш-коды, возвращаемые методом System.identityHashCode, уникально назначаются каждому объекту?

Question

Являются ли хеш-коды, возвращаемые методом System.identityHashCode, уникально назначенными каждому объекту?

Поскольку хеш-код является целым числом и, следовательно, возможными значениями 4 294 967 295, гарантирует ли jvm хотя бы один уникальный хеш-код для каждого объект в таком количестве объектов?

Answer 1

Применяется принцип "голубиного отверстия".

Если у вас есть 4 голубиных отверстия и 5 голубей, которые должны найти голубиную лунку для ночлега, то хотя бы в одной голубиной лунке будет больше одного голубя. это.

Очевидно, верно?

То же самое применимо и здесь. Есть только 2^32 различных голубиных отверстий га sh кодов (поскольку значение int, int в java определяется как 32-битное число, таким образом, только 2 ^ 32 различные возможные значения выхода). Это большое, большое число. около 4 млрд.

Однако в java spe c нет ничего, что указывало бы на то, что когда-либо может существовать не более 4 миллиардов голубей объектов. Если существует более 4 миллиардов объектов, ни один алгоритм, который можно было бы разработать, никогда не мог бы пообещать уникальности из-за этого принципа. КЭД.

NB. Вы также можете использовать принцип квадратного отверстия, чтобы доказать, что универсальный компрессор (инструмент, который может сжимать все, что гарантирует, что сжатый результат всегда меньше или равен) не может существовать, пока он на самом деле что-то сжимает, то, как следствие, должен быть некоторый поток битов, для которого компрессор фактически создает файл большего размера . Вы можете использовать его, чтобы доказать, что (int) (Math.random() * 10) не совсем равномерная случайная величина, и почему вы должны поэтому использовать random.nextInt(10) вместо этого (что есть). Это удивительно полезный принцип, чтобы доказать что-то в компьютерных науках!

Теперь можно представить систему кодирования на основе int, которая обещает уникальные коды до , когда вы попадете в 4 миллиарда уникальных объектов, но сделаете такое обещание невероятно сложно и само по себе является проблемой памяти, если бы оно работало для всех без исключения объектов.

Java не дает таких обещаний, и, как следствие, System.iHC не гарантированно будет иметь либо уникальные числа (абсолютно невозможно дать такое обещание), либо то, что System.iHC имеет «идеальное» распределение (хеш-коды распределены настолько, насколько они могли бы быть, то есть не использовать повторно, пока не существует 4 миллиарда объектов одновременно). Обратите внимание, что «существует» уже сложно: когда объект действительно «исчезает»?

На практике iH C основан на позициях памяти; это очень хорошее распределение. Но есть разница между , очень маловероятно, что любые 2 объекта когда-либо будут иметь одинаковый хэш-код идентификатора и , мы гарантируем, что никакие два объекта не будут иметь идентификаторы ha sh code .

Answer 2

Из того, что я прочитал, вместо того, чтобы зарезервировать место для кода объекта ha sh, по крайней мере, некоторая версия JVM резервирует пару битов в заголовке объекта, которые указывают, какое из трех примененных условий:

1. Идентификационный код ha sh еще не проверен.
2. Идентификационный код ha sh проверен, и с тех пор объект не был перемещен.
3. Идентификационный код ha sh был проверен, а затем объект был перемещен.

Получение идентификатора hashCode, когда объект находится в состоянии # 1, изменит его на состояние # 2 и вернет значение происходит от адреса объекта. Получение идентификатора hashCode, когда объект находится в состоянии # 2, просто выполнит те же вычисления на адресе.

Если объект в состоянии # 1 необходимо переместить, он просто останется в состоянии # 1. Если объект перемещается, когда он находится в состоянии # 2, система создаст копию с четырьмя дополнительными байтами, зарезервированными для кода ha sh, вычислит код ha sh на основе старого адреса и сохранит его в эти зарезервированные байты, и пометьте объект как находящийся в состоянии # 3. После этого любая попытка прочитать код ha sh сообщит о сохраненном значении.

Если объект создается, а затем перемещается или уничтожается, ранее занимаемое им пространство, вероятно, будет использоваться в какое-то время в будущее, чтобы держать новый объект. Такой объект вполне может иметь тот же адрес, что и старый; если это так, то код ha sh, скорее всего, будет совпадать.

Обратите внимание, что функция hashCode, как ожидается, не будет достаточно хорошей, чтобы избежать всех коллизий, а достаточно хороша, чтобы выполнить большое количество сравнений. в небольшое количество. Если код ha sh может уменьшить количество сравнений с 10 000 до 10, это гораздо более выигрышная задача, чем сокращение числа сравнений с 10 до 1.

Answer 3

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