Перейти к основному содержимому

Класс Java IdentityHashMap и варианты его использования

· 6 мин. чтения

Задача: Медиана двух отсортированных массивов

Даны два отсортированных массива размерами n и m. Найдите медиану слияния этих двух массивов.
Временная сложность решения должна быть O(log(m + n)) ...

ANDROMEDA

1. Обзор

В этом руководстве мы узнаем, как использовать класс IdentityHashMap в Java. Мы также рассмотрим, чем он отличается от общего класса HashMap . Хотя этот класс реализует интерфейс Map , он нарушает контракт интерфейса Map .

Для получения более подробной документации мы можем обратиться к странице документа IdenityHashMap java. Подробнее об общем классе HashMap можно прочитать в A Guide to Java HashMap .

2. О классе IdentityHashMap

Этот класс реализует интерфейс Map . Интерфейс карты требует использования метода equals() при сравнении ключей. Однако класс IdentityHashMap нарушает этот договор. Вместо этого он использует ссылочное равенство (==) для ключевых операций поиска .

Во время операций поиска HashMap использует для хеширования метод hashCode() , тогда как IdentityHashMap использует метод System.identityHashCode() . Он также использует метод линейного зондирования хеш-таблицы для операций поиска.

Использование равенства ссылок, System.identityHashCode() и метода линейного зондирования повышает производительность класса IdentityHashMap .

3. Использование класса IdentityHashMap

Конструкция объекта и сигнатуры методов такие же, как у HashMap, но поведение отличается из-за равенства ссылок.

3.1. Создание объектов IdentityHashMap

Мы можем создать его с помощью конструктора по умолчанию:

IdentityHashMap<String, String> identityHashMap = new IdentityHashMap<>();

Или его можно создать, используя начальную ожидаемую мощность:

IdentityHashMap<Book, String> identityHashMap = new IdentityHashMap<>(10);

Если мы не укажем начальный параметр expectCapcity , как мы сделали выше, он использует 21 в качестве емкости по умолчанию.

Мы также можем создать его, используя другой объект карты:

IdentityHashMap<String, String> identityHashMap = new IdentityHashMap<>(otherMap);

В этом случае он инициализирует созданную identityHashMap записями otherMap .

3.2. Добавить, получить, обновить и удалить записи

Метод put() используется для добавления записи:

identityHashMap.put("title", "Harry Potter and the Goblet of Fire");
identityHashMap.put("author", "J. K. Rowling");
identityHashMap.put("language", "English");
identityHashMap.put("genre", "Fantasy");

Мы также можем добавить все записи с другой карты, используя метод putAll() :

identityHashMap.putAll(otherMap);

Для получения значений мы используем метод get() :

String value = identityHashMap.get(key);

Чтобы обновить значение ключа, мы используем метод put() :

String oldTitle = identityHashMap.put("title", "Harry Potter and the Deathly Hallows");
assertEquals("Harry Potter and the Goblet of Fire", oldTitle);

В приведенном выше фрагменте метод put() возвращает старое значение после обновления. Второй оператор гарантирует, что oldTitle соответствует более раннему значению title.

Мы можем использовать метод remove() для удаления элемента:

identityHashMap.remove("title");

3.3. Повторить все записи

Мы можем пройтись по всем записям, используя метод entitySet() :

Set<Map.Entry<String, String>> entries = identityHashMap.entrySet();
for (Map.Entry<String, String> entry: entries) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}

Мы также можем пройтись по всем записям, используя метод keySet() :

for (String key: identityHashMap.keySet()) {
System.out.println(key + ": " + identityHashMap.get(key));
}

Эти итераторы используют отказоустойчивый механизм. Если карта изменяется во время итерации, она генерирует исключение ConcurrentModificationException .

3.4. Другие методы

У нас также есть различные доступные методы, которые работают аналогично другим объектам Map :

  • clear() : удаляет все записи
  • containsKey() : определяет, существует ли ключ на карте или нет. Приравниваются только ссылки
  • containsValue() : определяет, существует ли значение на карте. Приравниваются только ссылки
  • keySet() : возвращает набор ключей на основе идентификации
  • size() : возвращает количество записей
  • values() : возвращает набор значений

3.5. Поддержка нулевых ключей и нулевых значений

IdentityHashMap допускает значение null как для ключа, так и для значения:

