В чому різниця між HashMap та Hashtable

HashMap і Hashtable — це дві реалізації асоціативного масиву (інтерфейсу Map), які зберігають дані у вигляді пар «ключ-значення». Проте між ними існують фундаментальні архітекту...

🟢 Junior Level

HashMap і Hashtable — це дві реалізації асоціативного масиву (інтерфейсу Map), які зберігають дані у вигляді пар «ключ-значення». Проте між ними існують фундаментальні архітектурні та історичні відмінності:

Характеристика	`HashMap`	`Hashtable`
Потокобезпечність	❌ Не потокобезпечна (висока швидкість)	✅ Потокобезпечна (методи `synchronized`)
Підтримка `null`	✅ Дозволяє 1 `null`-ключ і будь-які `null`-значення	❌ Забороняє `null` (викидає NPE)
Статус у JDK	Сучасний стандарт (Java 1.2+)	Застарілий клас (Legacy з Java 1.0)
Продуктивність	Висока (без блокувань, бітова індексація)	Низька (блокування всієї таблиці на кожен виклик)
Деревофікація колізій	Перетворення бакетів у RB-Tree ($O(\log N)$)	Виключно зв’язний список ($O(N)$)

import java.util.HashMap;
import java.util.Hashtable;
import java.util.Map;

public class MapVsHashtableDemo {
    public static void main(String[] args) {
        // Сучасний вибір
        Map<String, String> hashMap = new HashMap<>();
        hashMap.put(null, "Allowed"); // OK

        // Застарілий клас (Legacy)
        Map<String, String> hashtable = new Hashtable<>();
        // hashtable.put(null, "Error"); // Викине NullPointerException!
    }
}

Аналогія: Hashtable — це старий механічний сейф, до якого пускають суворо по одній людині: доки один переглядає вміст, усі інші чекають зовні в черзі. HashMap — це відкритий сучасний стелаж без черг для одного працівника (або ConcurrentHashMap — для одночасного паралельного доступу багатьох людей до різних полиць).

🟡 Middle Level

Детальна порівняльна таблиця

Критерій	`HashMap`	`Hashtable`
Ієрархія класів	Спадкує `AbstractMap`	Спадкує застарілий клас `Dictionary`
Початкова місткість (Default)	$16$ ($2^4$, степінь двійки)	$11$ (непарне/просте число)
Формула ресайзу	$\text{newCap} = \text{oldCap} \ll 1$ ($2 \times$)	$\text{newCap} = (\text{oldCap} \ll 1) + 1$
Обчислення індексу	`(n - 1) & hash` (бітова маска, 1 такт)	`(hash & 0x7FFFFFFF) % n` (ділення за модулем)
Perturbation Function	`(h = key.hashCode()) ^ (h >>> 16)`	Відсутня (береться `key.hashCode()`)
Ітератори	`Iterator` (поведінка Fail-Fast)	`Iterator` (Fail-Fast) + `Enumeration` (Fail-Safe)
Структура бакета	Зв’язний список $\to$ Червоно-чорне дерево	Виключно однозв’язний список

Чому `Hashtable` вважається застарілим антипатерном?

Груба синхронізація (Coarse-Grained Locking): Усі публічні методи Hashtable позначені ключовим словом synchronized:
```
public synchronized V get(Object key) { ... }
public synchronized V put(K key, V value) { ... }
```
Це означає, що на всю таблицю існує один спільний монітор (this). Навіть паралельні операції читання (get) блокують одна одну, шикуючи потоки в штучну чергу.
Відсутність деревофікації: У разі атаки Hash Flooding або невдалої хеш-функції Hashtable деградує до $O(N)$ без шансів оптимізації в дерево.
Сучасна заміна:
- Для однопотокового коду: HashMap.
- Для багатопотокового коду: ConcurrentHashMap (працює в десятки разів швидше завдяки CAS і побакетним блокуванням).
- Якщо суворо вимагається блокування всієї таблиці: Collections.synchronizedMap(new HashMap<>()).

🔴 Senior Level

Індексація та математика ресайзу: Modulo vs Bitwise AND

Розробники Hashtable (1995 р.) та HashMap (1998 р.) обрали принципово різні підходи до обчислення індексу:

1. Підхід `Hashtable`:

int index = (hash & 0x7FFFFFFF) % tab.length;

Операція & 0x7FFFFFFF обнуляє старший знаковий біт, перетворюючи від’ємний hashCode() на додатний діапазон [0, Integer.MAX_VALUE].
Операція ділення за модулем % (idiv) є однією з найповільніших інструкцій мікропроцесора (15–40 тактів).
Формула ресайзу (oldCapacity << 1) + 1 цілеспрямовано генерує непарні числа ($11 \to 23 \to 47 \to 95$). Непарні числа зменшують імовірність колізій у разі використання «сирого» hashCode().

2. Підхід `HashMap`:

int index = (table.length - 1) & hash;

Побітове «І» виконується за 1 такт процесора.
Зобов’язує місткість бути суворо степенем двійки ($2^k$).
Щоб усунути проблему колізій через степінь двійки, застосовується попереднє перемішування бітів: (h = key.hashCode()) ^ (h >>> 16).

Ітератори: `Enumeration` проти `Iterator`

У Hashtable співіснують два механізми обходу:

