Когда ConcurrentSkipListSet полезен?
Я просто видел эту структуру данных на Java 6 API, и мне любопытно на предмет того, когда это был бы полезный ресурс. Я учусь для scjp экзамена, и я не вижу, что он покрыл на книге Kathy Sierra, даже при том, что я видел ложные вопросы об экзамене, которые упоминают это.
3 ответа
ConcurrentSkipListSet and ConcurrentSkipListMap are useful when you need a sorted container that will be accessed by multiple threads. These are essentially the equivalents of TreeMap and TreeSet for concurrent code.
The implementation for JDK 6 is based on High Performance Dynamic Lock-Free Hash Tables and List-Based Sets by Maged Michael at IBM, which shows that you can implement a lot of operations on skip lists atomically using compare and swap (CAS) operations. These are lock-free, so you don't have to worry about the overhead of synchronized (for most operations) when you use these classes.
There's currently no Red-Black tree based concurrent Map/Set implementation in Java. I looked through the literature a bit and found a couple papers that showed concurrent RB trees outperforming skip lists, but a lot of these tests were done with transactional memory, which isn't supported in hardware on any major architectures at the moment.
I'm assuming the JDK guys went with a skip list here because the implementation was well-known and because making it lock-free was simple and portable (using CAS). If anyone cares to clarify, please do. I'm curious.
списки пропуска - это отсортированные списки, которые можно эффективно изменять с помощью функции log (n). в этом отношении это похоже на TreeSet. однако нет ConcurrentTreeSet. я слышал, что список пропуска очень легко реализовать, наверное, поэтому.
В любом случае, когда вам нужен параллельный, отсортированный и эффективный набор, вы можете использовать ConcurrentSkipListSet
These are useful when you need a set that can safely be accessed by multiple threads simultaneously. It also provides decent performance by being weakly consistent -- inserts can be made safely while you're iterating through the Set, but there's no guarantee that your Iterator will see that insert.