🔼 Оптимизация ArrayList

Многие недооценивают, насколько ArrayList может быть узким местом в производительности, особенно при работе с большими объёмами данных. Разберём, как оптимизировать его использование 👇

⚙️ Указывайте ёмкость при создании

По умолчанию:

List<String> list = new ArrayList<>();

ArrayList начинает с небольшой ёмкости (10 элементов) и каждый раз увеличивается в 1.5 раза, когда не хватает места. Это вызывает множество копирований массива, что замедляет работу при миллионах элементов.

✔️ Оптимальный вариант:

List<String> list = new ArrayList<>(1_000_000);

Если вы знаете (или можете оценить) количество элементов заранее — выделите память сразу. Это уменьшает количество realocations и экономит до 30–40% времени при массовых вставках.

🧠 Очищайте, а не пересоздавайте

Многие делают так:

list = new ArrayList<>();

Это создаёт новый объект и выбрасывает старый в GC. При частых операциях — GC начинает тормозить систему.

✔️ Лучше:

list.clear();

Если список используется повторно, очистка быстрее и не требует новой аллокации памяти.

⚡️ Не используйте remove() в цикле

Удаление элементов в цикле вручную — частая и дорогая ошибка.

Плохо:

for (String s : list) {
    if (s.startsWith("A")) list.remove(s);
}

❌ Такой код приведёт к ConcurrentModificationException.

Даже если использовать Iterator, это безопасно, но медленно — каждый вызов remove() сдвигает все последующие элементы (O(n) на удаление).

✔️ Хорошо:

list.removeIf(s -> s.startsWith("A"));

Метод removeIf оптимизирован под внутренние операции и работает быстрее при массовом удалении.

* Кстати, у нас есть курс по Алгоритмам и структурам данных со скидкой.

Ставь → 🔥, если интересно почитать про внутреннюю реализацию стандартных методов коллекций.

🐸 Библиотека джависта

#CoreJava

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

ConcurrentHashMap — это потокобезопасная реализация хэш-таблицы из пакета java.util.concurrent. В отличие от обычного HashMap, он допускает одновременные операции чтения и записи без глобальной блокировки всей таблицы.

📦 Базовая структура

Внутри ConcurrentHashMap хранит данные в массиве Node<K,V>[] table, где каждый элемент массива — это цепочка (связанный список или дерево).

Главная особенность:
— Вся таблица не блокируется целиком.
— Блокируется только нужный бакет при изменении.
— Для мелких структур используется synchronized на уровне ноды, для больших — tree bin locks (аналог TreeMap).

🔍 Как устроено хранение

— При вставке ключ хэшируется, чтобы равномерно распределить данные по бакетам.
— Каждая ячейка может содержать:
• Node — обычная запись (ключ/значение/ссылка).
• TreeBin — сбалансированное дерево при переполнении бакета (>8 элементов).
— Чтения (get) работают без блокировок, просто читают volatile-ссылки.

⚡️ Операции вставки и удаления

— put(K key, V value):

1. Высчитывается индекс бакета.
2. Если ячейка пустая, создаётся новая нода через CAS (Compare-And-Swap).
3. Если нет, блокируется только этот бакет (synchronized (f)), выполняется вставка.

— remove(Object key):

1. Определяется бакет.
2. Захватывается локальная блокировка на уровне бакета.
3. Узел удаляется, при необходимости структура перестраивается.

Сложность операций — O(1) в среднем случае, но с учётом блокировок.

🌊 Итераторы

Итераторы в ConcurrentHashMap — weakly consistent:
— Не выбрасывают ConcurrentModificationException.
— Видят часть изменений, сделанных другими потоками (в отличие от CopyOnWriteArrayList).
— Итерация не требует блокировок и не мешает параллельным вставкам или удалению.

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

— get() → практически O(1), без блокировок.
— put() / remove() → O(1) в среднем, но с локальной синхронизацией.
— Итерация → O(n), стабильная, но может не отражать все изменения.

⚖️ Важные нюансы

— С 8-й Java ConcurrentHashMap отказался от сегментов (Segment[]), теперь всё управляется атомарными операциями CAS и локальными синхронизациями.
— Не допускает null ключей и значений (в отличие от HashMap).
— Внутри используется LongAdder для счётчиков, чтобы избежать ложного sharing-а.

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

— Часто читаемые и обновляемые словари (например, кэш, статистика, счётчики).
— Реализация пулов подключений, очередей задач, метрик и хранилищ состояний.
— Когда важно масштабирование под многоядерные системы без глобальных блокировок.

❗️ Не использовать, если:

— Обновления редки → Collections.synchronizedMap проще и дешевле.
— Нужен строгий порядок → лучше ConcurrentSkipListMap.

🔗 Документация: JavaDoc (Java 17)

Ставьте 🔥, если хотите разбор ConcurrentSkipListMap или LinkedBlockingQueue.

🐸 Библиотека джависта

#CoreJava