Что такое HashTable?

Что такое HashTable

HashTable (Хеш-таблица) — это структура данных, которая реализует интерфейс Map в Java и хранит данные в виде пар ключ-значение. Это один из старейших контейнеров Java (с JDK 1.0), полностью синхронизированный, но сегодня считается устаревшим.

Основные характеристики

HashTable:

• Синхронизирована (thread-safe) — все методы synchronized
• Не допускает null ключи и null значения
• Использует хеширование с открытой адресацией
• Начальная ёмкость по умолчанию 11

Как работает HashTable

import java.util.Hashtable;

public class HashTableExample {
    public static void main(String[] args) {
        // Создание Hashtable
        Hashtable<String, Integer> table = new Hashtable<>();
        
        // Добавление элементов
        table.put("Alice", 30);
        table.put("Bob", 25);
        table.put("Charlie", 35);
        
        // Получение значения
        System.out.println(table.get("Alice")); // 30
        
        // Проверка наличия
        System.out.println(table.containsKey("Bob")); // true
        
        // Итерация
        table.forEach((name, age) -> 
            System.out.println(name + ": " + age)
        );
        
        // Удаление
        table.remove("Charlie");
        
        // Размер
        System.out.println(table.size()); // 2
    }
}

Внутреннее устройство

HashTable использует массив бакетов (buckets). Когда добавляется элемент:

1. Вычисляется хеш ключа: hash = key.hashCode() & 0x7FFFFFFF
2. Определяется индекс: index = hash % capacity
3. На этом индексе хранится связный список (chain) элементов
4. Если произойдёт коллизия (два ключа с одинаковым хешем), элемент добавляется в цепочку

HashTable vs HashMap

// HashTable — синхронизирована, медленнее
Hashtable<String, String> hashtable = new Hashtable<>();

// HashMap — не синхронизирована, быстрее, допускает null
HashMap<String, String> hashmap = new HashMap<>();

// ConcurrentHashMap — синхронизирована, но быстрее HashTable
ConcurrentHashMap<String, String> concurrent = new ConcurrentHashMap<>();

// Collections.synchronizedMap() — оборачивает HashMap в синхронизацию
Map<String, String> syncMap = Collections.synchronizedMap(new HashMap<>());

Синхронизация HashTable

public class HashTable<K, V> extends Dictionary<K, V> {
    // Все методы синхронизированы полностью
    public synchronized V put(K key, V value) { ... }
    public synchronized V get(Object key) { ... }
    public synchronized boolean containsKey(Object key) { ... }
    public synchronized V remove(Object key) { ... }
}

Это означает, что при обращении к HashTable вся таблица блокируется. Это приводит к:

• Bottleneck — только один поток может работать с таблицей одновременно
• Low throughput — плохо масштабируется в многопоточной среде
• Deadlock risk — при неправильном использовании

Почему HashTable устаревший

// ПЛОХО: использовать HashTable
Hashtable<String, Integer> table = new Hashtable<>();

// ХОРОШО: использовать HashMap + синхронизация при необходимости
Map<String, Integer> map = new HashMap<>();
Map<String, Integer> syncMap = Collections.synchronizedMap(map);

// ЛУЧШЕ: использовать ConcurrentHashMap для многопоточности
ConcurrentHashMap<String, Integer> concurrentMap = new ConcurrentHashMap<>();

Когда может быть полезна HashTable

• Legacy код, который нельзя менять
• Простые однопоточные приложения (но лучше использовать HashMap)
• Необходимость запретить null значения

Производительность

• Get/Put/Remove: O(1) в среднем случае, O(n) в худшем (все элементы в одном bucket)
• Коэффициент загрузки (load factor): 0.75 по умолчанию
• Увеличение ёмкости: когда размер > capacity * loadFactor, ёмкость увеличивается в 2 раза + 1

Вывод

HashTable — исторический артефакт Java, оставленный для обратной совместимости. В современном коде используй:

• HashMap для простого случая
• ConcurrentHashMap для многопоточности
• Collections.synchronizedMap() если нужна полная синхронизация отдельного Map