Застарілий Enumeration (hashtable.elements(), hashtable.keys()):
- Не має методу remove().
- Не є fail-fast: він не перевіряє поле modCount! Якщо інший потік модифікує Hashtable під час роботи Enumeration, виняток ConcurrentModificationException не буде викинуто, проте результат ітерації може містити пропущені або двічі обійдені елементи.
Колекційний Iterator (hashtable.keySet().iterator()):
- Був доданий у Java 1.2 під час адаптації Hashtable під інтерфейс Map. Є повноцінним fail-fast ітератором.

Спадщина `java.util.Properties`

Чому Hashtable досі не видалена з JDK? Головна причина зворотної сумісності — клас java.util.Properties (використовуваний для читання конфігураційних файлів .properties), який історично оголошений як:

public class Properties extends Hashtable<Object, Object>

Успадкування Properties від Hashtable визнано однією з найвідоміших помилок проєктування стандартної бібліотеки Java (порушення принципу композиції на користь успадкування). Через це в Properties можна випадково покласти довільні нерядкові об’єкти через put(key, value), що ламає методи getProperty(String key).

4 Tricky Questions

1. Якщо огорнути `HashMap` через `Collections.synchronizedMap(map)`, чи стане вона ідентичною `Hashtable`?

Відповідь: Ні, між ними залишиться низка ключових відмінностей:

Підтримка null: Collections.synchronizedMap(new HashMap<>()) як і раніше дозволяє один null-ключ і множину null-значень, тоді як Hashtable викине NullPointerException.
Деревофікація: Огорнута HashMap у Java 8+ у разі колізій продовжить перетворювати бакети в червоно-чорні дерева ($O(\log N)$), а Hashtable завжди залишається однозв’язним списком ($O(N)$).
Продуктивність індексації: HashMap використовує побітову маску (n - 1) & hash замість важкого ділення % у Hashtable.
Об’єкт блокування: У Hashtable синхронізація йде за this (самим об’єктом таблиці). У synchronizedMap можна явно передати кастомний об’єкт м’ютекса другим аргументом конструктора.

2. Чому в `Hashtable` виклик `put(key, null)` призводить до `NullPointerException`, хоча в методі `put` перший рядок — `if (value == null) throw new NullPointerException();`, а для ключа явної перевірки немає?

Відповідь: Для ключа явна перевірка не потрібна, тому що викидання NPE гарантовано першим же рядком роботи з ключем:

public synchronized V put(K key, V value) {
    if (value == null) {
        throw new NullPointerException(); // Явна перевірка значення
    }
    // ...
    int hash = key.hashCode(); // Неявний NPE, якщо key == null!
}

Якщо передати key == null, виклик key.hashCode() автоматично викине JVM-виняток NullPointerException. Для значення ж перевірка зроблена явним if, оскільки у значення метод hashCode() всередині методу не викликається.

3. Чому початкова місткість `Hashtable` дорівнює 11, а у `HashMap` — 16?

Відповідь:

У Hashtable індекс бакета обчислюється діленням за модулем hash % capacity. Щоб мінімізувати кількість колізій у разі використання простого ділення (особливо якщо вхідні хеш-коди кратні якомусь числу), розмір таблиці має бути простим або непарним числом. Число 11 — найменше зручне просте число, близьке до 10.
У HashMap для обчислення індексу використовується побітове «І» (capacity - 1) & hash. Ця формула коректно розподіляє елементи по всіх бакетах тільки в тому разі, якщо місткість є точним степенем двійки ($2^k$). Число 16 ($2^4$) було обрано як оптимальний початковий степінь двійки.

4. Чи викидатиме ітератор `hashtable.elements()` виняток `ConcurrentModificationException` під час паралельного додавання елементів?

Відповідь: Ні, не викидатиме. Метод hashtable.elements() повертає застарілий інтерфейс Enumeration. Його внутрішня реалізація Enumerator не відстежує значення лічильника структурних модифікацій modCount і не має механізму fail-fast. У результаті обхід через Enumeration виконається без винятків, але поведінка буде недетермінованою: ітератор може повернути елементи в неузгодженому стані, пропустити щойно додані записи або повернути дублікати.

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

Головна відмінність: Hashtable — застарілий синхронізований клас (Java 1.0); HashMap — швидка несинхронізована сучасна колекція (Java 1.2+).
Синхронізація: У Hashtable усі методи synchronized (блокування всієї таблиці). У сучасному коді для багатопотоковості застосовується ConcurrentHashMap.
Підтримка null: HashMap дозволяє null (1 ключ, будь-які значення). Hashtable суворо забороняє null скрізь (NPE).
Індексація: HashMap використовує побітову маску (n - 1) & hash (1 такт); Hashtable використовує ділення hash % capacity (повільно).
Ієрархія: HashMap успадковує AbstractMap, Hashtable успадковує застарілий Dictionary.
Чому Hashtable досі живе: Задля зворотної сумісності, зокрема через клас java.util.Properties extends Hashtable.

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

Твердження, що Hashtable рекомендується для сучасних багатопотокових проєктів (слід використовувати ConcurrentHashMap).
Твердження, що Hashtable підтримує деревофікацію при колізіях (вона завжди лишається зв’язним списком).
Думка, що Collections.synchronizedMap(map) повністю ідентична Hashtable (вони відрізняються підтримкою null, алгоритмом індексації та деревами).

🟢 Junior Level

🟡 Middle Level

Детальна порівняльна таблиця

Чому Hashtable вважається застарілим антипатерном?

🔴 Senior Level

Індексація та математика ресайзу: Modulo vs Bitwise AND

1. Підхід Hashtable:

2. Підхід HashMap:

Ітератори: Enumeration проти Iterator

Спадщина java.util.Properties