ConcurrentSkipListMap design question

[Lalith Suresh]

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