У меня есть несколько вопросов, связанных с пакетом java.util.concurrent;:
Почему в java-интерфейсе есть неконкурентная TreeMap с одной стороны и параллельная ConcurrentSkipListMap на странице?
Почему они не называли это ConcurrentTreeMap? Можно ли сказать, что SkipListMap содержит TreeMap?
Например, неконкурентный HashMap имеет свой параллельный экземпляр ConcurrentHashMap. Почему это не происходит для TreeMap?
Почему существует неконкурентная TreeMap с одной стороны и ConcurrentSkipListMap на другом?
Я подозреваю, что это было сделано, потому что одновременное создание древовидной структуры было слишком сложным или было связано с проблемами с блокировкой производительности. С точки зрения упорядоченных коллекций, SkipLists - это очень простые структуры данных и обеспечивают подобное поведение и производительность для деревьев.
На самом деле я больше разочарован тем, что не существует несовместимой коллекции SkipList.
Можно ли сказать, что в SkipListMap включен TreeMap?
Нет. Можно с уверенностью сказать, что SkipList дает похожие функции в терминах упорядоченного набора элементов, который дает производительность O(logN) для поиска, вставки, удаления и т.д. По крайней мере, это дает вероятностную аппроксимацию этой производительности.
Здесь хорошая страница о скипистах. Это чрезвычайно классные структуры данных. Я могу только надеяться, что они преподаются в современных классах структур данных программирования.
Класс TreeMap называется таким образом, потому что он реализован с помощью сбалансированного дерева поиска. ConcurrentSkipListMap называется так, потому что он реализован с помощью списка пропуска. Почему нет параллельной версии TreeMap? Возможно потому, что трудно создать древовидную структуру, которая масштабируется до высоких уровней concurrency; параллельный список пропусков проще реализовать правильно.