Как реализованы потокобезопасные Map?

Как реализованы потокобезопасные Map

Потокобезопасные Map в Java позволяют безопасно работать с данными из нескольких потоков одновременно. Существует несколько реализаций с разными подходами.

1. Hashtable - синхронизированная коллекция (устаревшая)

Старый подход - синхронизация всего объекта:

// ❌ Устаревший подход
Map<String, String> map = new Hashtable<>();

// Все методы синхронизированы (locked)
map.put("key1", "value1");
String value = map.get("key1");

// Проблема: вся таблица залочена при каждой операции
// Невысокая производительность в многопоточной среде

2. Collections.synchronizedMap() - обертка

Синхронизированная обертка над обычным Map:

Map<String, String> unsafeMap = new HashMap<>();
Map<String, String> safeMap = Collections.synchronizedMap(unsafeMap);

// Использование
safeMap.put("key1", "value1");
String value = safeMap.get("key1");

// Проблема: все методы синхронизированы,
// но операции типа putIfAbsent не атомарны
if (!safeMap.containsKey("key2")) {
    safeMap.put("key2", "value2"); // Race condition!
}

3. ConcurrentHashMap - оптимальное решение

Современный подход с использованием fine-grained locking (блокировка отдельных сегментов):

Map<String, String> map = new ConcurrentHashMap<>();

// Базовые операции
map.put("key1", "value1");
String value = map.get("key1");
map.remove("key1");

// Итерация безопасна
for (String key : map.keySet()) {
    System.out.println(key);
}

// Внутренняя структура - массив сегментов (buckets)
// Каждый сегмент имеет собственную блокировку
// Позволяет множеству потоков работать одновременно

4. Внутренняя реализация ConcurrentHashMap

Разбиение на сегменты (segmentation):

// Концептуально ConcurrentHashMap работает так:
public class SimpleConcurrentHashMap<K, V> {
    
    private static final int SEGMENTS = 16;
    private final Segment<K, V>[] segments = new Segment[SEGMENTS];
    
    public V get(K key) {
        int index = hash(key) % SEGMENTS;
        // Только один сегмент используется
        return segments[index].get(key);
    }
    
    public void put(K key, V value) {
        int index = hash(key) % SEGMENTS;
        // Блокируется только нужный сегмент
        segments[index].put(key, value);
    }
    
    private static class Segment<K, V> {
        private final Object lock = new Object();
        private final Map<K, V> map = new HashMap<>();
        
        public V get(K key) {
            synchronized (lock) {
                return map.get(key);
            }
        }
        
        public void put(K key, V value) {
            synchronized (lock) {
                map.put(key, value);
            }
        }
    }
}

5. Атомарные операции в ConcurrentHashMap

Методы, которые выполняют несколько действий атомарно:

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

// putIfAbsent - установить значение, если ключа нет
// Атомарная операция - не требует дополнительной синхронизации
Integer result = map.putIfAbsent("count", 1);
if (result == null) {
    System.out.println("Значение было добавлено");
}

// computeIfAbsent - вычислить значение, если ключа нет
map.computeIfAbsent("list", k -> new ArrayList<>()).add("item");

// computeIfPresent - обновить значение, если ключ есть
map.computeIfPresent("count", (k, v) -> v + 1);

// compute - обновить значение в любом случае
map.compute("count", (k, v) -> (v == null) ? 1 : v + 1);

// replace - заменить значение
map.replace("count", 1, 2); // Только если текущее значение 1
boolean replaced = map.replace("count", 5);

6. ConcurrentHashMap Java 8+

Улучшенная реализация с использованием Node и бинарных деревьев:

// Java 8+ ConcurrentHashMap использует
// - массив Node'ов
// - связные списки для коллизий
// - красно-черные деревья при большом количестве коллизий

ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();

// forEach работает параллельно (с Java 8)
map.forEach((key, value) -> {
    System.out.println(key + ": " + value);
});

// forEachEntry для параллельной обработки
map.forEachEntry(Runtime.getRuntime().availableProcessors(), entry -> {
    System.out.println(entry);
});

7. ConcurrentSkipListMap - отсортированная

Для отсортированной потокобезопасной Map:

// ConcurrentSkipListMap использует Skip List структуру
Map<Integer, String> sortedMap = new ConcurrentSkipListMap<>();

sortedMap.put(3, "three");
sortedMap.put(1, "one");
sortedMap.put(2, "two");

// Итерирует в отсортированном порядке
for (Integer key : sortedMap.keySet()) {
    System.out.println(key); // 1, 2, 3
}

// Range операции
Map<Integer, String> subMap = sortedMap.subMap(1, 3); // 1 и 2

8. Сравнение реализаций

Реализация          | Синхронизация      | Производительность | Сортировка
--------------------|------------------|-------------------|----------
Hashtable           | Весь объект      | Низкая            | Нет
Collections.sync()  | Весь объект      | Низкая            | Нет
ConcurrentHashMap   | По сегментам     | Высокая           | Нет
ConcurrentSkipList  | Lock-free        | Средняя           | Да

9. Практический пример: счетчик

// ❌ Неправильно - не потокобезопасно
Map<String, Integer> counters = new HashMap<>();
int count = counters.getOrDefault("request", 0);
counters.put("request", count + 1); // Race condition!

// ✅ Правильно - с ConcurrentHashMap
Map<String, Integer> counters = new ConcurrentHashMap<>();
counters.compute("request", (k, v) -> (v == null) ? 1 : v + 1);

// Или с AtomicInteger
Map<String, AtomicInteger> counters = new ConcurrentHashMap<>();
counters.computeIfAbsent("request", k -> new AtomicInteger(0))
    .incrementAndGet();

10. Правила использования

// ✅ Хорошо - для многопоточного доступа
Map<String, String> map = new ConcurrentHashMap<>();
map.putIfAbsent("key", "value");

// ⚠️ Осторожно - итерация не всегда потокобезопасна
for (String key : map.keySet()) {
    // Если другой поток удалит элемент, выбросит ConcurrentModificationException
    map.remove(key);
}

// ✅ Правильно - если нужно модифицировать
Iterator<String> iter = map.keySet().iterator();
while (iter.hasNext()) {
    String key = iter.next();
    if (someCondition(key)) {
        map.remove(key);
    }
}

// ✅ Используйте computeIfPresent
map.computeIfPresent("key", (k, v) -> {
    if (shouldRemove(k)) {
        return null; // Удалит запись
    }
    return v;
});

// Никогда не полагайтесь на size() в многопоточной среде
int size = map.size(); // Может измениться в следующий момент!

Вывод: для многопоточных приложений используйте ConcurrentHashMap - это оптимальный выбор благодаря блокировке отдельных сегментов, что позволяет множеству потоков работать параллельно. Используйте атомарные методы типа putIfAbsent, compute для правильной синхронизации сложных операций.