Что эффективнее HashTable или ConcurrentHashMap

HashTable vs ConcurrentHashMap: Сравнение

Оба класса — потокобезопасные реализации Map для многопоточного окружения, но ConcurrentHashMap значительно эффективнее. Давайте разберём в чём различия.

HashTable

HashTable — это устаревший класс (legacy), появился в Java 1.0. Вся таблица защищена одной блокировкой (монитором).

public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V> {
    
    private Entry<?,?>[] table;
    
    // ВСЕ методы синхронизированы!
    public synchronized V put(K key, V value) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        // ... операции
        return addEntry(hash, key, value, index);
    }
    
    public synchronized V get(Object key) {
        Entry<?,?>[] tab = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        // ... операции
        return null;
    }
    
    public synchronized int size() {
        return count;
    }
}

Проблема HashTable: Блокировка охватывает ВСЮ таблицу, даже если два потока обращаются к разным ячейкам (бакетам).

Hashtable<String, Integer> ht = new Hashtable<>();

// Поток 1 блокирует ВСЕЙ таблицу
ht.put("key1", 1);

// Поток 2 должен ЖДАТЬ, хотя обращается к другому ключу
ht.put("key2", 2); // ❌ Ждёт завершения key1

ConcurrentHashMap

ConcurrentHashMap (Java 1.5+) использует более тонкую синхронизацию — сегментарную блокировку (segment-based locking, Java 1.5-1.7) или bucket-level locking (Java 8+).

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V> {
    
    // Java 8+: каждый бакет имеет свою блокировку
    static class Node<K,V> {
        volatile K key;
        volatile V val;
        Node<K,V> next;
    }
    
    transient volatile Node<K,V>[] table;
    
    // Синхронизирована только часть таблицы
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        int hash = spread(key.hashCode());
        Node<K,V>[] tab = table;
        // Блокируем только нужный бакет
        synchronized (tab[hash & (tab.length - 1)]) {
            // ... только эта ячейка заблокирована
            return value;
        }
    }
    
    // Чтение БЕЗ блокировки (volatile)
    public V get(Object key) {
        int hash = spread(key.hashCode());
        Node<K,V>[] tab = table;
        // Просто читаем (volatile read, без синхронизации)
        return null;
    }
    
    // size() не является точным (может быть примерно)
    public int size() {
        long sum = 0L;
        // Подсчитываем приблизительно
        return (int) sum;
    }
}

Преимущество ConcurrentHashMap: Разные потоки могут одновременно писать в разные бакеты.

ConcurrentHashMap<String, Integer> chm = new ConcurrentHashMap<>();

// Поток 1 блокирует только бакет с key1
chm.put("key1", 1);

// Поток 2 может одновременно работать с key2 (другой бакет)
chm.put("key2", 2); // ✓ Не ждёт key1

Сравнение: HashTable vs ConcurrentHashMap

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

import java.util.concurrent.*;

public class PerformanceComparison {
    
    public static void main(String[] args) throws InterruptedException {
        // Тест HashTable
        Hashtable<Integer, Integer> ht = new Hashtable<>();
        testMap(ht, "HashTable");
        
        // Тест ConcurrentHashMap
        ConcurrentHashMap<Integer, Integer> chm = new ConcurrentHashMap<>();
        testMap(chm, "ConcurrentHashMap");
    }
    
    static void testMap(Map<Integer, Integer> map, String name) throws InterruptedException {
        int threads = 10;
        int iterations = 100000;
        
        long start = System.nanoTime();
        
        Thread[] t = new Thread[threads];
        for (int i = 0; i < threads; i++) {
            final int threadId = i;
            t[i] = new Thread(() -> {
                for (int j = 0; j < iterations; j++) {
                    int key = (threadId * 1000) + j;
                    map.put(key, j);
                    map.get(key);
                }
            });
            t[i].start();
        }
        
        for (Thread thread : t) {
            thread.join();
        }
        
        long elapsed = System.nanoTime() - start;
        System.out.println(name + ": " + (elapsed / 1_000_000) + " ms");
    }
}

// Типичный вывод:
// HashTable: 5432 ms
// ConcurrentHashMap: 642 ms  <- в 8 раз быстрее!

Какая блокировка используется?

Java 1.5-1.7 (Segment-based):

// Таблица разделена на сегменты
HashEntry<K,V>[][] segments = new HashEntry[16][];

// Каждый сегмент имеет свою ReentrantLock
ReentrantLock[] locks = new ReentrantLock[16];

public V put(K key, V value) {
    int hash = hash(key);
    int segmentIndex = hash % segments.length;
    
    locks[segmentIndex].lock();  // Блокируем только сегмент
    try {
        // работа
    } finally {
        locks[segmentIndex].unlock();
    }
}

Java 8+ (Node-level с CAS операциями):

// Используется synchronized на конкретный узел
private static final sun.misc.Unsafe U;

final V putVal(K key, V value, boolean onlyIfAbsent) {
    int hash = spread(key.hashCode());
    Node<K,V>[] tab = table;
    int n = tab.length;
    
    int i = (n - 1) & hash;
    Node<K,V> f = tabAt(tab, i);
    
    if (f == null) {
        // CAS операция (Compare-And-Swap) без блокировки
        if (casTabAt(tab, i, null, new Node<>(hash, key, value, null))) {
            return null;
        }
    }
    
    synchronized (f) { // Блокируем только узел f
        // работа
    }
}

Итерация и ConcurrentModificationException

HashTable:

Hashtable<String, Integer> ht = new Hashtable<>();
ht.put("a", 1);
ht.put("b", 2);

// Iterator-ы безопасны для исключения
for (Map.Entry<String, Integer> e : ht.entrySet()) {
    if (e.getKey().equals("a")) {
        ht.remove("a"); // ❌ ConcurrentModificationException
    }
}

ConcurrentHashMap:

ConcurrentHashMap<String, Integer> chm = new ConcurrentHashMap<>();
chm.put("a", 1);
chm.put("b", 2);

// Iterator-ы слабо согласованы
for (Map.Entry<String, Integer> e : chm.entrySet()) {
    if (e.getKey().equals("a")) {
        chm.remove("a"); // ✓ Работает! (но может не отразиться в текущей итерации)
    }
}

Когда что использовать?

Используй ConcurrentHashMap:

• В многопоточных приложениях (modern Java код)
• Когда нужна высокая пропускная способность (throughput)
• Когда много потоков читают и пишут одновременно

HashTable избегай:

• Это legacy класс (уже не поддерживается)
• Медленнее в многопоточных сценариях
• Используй ConcurrentHashMap вместо этого

Пример: Правильная инициализация

// ❌ Плохо (legacy)
Map<String, String> map = new Hashtable<>();

// ✓ Хорошо (modern)
Map<String, String> map = new ConcurrentHashMap<>();

// ✓ Если не нужна потокобезопасность
Map<String, String> map = new HashMap<>();

Заключение

ConcurrentHashMap использует более sophisticated синхронизацию (bucket-level вместо table-level), что позволяет разным потокам работать с разными частями таблицы одновременно. Это делает его значительно эффективнее HashTable, особенно при высокой concurrency. HashTable сегодня — это только исторический артефакт, используй ConcurrentHashMap.