IdentityHashMap<String, String> identityHashMap = new IdentityHashMap<>();
identityHashMap.put(null, "Null Key Accepted");
identityHashMap.put("Null Value Accepted", null);
assertEquals("Null Key Accepted", identityHashMap.get(null));
assertEquals(null, identityHashMap.get("Null Value Accepted"));

В приведенном выше фрагменте гарантируется значение null как для ключа, так и для значения.

3.6. Параллелизм с IdentityHashMap

IdentityHashMap не является потокобезопасным , как и HashMap . Поэтому, если у нас есть несколько потоков для параллельного доступа/изменения записей IdentityHashMap , мы должны преобразовать их в синхронизированную карту.

Мы можем получить синхронизированную карту, используя класс Collections :

Map<String, String> synchronizedMap = Collections.synchronizedMap(new IdentityHashMap<String, String>());

4. Пример использования эталонного равенства

IdentityHashMap использует ссылочное равенство (==) по сравнению с методом equals() для поиска/сохранения/доступа к ключевым объектам.

IdentityHashMap , созданный с четырьмя свойствами:

IdentityHashMap<String, String> identityHashMap = new IdentityHashMap<>();
identityHashMap.put("title", "Harry Potter and the Goblet of Fire");
identityHashMap.put("author", "J. K. Rowling");
identityHashMap.put("language", "English");
identityHashMap.put("genre", "Fantasy");

Другой HashMap , созданный с теми же свойствами:

HashMap<String, String> hashMap = new HashMap<>(identityHashMap);
hashMap.put(new String("genre"), "Drama");
assertEquals(4, hashMap.size());

При использовании нового строкового объекта « genre» в качестве ключа HashMap приравнивает его к существующему ключу и обновляет значение. Следовательно, размер хеш-карты остается таким же, как 4.

В следующем фрагменте кода показано, как IdentityHashMap ведет себя иначе:

identityHashMap.put(new String("genre"), "Drama");
assertEquals(5, identityHashMap.size());

IdentityHashMap рассматривает новый строковый объект «жанр» как новый ключ. Следовательно, он утверждает, что размер равен 5. Два разных объекта «жанра» используются в качестве двух ключей со значениями « Драма » и « Фэнтези » .

5. Изменяемые ключи

IdentityHashMap позволяет изменять ключи . Это еще одна полезная функция этого класса.

Здесь мы возьмем простой класс Book в качестве изменяемого объекта:

class Book {
String title;
int year;

// other methods including equals, hashCode and toString
}

Сначала создаются два изменяемых объекта класса Book :

Book book1 = new Book("A Passage to India", 1924);
Book book2 = new Book("Invisible Man", 1953);

Следующий код показывает использование изменяемого ключа с помощью HashMap :

HashMap<Book, String> hashMap = new HashMap<>(10);
hashMap.put(book1, "A great work of fiction");
hashMap.put(book2, "won the US National Book Award");
book2.year = 1952;
assertEquals(null, hashMap.get(book2));

Хотя запись book2 присутствует в HashMap , она не может получить ее значение. Поскольку он был изменен, метод equals() теперь не соответствует измененному объекту. Вот почему общие объекты Map предписывают неизменяемые объекты в качестве ключа.

В приведенном ниже фрагменте используются те же изменяемые ключи с IdentityHashMap :

IdentityHashMap<Book, String> identityHashMap = new IdentityHashMap<>(10);
identityHashMap.put(book1, "A great work of fiction");
identityHashMap.put(book2, "won the US National Book Award");
book2.year = 1951;
assertEquals("won the US National Book Award", identityHashMap.get(book2));

Интересно, что IdentityHashMap может извлекать значения, даже если ключевой объект был изменен. В приведенном выше коде assertEquals гарантирует, что тот же текст будет получен снова. Это возможно благодаря ссылочному равенству.

6. Некоторые варианты использования

Благодаря своим функциям IdentiyHashMap стоит особняком от других объектов Map . Однако он не используется для общих целей, и поэтому мы должны быть осторожны при использовании этого класса.

Это полезно при создании конкретных фреймворков, в том числе:

  • Ведение прокси-объектов для набора изменяемых объектов
  • Построение быстрого кеша на основе ссылки на объект
  • Хранение в памяти графа объектов со ссылками

7. Заключение

В этой статье мы узнали, как работать с IdentityHashMap , чем он отличается от обычного HashMap , и некоторыми вариантами использования.

Полный пример кода можно найти на GitHub .