> Skiplists also win over balanced BSTs when it comes to concurrent access. Balanced Skiplists search better than plain Skiplists which may skew (but balancing

> Skiplists also win over balanced BSTs when it comes to concurrent access. Balanced Skiplists search better than plain Skiplists which may skew (but balancing itself is expensive). Also, I've have found that finger search (especially with doubly-linked skiplist with million+ entries) instead of always looking for elements from the root/head is an even bigger win. > ConcurrentSkipListMap has been in the standard library since Java 6 for exactly this reason and it holds up well under high contention An amusing observation I lifted from OCaml's implementation (which inturn quotes Donald Knuth): MSBs of PRNG values have more "randomness" than LSBs (randomness affects "balance"): https://github.com/ocaml/ocaml/blob/389121d3/runtime/lf_skiplist.c#L86 https://github.com/ocaml/ocaml/blob/389121d3/runtime/lf_skip... --- Some neat refs from our codebase: - Skip lists: Done right (2016), https://ticki.github.io/blog/skip-lists-done-right https://ticki.github.io/blog/skip-lists-done-right / https://archive.is/kwhnG https://archive.is/kwhnG - An analysis of skip lists, https://eugene-eeo.github.io/blog/skip-lists.html https://eugene-eeo.github.io/blog/skip-lists.html / https://archive.is/ffCDr https://archive.is/ffCDr - Skip lists, http://web.archive.org/web/20070212103148/http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_skip.aspx http://web.archive.org/web/20070212103148/http://eternallyco... / https://archive.is/nl3G8 https://archive.is/nl3G8