📊 Как работает ConcurrentHashMap под капотом?

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

💡 Основные механизмы:

🔹 Сегментация данных (до 8 java): Данные разделялись на сегменты, и блокировка происходила на уровне сегмента, а не всей карты. Это обеспечивало параллельный доступ к разным частям карты.

🔹 Кассовые таблицы (Java 8+): Вместо сегментов используется структура на основе Node[] – массив узлов. Это сделало структуру более гибкой. Вместо сегментации применяется механизм Fine-Grained Locking и Compare-And-Swap:
- Compare-And-Swap используется для операций записи, что позволяет избегать блокировок для большинства операций. Операции с разными бакетами могут выполняться параллельно, поскольку локальная блокировка применяется только к отдельному узлу или бакету.
- Fine-Grained Locking минимизирует область блокировок. Например, если требуется масштабирование (resize) или обработка коллизий, потоки могут продолжать работу с другими бакетами, даже если один из них временно заблокирован.
- synchronized применяется только для случаев, когда CAS не справляется (например, при реорганизации данных или сложных операциях). Это помогает поддерживать баланс между безопасностью и производительностью.

🔹 Масштабируемый массив (Resizable Array): Масштабирование в ConcurrentHashMap происходит градуально, чтобы избежать блокировки всей структуры. Новый массив создаётся с увеличенным размером, и данные переносятся постепенно, по частям. Во время переноса используется специальный узел ForwardingNode, который перенаправляет операции к новому массиву, обеспечивая корректную работу всех потоков.

📚 Основные методы:

▪️ get(Object key):
Легковесная операция, не требует блокировок. Ключ хэшируется, затем вычисляется индекс сегмента. Если в сегменте есть соответствующий узел, он возвращается.

▪️ put(K key, V value):
- Сначала используется CAS для вставки нового элемента.
- Если CAS не срабатывает (например, при наличии коллизии), включается локальная блокировка на соответствующей корзине.

▪️ computeIfAbsent/compute:
Более сложные операции, которые комбинируют вычисления с модификацией. Используются короткие локи для минимизации блокировки других потоков.

⚠️ Особенности:

- ConcurrentHashMap не допускает хранения null для ключей и значений. Это связано с невозможностью различать отсутствие значения и реальное хранение null.
- Итерации по карте предоставляют "слабо согласованные" данные, что означает, что изменения, происходящие параллельно, могут быть частично видны.

Документация

🕯 Паттерн Строитель (Builder)

Builder — это порождающий паттерн, который позволяет пошагово создавать сложные объекты. Вместо того чтобы создавать объект одним большим конструктором с множеством параметров, Builder организует процесс создания по частям, обеспечивая гибкость и читаемость кода.

Использование:

🔹 Когда нужно создать объект с большим количеством параметров, и не все из них обязательны.
🔹 Когда процесс создания объекта требует выполнения нескольких шагов или дополнительных проверок.
🔹 В случаях, когда один и тот же код должен создавать разные представления объекта (например, текстовое и графическое).

Преимущества:

1️⃣ Упрощает создание сложных объектов, делая процесс понятным и читаемым.
2️⃣ Позволяет создавать объекты с разными вариациями без необходимости дублирования кода.
3️⃣ Разделяет логику создания объекта от его структуры, что упрощает поддержку и модификацию кода.

Недостатки:

1️⃣ Увеличивает сложность кода за счёт создания дополнительных классов и методов.
2️⃣ Может быть избыточным для простых объектов с небольшим количеством параметров.
3️⃣ Требует дополнительного внимания при проектировании, чтобы избежать путаницы между обязательными и необязательными шагами.

📌 Паттерн Builder полезен, если объект имеет много параметров и их нужно задавать гибко. Например, при создании сложных конфигураций для HTTP-запросов (заголовки, тело, параметры), построении графических интерфейсов или генерации HTML-документов. Builder помогает сделать код более понятным и избежать создания конструкций с длинными и неудобными конструкторами.

💡 Глубокий взгляд на реализацию Arrays.sort()

А вы задумывались, что скрывается под капотом Arrays.sort()? Быстрая сортировка? Пузырёк? Или, может, что-то ещё?

На самом деле, Arrays.sort() – это больше, чем просто сортировка. Этот метод использует адаптивные алгоритмы и оптимизации, которые подстраиваются под тип данных и размер массива. А главное – в его реализации предусмотрена защита от худших случаев, таких как неудачное распределение данных, чтобы всегда обеспечивать стабильную производительность.

