为什么ConcurrentSkipListSet升序迭代器比降序迭代器更快？

Question

我在ConcurrentSkipListSet上使用了descendingIterator方法.我刚检查了文档并注意到以下注释:

'升序有序视图及其迭代器比下行视图更快.

请参阅https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentSkipListSet.html#descendingIterator--

不幸的是,它没有提供任何关于此的更多信息.有什么样的性能差异？它有意义吗？为什么会有性能差异？

Answer 1

如果您查看Skip Lists的Wikipedia页面,您会发现它们实际上是一种复杂的链表,其中的链接指向列表条目的排序方向.(该图清楚地说明了......)

当您沿向前方向遍历跳过列表时,您只需按照链接进行操作即可.每次next()调用都是O(1)操作.

当您反向遍历跳过列表时,每个next()调用必须在返回最后一个键之前找到该键.这是一个O(logN)操作.

(但是,向后遍历跳过列表仍然比向后遍历单个链接列表快得多.对于每个next()调用,这将是O(N)...)

如果你在引擎盖下看,你会发现a ConcurrentSkipListSet实际上是一个包装器ConcurrentSkipListMap.在该类中,Node地图的跳过列表表示中的对象在升序键方向上单独链接链...... 它遵循(从前一个)上升迭代比下降迭代更快.

性能差异将是显着的,并且随着设置大小的增加,由于O(1)与O(logN)的差异,它将变得更加显着.