Почему нет параллельной TreeMap?

У меня есть несколько вопросов, связанных с пакетом java.util.concurrent;:

  • Почему в java-интерфейсе есть неконкурентная TreeMap с одной стороны и параллельная ConcurrentSkipListMap на странице?

  • Почему они не называли это ConcurrentTreeMap? Можно ли сказать, что SkipListMap содержит TreeMap?

Например, неконкурентный HashMap имеет свой параллельный экземпляр ConcurrentHashMap. Почему это не происходит для TreeMap?

Ответы

Ответ 1

Почему существует неконкурентная TreeMap с одной стороны и ConcurrentSkipListMap на другом?

Я подозреваю, что это было сделано, потому что одновременное создание древовидной структуры было слишком сложным или было связано с проблемами с блокировкой производительности. С точки зрения упорядоченных коллекций, SkipLists - это очень простые структуры данных и обеспечивают подобное поведение и производительность для деревьев.

На самом деле я больше разочарован тем, что не существует несовместимой коллекции SkipList.

Можно ли сказать, что в SkipListMap включен TreeMap?

Нет. Можно с уверенностью сказать, что SkipList дает похожие функции в терминах упорядоченного набора элементов, который дает производительность O(logN) для поиска, вставки, удаления и т.д. По крайней мере, это дает вероятностную аппроксимацию этой производительности.

Здесь хорошая страница о скипистах. Это чрезвычайно классные структуры данных. Я могу только надеяться, что они преподаются в современных классах структур данных программирования.

Ответ 2

Класс TreeMap называется таким образом, потому что он реализован с помощью сбалансированного дерева поиска. ConcurrentSkipListMap называется так, потому что он реализован с помощью списка пропуска. Почему нет параллельной версии TreeMap? Возможно потому, что трудно создать древовидную структуру, которая масштабируется до высоких уровней concurrency; параллельный список пропусков проще реализовать правильно.