3

Java 集合框架中的大多数类默认情况下是不同步的,但如果您需要它们是线程安全的,可以将它们制成同步的东西。同步有性能损失,所以如果你写的东西不需要是线程安全的,你最好使用非同步版本。

ConcurrentSkipListMap不遵循这个方案。没有不同步的版本。为什么SkipListMap不需要线程安全的应用程序没有更快的非同步,与集合框架的其余部分一致?

我能想到的是,跳过列表的最简单实现已经是线程安全的,因此拥有同步版本不会有性能损失。这会有些道理,但是看一下源代码并不能完全证明这一点。尽管代码中没有synchronized块,但 Javadoc 确实以

此类实现 SkipLists 的并发变体...

这表明它正在不遗余力地修改算法以使其成为线程安全的。后来,我们读到

这些列表中的基本思想是在删除时标记已删除节点的“下一个”指针,以避免与并发插入冲突......

这听起来好像涉及某种开销。

仅仅是这个开销是如此之小以至于不值得拥有一个非线程安全的SkipListMap吗?

4

2 回答 2

1

尽管 Java 没有SkipListMap,但它有一个非同步对应物ConcurrentSkipListMap- TreeMap

TreeMap和都ConcurrentSkipListMap实现SortedMap,NavigableMap并根据其键的自然顺序排序,或者通过在地图创建时提供的 Comparator 排序,具体取决于使用的构造函数。

但是 TreeMap 在内部使用红黑树,而 ConcurrentSkipListMap 使用 Java 文档中提到的 SkipLists 的并发变体。

所以,如果你想要一个不同步的版本ConcurrentSkipListMap,你可以使用TreeMap

于 2020-11-20T16:16:15.530 回答
-2

ConcurrentSkipListMap 是基于 CAS 操作的无锁实现。从理论上讲,如果您仅在单个线程中使用它,则不必支付任何性能损失。没有同步。当存在争用而不是阻塞实现时,本质上是循环来解决争用。如果没有竞争,则没有循环。

于 2014-11-13T20:13:26.360 回答