🔑 Розділ 10 · Питання #24

Чи можна зберігати null ключ в HashMap

У класі java.util.HashMap функція хешування містить тернарну перевірку:

🔑 HashMap equals hashCode 📄 Вихідний Markdown

🟢 Junior Level

Так, HashMap повністю дозволяє зберігати null як ключ, але тільки в єдиному екземплярі.

Ключові особливості:

  1. Єдиність ключа: Як і для будь-яких інших ключів, у HashMap не може бути двох однакових ключів. Якщо повторно викликати map.put(null, "нове значення"), старе значення буде перезаписано.
  2. Завжди 0-й бакет: Хеш-код для null примусово приймається рівним 0. Тому запис із ключем null завжди потрапляє в кошик (бакет) з індексом 0 (table[0]).
  3. Безпека викликів: Під час роботи з null-ключем виняток NullPointerException не виникає, оскільки методи hashCode() та equals() у null не викликаються.
import java.util.HashMap;
import java.util.Map;

public class NullKeyDemo {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();

        map.put(null, "Default Value");
        System.out.println(map.get(null)); // "Default Value"

        // Перезапис значення за null-ключем
        map.put(null, "Updated Value");
        System.out.println(map.get(null)); // "Updated Value"
        System.out.println(map.size());    // 1 (розмір не збільшився)
    }
}

Аналогія: Ключ null — це спеціальна папка «Без категорії» на першій полиці шафи (в нульовій шухляді). Така папка може бути лише одна, і якщо покласти в неї новий документ, він замінить попередній.

🟡 Middle Level

Реалізація функції хешування для null

У класі java.util.HashMap функція хешування містить тернарну перевірку:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Обчислення індексу кошика відбувається за стандартною формулою: \(\text{index} = (n - 1) \ \& \ \text{hash} = (n - 1) \ \& \ 0 = 0\)

Отже, null-ключ завжди розміщується виключно в комірці table[0].

Порівняння ключів під час пошуку

Усередині бакета table[0] можуть міститися й інші елементи (не-null ключі, чий хеш дав нульовий залишок). Пошук вузла в ланцюжку виконується таким виразом:

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
  • Для null-ключа: key == null.
  • Друга частина перевірки (key != null && key.equals(k)) безпечно відсікається за короткою схемою (short-circuit evaluation).
  • Порівняння відбувається за посиланням: (k = p.key) == key $\implies$ p.key == null.
  • Метод equals() ніколи не викликається у null, що гарантує відсутність NullPointerException.

Підтримка null-ключа в різних колекціях

Колекція null-ключ null-значення Поведінка під час put(null, ...)
HashMap ✅ Дозволено (1) ✅ Дозволено Зберігає в table[0]
LinkedHashMap ✅ Дозволено (1) ✅ Дозволено Зберігає в table[0] + зв’язок у списку
ConcurrentHashMap ❌ Заборонено ❌ Заборонено Викидає NullPointerException
Hashtable ❌ Заборонено ❌ Заборонено Викидає NullPointerException
TreeMap ⚠️ Умовно ✅ Дозволено За замовчуванням NPE, але дозволено з Comparator.nullsFirst
Map.of(...) (Java 9+) ❌ Заборонено ❌ Заборонено Викидає NullPointerException

🔴 Senior Level

Еволюція реалізації: Java 7 vs Java 8+

У Java 7 для обробки null-ключа існували окремі спеціалізовані методи:

  • putForNullKey(V value)
  • getForNullKey()

Це було пов’язано з тим, що в Java 7 бакет table[0] оброблявся відокремлено, щоб уникнути зайвих перевірок у загальному циклі.

У Java 8+ архітектуру уніфікували:

  • Завдяки функції hash(key), яка повертає 0 для null, увесь ланцюжок логіки (putVal, getNode, removeNode) став єдиним для будь-яких типів ключів.
  • Виділені методи putForNullKey та getForNullKey було видалено з вихідного коду OpenJDK.

Бакет table[0] не зарезервований лише під null

Поширена помилкова думка: вважати, що комірка table[0] виділена виключно під null. Це не так:

  1. Будь-який об’єкт із key.hashCode() == 0 потрапить у бакет 0.
  2. Будь-який об’єкт, чий хеш кратний степеню двійки (наприклад, молодші біти хешу дорівнюють 0000), потрапить у table[0].
  3. У бакеті table[0] може утворитися повноцінний зв’язний список або навіть червоно-чорне дерево TreeNode, якщо туди потраплять 8 колізійних ключів разом із null!

