37

我有几个与java.util.concurrent包裹有关的问题：

  1. 为什么在 java API 中一侧有非并发TreeMap而另一侧有并发 ConcurrentSkipListMap？

  2. 他们为什么不叫呢ConcurrentTreeMap？可以肯定地说 aSkipListMap包括 aTreeMap吗？

例如，非并发HashMap有它的并发对应物ConcurrentHashMap。为什么它不会发生TreeMap？

4

2 回答 2

44

为什么一侧有非并发 TreeMap 而另一侧有 ConcurrentSkipListMap？

我怀疑这样做是因为使树结构并发太困难或遭受锁定性能问题。就有序集合而言，SkipLists 是非常简单的数据结构，并提供与树相似的行为和性能，因此ConcurrentSkipListMap(and Set) 可能更容易实现并发。

实际上，我对自己没有非并发的 SkipList 集合感到更加失望。

可以肯定地说 SkipListMap 包含 TreeMap 吗？

不。可以肯定地说，SkipList 在有序的项目集合方面提供了类似的特性，这些O(logN)特性为查找、插入、删除等提供了性能。至少它给出了该性能的概率近似值。

这是一个关于跳过列表的好页面。它们是非常酷的数据结构。我只能希望在现代编程数据结构课程中教授这些内容。

于 2013-07-15T14:17:51.447 回答
7

之所以这样调用该类TreeMap，是因为它是使用平衡搜索树实现的。之所以ConcurrentSkipListMap这样调用，是因为它是使用跳过列表实现的。为什么没有并发版本TreeMap？可能是因为很难创建一个可扩展到高并发级别的树结构；并发跳过列表更容易正确实现。

于 2013-07-15T14:20:57.867 回答