Является ли ConcurrentSkipListMap положил метод потокобезопасным?
Недавно во время изучения ConcurrentSkipListMap Я прошел его реализацию и обнаружил, что его метод put не является потокобезопасным. Это внутренне вызывает doPut который на самом деле добавляет элемент. Но я обнаружил, что этот метод не использует какой-либо вид блокировки, аналогичный ConcurrentHashMap,
Поэтому я хочу знать, add является потокобезопасным или нет. Глядя на метод, кажется, что он не является потокобезопасным - то есть, если этот метод выполняется двумя потоками одновременно, может возникнуть проблема.
я знаю ConcurrentSkipListMap внутренне использует структуру данных skiplist, но я ожидал add способ быть потокобезопасным. Я что-то не так понимаю? Является ConcurrentSkipListMap действительно не потокобезопасный?
3 ответа
Просто потому, что он не использует Lock не делает его небезопасным. Структура списка пропуска может быть реализована без блокировки.
Вы должны внимательно прочитать API.
... Операции вставки, удаления, обновления и доступа безопасно выполняются одновременно несколькими потоками. Итераторы слабо согласованы, возвращая элементы, отражающие состояние карты в некоторой точке во время или после создания итератора. Они не генерируют исключение ConcurrentModificationException и могут выполняться одновременно с другими операциями....
Комментарии в реализации говорят:
Учитывая использование древовидных индексных узлов, вы можете удивиться, почему вместо этого не используется какое-то дерево поиска, которое будет поддерживать несколько более быстрые операции поиска. Причина в том, что не существует известных эффективных алгоритмов вставки и удаления без блокировок для деревьев поиска. Неизменность "нисходящих" связей узлов индекса (в отличие от изменяемых "левых" полей в истинных деревьях) делает это возможным, используя только операции CAS.
Поэтому они используют некоторые низкоуровневые функции программирования с операциями сравнения и замены, чтобы внести изменения в элементарную карту. При этом они обеспечивают безопасность потоков без необходимости синхронизировать доступ.
Вы можете прочитать это более подробно в исходном коде.
Мы должны доверять Java API. И вот что говорит документация пакета java.util.concurrent:
Параллельные Коллекции
Помимо очередей, этот пакет предоставляет реализации Collection, предназначенные для использования в многопоточных контекстах: ConcurrentHashMap, ConcurrentSkipListMap, ConcurrentSkipListSet, CopyOnWriteArrayList и CopyOnWriteArraySet.