Проблеми архітектури під час використання null-ключів

  1. Несумісність із багатопотоковим рефакторингом: Якщо кодова база спирається на null-ключі в HashMap, спроба міграції на ConcurrentHashMap під час переведення компонента в багатопотоковий режим призведе до масових падінь із NullPointerException у runtime.
  2. Неможливість використання фабрик Java 9+: Методи Map.of(), Map.ofEntries() та колектори Collectors.toUnmodifiableMap() принципово відхиляють null як ключі, викидаючи NullPointerException.
  3. Порушення семантики DDD (Domain-Driven Design): Ключ асоціативного масиву в бізнес-логіці є ідентифікатором сутності (ID користувача, артикул товару тощо). Відсутній ідентифікатор (null) не повинен бути валідним ідентифікатором.

Рекомендований патерн: Null Object Pattern

// Замість map.put(null, defaultHandler):
public enum SystemKey {
    ANONYMOUS,
    DEFAULT
}
map.put(SystemKey.DEFAULT, defaultHandler);

4 Tricky Questions

1. Чи можна зберегти null як ключ у TreeMap?

Відповідь: За замовчуванням — ні, але за наявності спеціального компаратора — так. За замовчуванням new TreeMap<>() використовує природний порядок елементів (Comparable). Під час першої вставки або порівняння викликається k.compareTo(...), що при передачі null негайно призводить до NullPointerException. Однак якщо створити TreeMap з компаратором, який підтримує null (наприклад, Comparator.nullsFirst(Comparator.naturalOrder())):

Map<String, String> treeMap = new TreeMap<>(Comparator.nullsFirst(String::compareTo));
treeMap.put(null, "Works!"); // Відпрацює успішно без помилок!
System.out.println(treeMap.get(null)); // "Works!"

У цьому разі компаратор перехоплює null до виклику методів об’єкта і коректно позиціонує його в корені або лівому краї дерева.

2. Що станеться, якщо покласти null-ключ у Collections.unmodifiableMap(map)?

Відповідь: Код виконається успішно. Клас Collections.unmodifiableMap є лише легковажним декоратором-обгорткою над переданою вихідною мапою. Він не накладає додаткових обмежень на типи даних. Якщо базовою колекцією є HashMap, виклики map.put(null, "val") до огортання або читання unmodMap.get(null) працюють без жодних винятків.

3. Чи може бакет table[0], який містить null-ключ, перетворитися на червоно-чорне дерево (TreeNode)?

Відповідь: Так, може. Якщо в бакет table[0] окрім вузла з ключем null додадуться ще 8 ключів із хешем 0 (або таких, що дають індекс 0), і загальний розмір таблиці досягне $\ge 64$, бакет 0 буде деревофіковано в червоно-чорне дерево. При цьому вузол null стане одним із TreeNode. Оскільки null не реалізує Comparable, під час балансування дерева HashMap впорядкує його відносно інших вузлів за допомогою fallback-методу tieBreakOrder(a, b) на основі System.identityHashCode(a).

4. Чому Map.of(null, "value") викидає виняток, тоді як new HashMap<>() приймає null?

Відповідь: Методи Map.of(), що з’явилися в Java 9, проектувалися відповідно до сучасних стандартів дизайну API. Творці мови (Браян Ґетц та команда OpenJDK) визнали дозвіл null у старих колекціях (Java 1.2) історичною помилкою («Billion-Dollar Mistake»), що провокує важковловлювані баги й ускладнює внутрішню оптимізацію. В усіх сучасних фабриках незмінних колекцій (List.of, Set.of, Map.of) null суворо заборонено на рівні валідації аргументів (Objects.requireNonNull).

🎯 Шпаргалка для інтерв’ю

  • Підтримка null: HashMap дозволяє рівно один null-ключ. Повторний put(null, val) перезаписує значення.
  • Де зберігається: Завжди в комірці table[0], оскільки hash(null) == 0.
  • Порівняння: Порівнюється за посиланням key == null. Метод equals() не викликається, виняток NPE неможливий.
  • Бакет 0: Не ізольований для null — туди можуть потрапляти звичайні ключі з колізійним хешем.
  • Інші колекції:
    • ConcurrentHashMap, Hashtable — суворо забороняють null (NPE).
    • TreeMap — забороняє за замовчуванням, але дозволяє з компаратором Comparator.nullsFirst(...).
    • Map.of() — суворо забороняє null (NPE).
  • Production Best Practice: Уникайте null-ключів, замінюючи їх патерном Null Object або спеціальними enum-значеннями.

Червоні прапорці (чого уникати)

  • Твердження, що HashMap забороняє null-ключі або викидає на них NPE.
  • Твердження, що бакет 0 зарезервований виключно для null і туди не можуть потрапити інші об’єкти.
  • Забування того, що ConcurrentHashMap категорично забороняє null як для ключів, так і для значень.
  • Використання null-ключів у критичній бізнес-логіці замість Null Object Pattern.

Пов’язані теми