🔒 Розділ 13 · Питання #27

Чи можна використовувати незмінні об'єкти як ключі в HashMap

Головні причини:

🔒 Ім'ютабельність 📄 Вихідний Markdown

🟢 Junior Level

30-секундна відповідь

Не просто можна, а строго рекомендується! Незмінні (ім’ютабельні) об’єкти є золотим стандартом для ключів HashMap та HashSet.

Головні причини:

  1. Стабільність хеш-коду: значення hashCode() обчислюється на основі незмінних полів об’єкта і гарантовано залишається константним протягом усього життя програми.
  2. Гарантоване знаходження в бакеті: адреса корзини (bucket) у масиві хеш-таблиці розраховується за формулою (n - 1) & hash. Оскільки хеш не змінюється, map.get(key) завжди потрапляє саме в ту корзину, куди об’єкт було покладено при put(key, value).
  3. Захист від втрати даних: змінний ключ при зміні своїх полів змінює свій хеш-код, внаслідок чого об’єкт безповоротно «губиться» всередині таблиці, спричиняючи логічний витік пам’яті (Memory Leak).

Найкращі ключі в Java

  • java.lang.String — найпопулярніший та найбільш оптимізований ключ у Java.
  • Класи-обгортки примітивів (Integer, Long, UUID).
  • Класи дати й часу (LocalDate, Instant).
  • Java Records (Java 16+) — ідеальний вибір для складених ключів (Composite Keys).
// Класичний і безпечний приклад
Map<String, UserSession> sessions = new HashMap<>();
sessions.put("session_token_123", new UserSession("Alice"));

// Гарантовано поверне сесію Аліси:
UserSession session = sessions.get("session_token_123");

🟡 Middle Level

Механіка пошуку ключа в HashMap

При виклику map.put(key, value) та map.get(key) виконуються три суворі етапи:

  1. Обчислення хешу з перемішуванням (Bit Spreader): 
    static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  2. Визначення індексу корзини: index = (table.length - 1) & hash.
  3. Пошук вузла в корзині: перевірка p.hash == hash && (p.key == key || (key != null && key.equals(p.key))).

Якщо ключ мутабельний і змінив свій стан між викликами put та get:

  • get(key) обчислить новий хеш-код і піде шукати ключ у зовсім іншій корзині.
  • Метод поверне null, хоча фізично об’єкт із цим значенням залишається в купі в початковому бакеті!

Кешування хеш-коду (Lazy Hash Caching)

Незмінність відкриває можливість найпотужнішої оптимізації — кешування значення hashCode():

  • У класі String хеш-код обчислюється один раз при першому зверненні та запам’ятовується в приватне поле private int hash.
  • Усі наступні мільйони викликів map.get("someStringKey") беруть готовий hash за $O(1)$ без перерахунку символів!
  • Ви також можете реалізувати цей патерн у своїх незмінних класах: 
    public final class ImmutableOrderId {
  private final String prefix;
  private final long number;
  private int cachedHash; // Кеш

  public ImmutableOrderId(String prefix, long number) {
      this.prefix = Objects.requireNonNull(prefix);
      this.number = number;
  }

  @Override
  public int hashCode() {
      int h = cachedHash;
      if (h == 0) {
          h = Objects.hash(prefix, number);
          cachedHash = h;
      }
      return h;
  }
}

🔴 Senior Level

Складені ключі на базі Record (Composite Keys)

Для пошуку за кількома параметрами (наприклад, tenantId + userId) замість конкатенації рядків (tenant + ":" + id), яка створює сміттєві об’єкти, у сучасній Java використовують record:

// Ідеальний складений ключ в 1 рядок:
public record TenantUserKey(UUID tenantId, Long userId) implements Comparable<TenantUserKey> {
    @Override
    public int compareTo(TenantUserKey other) {
        int cmp = this.tenantId.compareTo(other.tenantId);
        return cmp != 0 ? cmp : this.userId.compareTo(other.userId);
    }
}

Переваги для Senior:

  1. Клас гарантовано final.
  2. Компілятор автоматично генерує математично коректні equals() та hashCode() на основі всіх компонентів.
  3. Реалізація Comparable захищає від деградації при колізіях.

Розв’язання колізій та деревоподібні корзини (Treeification)

Якщо різні незмінні ключі видають однаковий хеш-код (Hash Collision):

  1. Елементи складаються в один бакет у вигляді зв’язного списку.
  2. При перевищенні порогу у 8 елементів (TREEIFY_THRESHOLD = 8) і розмірі таблиці не менше 64 (MIN_TREEIFY_CAPACITY = 64) бакет перетворюється зі зв’язного списку на червоно-чорне дерево (Red-Black Tree).
  3. Складність пошуку падає з $O(N)$ до $O(\log N)$.
  4. Якщо ключі реалізують інтерфейс Comparable<K>, вузли дерева балансуються та порівнюються через compareTo(), повністю виключаючи необхідність виклику повільного System.identityHashCode().

Багатопотоковий контекст: ConcurrentHashMap

