Почему есть ConcurrentSkipListMap, но нет несинхронизированной версии?

Question

Большинство классов в Java Collections Framework по умолчанию не синхронизированы, но могут быть преобразованы во что-то синхронизированное, если вам нужно, чтобы они были поточно-ориентированными. Синхронизация снижает производительность, поэтому, если вы пишете что-то, что не должно быть поточно-ориентированным, вам лучше использовать несинхронизированную версию.

Но ConcurrentSkipListMap не следует этой схеме. Несинхронизированной версии нет. Почему не быстрее не синхронизируется SkipListMap для приложений, которые не требуют безопасности потоков, в соответствии с остальной частью Framework коллекций?

Все, что я могу думать, - это то, что самая простая реализация списка пропусков уже поточнобезопасна, поэтому не было бы никакого снижения производительности при наличии синхронизированной версии. Это имело бы некоторый смысл, но взгляд на исходный код не вполне подтверждает это. Хотя нет synchronized блоки в коде, Javadoc действительно начинается с

Этот класс реализует параллельный вариант Skip Lists...

что говорит о том, что он изо всех сил пытается изменить алгоритм, чтобы сделать его потокобезопасным. Позже мы читаем

Основная идея в этих списках - пометить "следующие" указатели удаленных узлов при удалении, чтобы избежать конфликтов с одновременными вставками...

это также звучит так, как будто есть какие-то накладные расходы.

Это просто так, что эти издержки настолько малы, что не стоит иметь не-потокобезопасный SkipListMap?

Answer 1

Хотя в Java нет SkipListMap, у него есть несинхронизированный аналог для ConcurrentSkipListMap- TreeMap

И то и другое TreeMap и ConcurrentSkipListMap реализует SortedMap, NavigableMap и сортируются в соответствии с естественным порядком ключей или компаратором, предоставленным во время создания карты, в зависимости от того, какой конструктор используется.

Но TreeMap использует красно-черное дерево внутри, а ConcurrentSkipListMap использует параллельный вариант SkipLists, как указано в java docs.

Итак, если вам нужна несинхронизированная версия ConcurrentSkipListMap, вы можете использовать TreeMap

Answer 2

ConcurrentSkipListMap - это реализация без блокировки, основанная на операциях CAS. Теоретически вам не нужно платить штраф за производительность, если вы используете его только в одном потоке. Синхронизации нет. Когда есть конфликт вместо того, чтобы блокировать реализацию, по существу, циклы для разрешения конфликта. Если нет возражений, петли отсутствуют.