为什么没有并发的TreeMap？

Question

我有一些与java.util.concurrent包有关的问题:

1. 为什么在java API中,一方存在非并发TreeMap,另一方存在并发 ConcurrentSkipListMap？

2. 他们为什么不叫呢ConcurrentTreeMap？说a SkipListMap包含一个TreeMap？是否安全？

例如,非并发HashMap有其并发对应物ConcurrentHashMap.为什么不会发生TreeMap？

Answer 1

为什么一边是非并发TreeMap,另一边是ConcurrentSkipListMap？

我怀疑这样做是因为并发树形结构太困难或者遇到锁定性能问题.就有序集合而言,SkipLists是非常简单的数据结构,并为树提供类似的行为和性能,因此ConcurrentSkipListMap(和Set)可能更容易并发.

我实际上更失望的是我自己没有非并发的SkipList集合.

说SkipListMap包含TreeMap是否安全？

不,它是安全地说,一个SkipList给出了项目的有序集合,给人的方面是相似的特征O(logN)进行查找,插入,删除等性能..它至少给出了业绩的概率近似.

这是关于跳过列表的好页面.它们是非常酷的数据结构.我只希望在现代编程数据结构类中讲授.

Answer 2

这个TreeMap类是这样调用的,因为它是使用平衡搜索树实现的.在ConcurrentSkipListMap被称为这种方式,因为它的使用来实现跳跃列表.为什么没有并发版本TreeMap？可能是因为很难使树结构扩展到高水平的并发性; 并发跳过列表更容易正确实现.