У ConcurrentHashMap незмінність ключів критична для масштабованості:

  • Під час процесу паралельного розширення таблиці (Concurrent Resizing) фонові потоки переносять бакети в нову таблицю.
  • Читаючі потоки виконують обхід без блокувань (Lock-Free Read).
  • Незмінність ключів гарантує, що читання хешу та порівняння посилань відбуваються атомарно й узгоджено без перегонів даних.

4 Tricky Questions

1. Чому клас String зберігає кешований хеш-код у звичайному, не-volatile полі private int hash, і чому це на 100% безпечно в багатопотоковому коді?

Відповідь: Це знаменита ідіома доброякісних перегонів даних (Benign Data Race):

  1. Клас String строго незмінний, а алгоритм обчислення hashCode() є чистою детермінованою функцією: за одними й тими самими незмінними байтами завжди виходить строго одне й те саме 32-бітне число.
  2. Якщо два потоки одночасно викличуть hashCode() у нового екземпляра String, вони обидва можуть обчислити значення паралельно й обидва запишуть абсолютно одне й те саме число в поле hash.
  3. Оскільки int у Java записується атомарно (на відміну від не-volatile long/double), потоки не можуть прочитати розірване значення. Відсутність модифікатора volatile виключає накладні витрати на бар’єри пам’яті процесора (Memory Barriers), забезпечуючи максимальну швидкість читання.

2. Що станеться, якщо клас-ключ record GroupKey(List<String> tags) оголошений як record, але в нього передано звичайний ArrayList?

Відповідь: Станеться прихована катастрофа:

  • Хоча record генерує final-поля, він забезпечує лише поверхневу (Shallow) незмінність.
  • Внутрішній ArrayList залишається змінним.
  • Якщо зовнішній код викличе tags.add("new_tag"), метод List.hashCode() перерахує хеш-код списку (він залежить від елементів).
  • Хеш-код GroupKey зміниться, і об’єкт загубиться в бакетах HashMap.
  • Правило: у Record для ключів колекція зобов’язана бути захищена через List.copyOf(tags) у компактному конструкторі!

3. Навіщо ключам у HashMap реалізовувати інтерфейс Comparable<K>, якщо для мапи обов’язкові тільки equals() та hashCode()?

Відповідь: У Java 8+ при великій кількості колізій в одному бакеті зв’язний список перетворюється на червоно-чорне дерево (TreeNode).

  • Для балансування та пошуку в дереві вузли необхідно впорядковувати.
  • Якщо ключ реалізує Comparable<K>, метод tree.putTreeVal() порівнює вузли через ((Comparable)k).compareTo(x). Це працює швидко й передбачувано.
  • Якщо ж ключ не реалізує Comparable, JVM змушена використовувати складний механізм тай-брейку (tie-break): порівнювати назви класів через getClass().getName(), а при збігу звертатися до нативного System.identityHashCode(), що суттєво уповільнює вставку та пошук.

4. Чи можна використовувати змінний об’єкт як ключ, якщо використовувати java.util.IdentityHashMap? У чому каверза?

Відповідь: Так, в IdentityHashMap це технічно можливо, але несе принципово іншу семантику:

  • IdentityHashMap повністю ігнорує методи equals() та hashCode().
  • Порівняння ключів виконується за посилальною рівністю k1 == k2, а хеш обчислюється через System.identityHashCode(), який прив’язаний до адреси об’єкта в купі й ніколи не змінюється від модифікації полів.
  • Каверза: два логічно абсолютно однакові об’єкти (наприклад, два User(id=1)) вважатимуться різними ключами, оскільки розташовані за різними адресами в пам’яті купи. Це підходить для кешів графів серіалізації, але непридатне для стандартної бізнес-логіки.

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

Головне про незмінні ключі в HashMap

  • Чи можна використовувати? Так, це рекомендований галузевий стандарт.
  • Чому: константний hashCode() $\to$ ключ завжди знаходиться в одному й тому ж бакеті $\to$ відсутність витоків пам’яті.
  • Оптимізація: кешування hashCode (як у String).
  • Складені ключі: використовувати Java Record із реалізацією Comparable.
  • Небезпека Shallow Immutability: якщо всередині ключа є змінна колекція, її мутація зламає хеш!

Змінний ключ vs Незмінний ключ

| Характеристика | Незмінний ключ (String, Record) | Змінний ключ (User, ArrayList) | | :— | :— | :— | | Стабільність хешу | 🟢 Гарантована 100% | 🔴 Змінюється при мутації | | Безпека пошуку | 🟢 Завжди знаходить значення | 🔴 Повертає null (втрата елемента) | | Витік пам’яті | 🟢 Виключений | 🔴 Високий ризик Logical Memory Leak | | Кешування хешу | 🟢 Можливе в приватному полі | ❌ Неможливе |

Червоні прапорці на співбесіді (Чого говорити не можна)

  • ❌ «Використовувати ArrayList як ключ HashMap — нормальна практика» — зміна списку зробить запис недосяжним.
  • ❌ «Для правильної роботи HashMap достатньо реалізувати лише hashCode()» — при колізіях мапа використовує equals(), обидва методи обов’язкові.
  • ❌ «Якщо поле ключа оголошене як final List<String>, ключ повністю захищений» — елементи списку можна змінювати, ламаючи хеш.

Пов’язані питання