JavaNotes

HashMap

2 min read

HashMap

HashMap<K, V> хранит пары «ключ — значение» и реализует Map<K, V>. Ключи уникальны по контракту equals, значения могут повторяться. Один ключ и несколько значений могут быть null. Порядок обхода не гарантирован.

Как устроена

Внутри находится массив бакетов. Бакет бывает пустым, цепочкой узлов или, при большом числе коллизий, красно-чёрным деревом.

Путь операции get(key):

  1. Получить hashCode ключа; для null используется ноль.
  2. Смешать старшие и младшие биты: h ^ (h >>> 16).
  3. Найти индекс: (table.length - 1) & hash.
  4. Сравнить hash, затем ключи через equals.

Длина таблицы — степень двойки, поэтому битовая маска заменяет деление.

record UserId(long value) {}
 
Map<UserId, String> names = new HashMap<>();
names.put(new UserId(7), "Ира");
String name = names.get(new UserId(7)); // Ира

Ёмкость, load factor и resize

По умолчанию load factor равен 0.75. Порог расширения: capacity * loadFactor. При превышении порога таблица в Java 8+ удваивается. Узел остаётся на прежнем индексе или переезжает на oldIndex + oldCapacity: это определяется одним битом hash, полный перерасчёт остатка не нужен.

При ёмкости не меньше 64 цепочка превращается в дерево после добавления девятого узла в бакет (TREEIFY_THRESHOLD = 8). При меньшей таблице сначала выполняется расширение. При сокращении до шести узлов дерево снова может стать списком.

ОперацияОбычноХудший случай
get, put, removeO(1)O(n), для дерева O(log n)
containsValueO(n)O(n)
обходO(capacity + size)O(capacity + size)

Важные ограничения

  • Ключ не должен менять поля, участвующие в equals и hashCode, пока он в map.
  • HashMap не потокобезопасен; для общей изменяемой map см. ConcurrentHashMap.
  • Начальная ёмкость влияет на resize и стоимость обхода.
  • Коллизия допустима: разные ключи могут иметь одинаковый hash.
  • put с равным ключом заменяет значение и возвращает предыдущее.

Подробнее о контракте ключа: Equals и hashCode. Оценки сложности: Big O.

Вопросы для собеседования

  1. Почему ёмкость — степень двойки? Чтобы вычислять индекс маской и распределять узлы при resize по одному дополнительному биту.
  2. Когда бакет становится деревом? После превышения порога цепочки при ёмкости таблицы не меньше 64.
  3. Что произойдёт при изменении ключа? Поиск пойдёт в другой бакет или не найдёт равный ключ; запись фактически станет недоступной.
  4. Допускает ли map коллизии? Да, hash выбирает бакет, а равенство ключа проверяется отдельно.
  5. Почему средняя сложность get — O(1)? При хорошем распределении в бакете остаётся мало элементов.
  6. Гарантирует ли HashMap порядок? Нет; для порядка вставки нужен LinkedHashMap, для сортировки — TreeMap.

Graph View

Backlinks