Я вижу, что ConcurrentHashMap хранит свои пары (ключ, значение) в список из Node. Однако Node может также быть организованным как TreeBin.
Таким образом, базовая структура данных ConcurrentHashMap представляет собой список, содержащий элементы, которые являются либо автономными, либо деревьями.
Почему структура данных не является ни списком, ни деревом?
В чем польза этой более сложной реализации?
Двоичная древовидная структура позволяет легко сортировать элементы либо по их естественному порядку, либо по хеш-коду, если элементы несопоставимы иным образом. Для довольно большого ведра хеширования это позволяет быстро извлекать элементы.
Однако в меньшей корзине хеширования затраты на поддержание этого дерева намного превышают любую экономию, полученную от поиска в древовидной структуре. В этом случае список будет в среднем более эффективным.