1️⃣ Примитивы: Dual-Pivot Quicksort

Для массивов примитивных типов (int, double и т.д.) используется Dual-Pivot Quicksort. Он выбирает два опорных элемента, которые делят массив на три части: элементы меньше первого опорного, между опорными и больше второго, с последующей рекурсивной сортировкой каждой части.

🔍 Как это выглядит:

if (arr[left] > arr[right]) {
    swap(arr, left, right); 
}
int pivot1 = arr[left];
int pivot2 = arr[right];

int i = left + 1, lt = left + 1, gt = right - 1;
while (i <= gt) {
    if (arr[i] < pivot1) {
        swap(arr, i++, lt++); // Элементы меньше первого опорного
    } else if (arr[i] > pivot2) {
        swap(arr, i, gt--);   // Элементы больше второго опорного
    } else {
        i++; // Элементы между опорными
    }
}
swap(arr, left, --lt);
swap(arr, right, ++gt);

📌 Почему это эффективно?

- Использование двух опорных элементов снижает глубину рекурсии.
- Разбиение на три части позволяет сбалансировать массив быстрее, чем в классическом Quicksort.
- Работает in-place, избегая лишних выделений.
- Даже на отсортированных или случайных данных Dual-Pivot Quicksort показывает стабильную производительность.

2️⃣ Ссылочные типы: Timsort

Если вы сортируете объекты (String, Integer и т.д.), то под капотом работает Timsort – гибридный алгоритм, который сочетает Merge Sort и Insertion Sort. Он адаптивно обрабатывает массивы, находя уже отсортированные последовательности (run'ы) и минимизируя количество операций для их слияния.

🔍 Как это выглядит:

int runLen = 32; // Минимальная длина run
for (int i = 0; i < array.length; i += runLen) {
    insertionSort(array, i, Math.min((i + runLen - 1), array.length - 1));
}

while (stackSize > 1) { 
    if (runLen[stackSize - 2] <= runLen[stackSize - 1]) {
        mergeRun(stackSize - 2, stackSize - 1); // Слияние соседних run'ов
    }
}

📌 Почему это эффективно?

- Timsort автоматически находит уже отсортированные подмассивы, уменьшая объём работы.
- Работает с заранее выделенными буферами для быстрого слияния подмассивов.
- Сохраняет порядок равных элементов, что важно для многих задач.
- Производительность близка к O(n) на частично отсортированных данных.

3️⃣ Небольшие массивы: Insertion Sort

Для массивов с небольшим количеством элементов (до 32) используется Insertion Sort (сортировка вставками). Он работает, проходя по массиву и вставляя каждый элемент на своё место в уже отсортированной части, сдвигая элементы, которые больше текущего, вправо. Этот алгоритм применяется, так как на малых объёмах данных он оказывается быстрее более сложных методов благодаря низким накладным расходам и простоте реализации.

🔍 Как это выглядит:

for (int i = left + 1; i <= right; i++) {
    int key = array[i];
    int j = i - 1;
    while (j >= left && array[j] > key) {
        array[j + 1] = array[j];
        j--;
    }
    array[j + 1] = key;
}

📌 Почему это эффективно?

- Алгоритм не требует дополнительной памяти и выполняется in-place.
- Сложность O(n^2) на больших данных компенсируется эффективностью на длине до 32 элементов.
- Использует уже загруженные данные в кэше процессора, что ускоряет доступ к памяти.

☄️ Проверь себя

Хочешь узнать, насколько ты прокачан в разработке? Тест для айтишников, чтобы проверить знания. Отличный способ отвлечься и сравнить результаты с друзьями!

👉 Пройти

💡 Как избежать катастрофы при переходе на PostgreSQL: руководство по спасению базы данных

Переход на PostgreSQL — это не просто замена одного инструмента другим. Неправильный подход может привести к потере данных, снижению производительности и длительным простоям. Особенно это касается хранимых процедур: различия между PL/pgSQL и языками, такими как PL/SQL или T-SQL, могут вызывать ошибки, которые сложно обнаружить заранее.

Если вы хотите узнать, как избежать этих проблем, правильно спланировать переход и не потерять производительность, ознакомьтесь с важными советами и готовыми решениями, которые сделают миграцию безопасной и эффективной. 🚀

🔗 Читать статью
🔗 Зеркало