Hi all, I’ve been trying to understand ConcurrentSkipListMap’s design, and noticed this comment in the source [1]:
“This class implements a tree-like two-dimensionally linked skip list in which the index levels are represented in separate nodes from the base nodes holding data. There are two reasons for taking this approach instead of the usual array-based structure: 1) Array based implementations seem to encounter more complexity and overhead 2) We can use cheaper algorithms for the heavily-traversed index lists than can be used for the base lists. “ I’m curious: what were the specific overheads involved with using an array-based structure? Would these overheads still hold today? I’ve tried to dig around and wasn’t able to find any design documents or discussions that elaborate on these two points, so any pointers to these details would be welcome. Thank you! Cheers, Lalith [1] https://github.com/openjdk/jdk/blob/d8c6516c921e1f437c175875c3157ee249a5ca3c/src/java.base/share/classes/java/util/concurrent/ConcurrentSkipListMap.java#L119
