Есть ли способ получить уникальный хэш-код Java от таких объектов, как HashMap?

Question

Я полагаю, что если я объявлю HashMap и несколько раз предоставлю ему экземпляры Map.Entry, в конце концов хеш-код столкнется с другим хеш-кодом, даже если два ключа (которые для моих нужд являются строками) различны.

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

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

Я могу создать реестр хеш-кода для своих строкно зачем, если Java уже может это сделать?

Answer 1

Нет .Вы не можете получить уникальный 32-битный номер для каждого возможного объекта в вашей системе.

Самое простое доказательство этого заключается в том, что на 64-битной JVM с достаточным объемом памяти вы можете легко имеет более 2 ^ 32 объектов: таким образом, вам потребуется более 2 ^ 32 различных значений хеш-функции.Но поскольку у вас есть только 32 бита для хранения этих хеш-значений, вы не можете получить более 2 ^ 32 разных хеш-значений.Это называется принцип Pidgeonhole .

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

Answer 2

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

1. Как указано другими, может быть больше объектов, чем можетбыть уникальным, представленным int: хэш-значение не может, следовательно, не может быть гарантировано уникальным.То есть диапазон хеш-функции меньше, чем область уникальных объектов.
2. Количество сегментов, используемых в хеш-таблице, [значительно] меньше, чем область значений хеш-функции: это приводит к неспособность гарантировать уникальное ведро используется : обычно bucket_used = hash % bucket_count.(Хеш-таблица с 2 ^ 32 сегментами для 42 записей вряд ли будет практичной; в этом случае область значения хэш-функции, если она больше, чем количество сегментов, в значительной степени не имеет значения.)

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

По этим причинам разрешение коллизий всегда требуется в общей реализации хэш-таблицы.(В реализации OpenJDK 7 HashMap используется подход цепочки связанных списков, и окончательное равенство определяется == и equals() в указанном порядке.)

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

Счастливого кодирования.

Answer 3

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

Как можно ожидать, что HashMap создаст действительно уникальный int хеш, когда может быть более 2 ³² различных объектов?