В чём разница между 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.

🟢 Junior Level

🟡 Middle Level

Детальная сравнительная таблица

Почему Hashtable считается устаревшим антипаттерном?

🔴 Senior Level

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

1. Подход Hashtable:

2. Подход HashMap:

Итераторы: Enumeration против Iterator

Наследие java.util.Properties

4 Tricky Questions

1. Если обернуть HashMap через Collections.synchronizedMap(map), станет ли она идентична Hashtable?

2. Почему в Hashtable вызов put(key, null) приводит к NullPointerException, хотя в методе put первая строчка — if (value == null) throw new NullPointerException();, а для ключа явной проверки нет?

3. Почему начальная ёмкость Hashtable равна 11, а у HashMap — 16?

4. Будет ли итератор hashtable.elements() выбрасывать ConcurrentModificationException при параллельном добавлении элементов?