Друзья, сегодня публикую первую часть подборки вопрос-ответ для собеседования, в ней постарался совместить часть теории и суть ответа:

1. Почему ёмкость HashMap — степень двойки?
HashMap хранит элементы в массиве bucket'ов. Чтобы определить bucket, используется:
index = (n - 1) & hash;
где n — размер массива.
Почему именно степень двойки? Потому что если n = 16:

n = 10000
n - 1 = 01111

Операция hash & 01111 оставляет только младшие 4 бита hash и гарантированно дает индекс от 0 до 15.

Если размер не степень двойки, например 10:

n - 1 = 9 = 01001

маска содержит нули между значащими битами. В результате часть битов hash вообще не участвует в выборе bucket'а, и распределение может стать хуже.
Есть и практический бонус при resize: при увеличении capacity в 2 раза элемент либо остается в том же bucket, либо перемещается на oldCapacity. Не нужно заново вычислять сложное распределение для каждого элемента.

Итого: степень двойки нужна не просто «для быстроты». Она позволяет эффективно использовать биты hash, быстро вычислять индекс через & и дешево выполнять resize.


2. HashMap vs ConcurrentHashMap — потокобезопасность и производительность
HashMap не является thread-safe. Одновременная модификация из нескольких потоков может привести к race condition и некорректному состоянию структуры.
ConcurrentHashMap специально спроектирован для конкурентного доступа. В современной Java он не использует один глобальный lock: применяются CAS и локальная синхронизация отдельных bucket'ов.
Поэтому два потока могут одновременно работать с разными участками Map, не блокируя друг друга.

HashMap
- быстро в одном потоке
- нет thread-safety

ConcurrentHashMap
- немного сложнее
- thread-safe
- лучше масштабируется при конкуренции
При этом ConcurrentHashMap запрещает null как ключ и значение.

3. Как устроен ConcurrentHashMap?
В Java 8+ ConcurrentHashMap уже не использует Segment'ы — это архитектура старых версий.
В основе современной реализации лежит массив Node[].
При вставке:
Если bucket пуст — используется CAS, чтобы атомарно установить первый элемент.
Если bucket уже занят — работа синхронизируется на конкретном bucket, а не на всей Map.
При большом количестве коллизий bucket может превратиться из списка в красно-чёрное дерево.
При resize несколько потоков могут совместно переносить элементы.
Поэтому главная идея ConcurrentHashMap:

минимизировать область блокировки и позволить нескольким потокам работать параллельно.

4. ConcurrentHashMap vs Collections.synchronizedMap()
Collections.synchronizedMap(new HashMap<>());
фактически синхронизирует доступ к Map через общий lock.
Условно:
synchronizedMap
↓
один lock
↓
вся Map

У ConcurrentHashMap блокировка гораздо более локальная, поэтому при большом количестве параллельных операций он масштабируется лучше.
synchronizedMap вполне подходит, если:
- конкуренции мало;
- Map небольшая;
- нужна простая синхронизация.

Для высококонкурентного кода обычно выбирают ConcurrentHashMap.

Важный нюанс: при итерации synchronizedMap нужно самостоятельно синхронизироваться на Map, если требуется согласованное поведение.

5. TreeMap vs HashMap
HashMap использует hash table: get / put / remove O(1) в среднем
TreeMap основан на красно-чёрном дереве: get / put / remove O(log n)
Зачем тогда нужен TreeMap?
Потому что он поддерживает отсортированный порядок ключей и операции с диапазонами:

firstKey()
lastKey()
higherKey()
lowerKey()
subMap()
headMap()
tailMap()

Поэтому выбор простой:

Нужен быстрый поиск по ключу HashMap

Нужны сортировка ключей и range-запросы TreeMap