Класс IdentityHashMap<K,​V>

public class IdentityHashMap<K,V>
extends AbstractMap<K,​V>
implements Map<K,​V>, Serializable, Cloneable

Этот класс реализует интерфейс Map с помощью хеш-таблицы, используя ссылочную эквивалентность вместо эквивалентности объектов при сравнении ключей (и значений). Другими словами, в IdentityHashMap, два ключа k1 и k2 считаются равными тогда и только тогда, когда (k1==k2). (В обычных реализациях Map (например, HashMap) два ключа k1 и k2 считаются равными тогда и только тогда, когда (k1==null ? k2==null : k1.equals(k2)).)

Этот класс не является универсальной реализацией Map! Хотя этот класс реализует интерфейс Map, он намеренно нарушает общий контракт Map's, который требует использования метода equals при сравнении объектов. Этот класс предназначен только для редких случаев, когда требуется семантика ссылочной эквивалентности.

Типичное использование этого класса – преобразования графов объектов, сохраняющих топологию, такие как сериализация или глубокое копирование. Для выполнения такого преобразования программа должна поддерживать «таблицу узлов», которая отслеживает все ссылки на объекты, которые уже были обработаны. Таблица узлов не должна приравнивать разные объекты, даже если они случайным образом равны. Другое типичное использование этого класса – поддержание объектов-прокси. Например, система отладки может захотеть поддерживать объект-прокси для каждого объекта в отлаживаемой программе.

Этот класс предоставляет все необязательные операции карты и допускает null значения и null ключ. Этот класс не гарантирует порядок карты; в частности, он не гарантирует, что порядок останется постоянным со временем.

Этот класс обеспечивает постоянное время выполнения для основных операций (get и put), предполагая, что функция хеширования системы идентификации (System.identityHashCode(Object)) правильно распределяет элементы по корзинам.

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

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

Обратите внимание, что эта реализация не синхронизирована. Если несколько потоков одновременно обращаются к карте тождественности, и по крайней мере один из потоков изменяет карту структурно, то необходимо внешне синхронизировать её. (Структурное изменение — это любая операция, которая добавляет или удаляет одну или несколько пар; просто изменение значения, связанного с ключом, который уже содержится в экземпляре, не является структурным изменением.) Обычно это достигается синхронизацией на каком-либо объекте, который естественным образом инкапсулирует карту. Если такого объекта нет, карту следует «обернуть» с помощью метода Collections.synchronizedMap. Это лучше всего сделать при создании, чтобы избежать случайного несинхронизированного доступа к карте:

Map m = Collections.synchronizedMap(new IdentityHashMap(...));

Итераторы, возвращаемые методом iterator коллекций, возвращаемых всеми «методами представления коллекций» этого класса, являются быстропроверяемыми: если карта каким-либо образом структурно изменяется в любое время после создания итератора, кроме как через собственный метод итератора remove, итератор выбросит исключение ConcurrentModificationException. Таким образом, при одновременном изменении итератор быстро и чисто завершает работу, а не рискует произвольным непредсказуемым поведением в неопределенный момент в будущем.

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

Примечание реализации: это простая хеш-таблица с линейным зондированием, как описано, например, в текстах Сedgewick и Knuth. Массив чередуется, содержащий ключи и значения. (Это обеспечивает лучшую локальность для больших таблиц, чем использование отдельных массивов.) Для многих реализаций JRE и наборов операций этот класс обеспечит лучшую производительность, чем HashMap (который использует цепирование, а не линейное зондирование).

Этот класс является членом Java Collections Framework.