> 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_skip...

---

Some neat refs from our codebase:

- Skip lists: Done right (2016), https://ticki.github.io/blog/skip-lists-done-right / https://archive.is/kwhnG

- An analysis of skip lists, https://eugene-eeo.github.io/blog/skip-lists.html / https://archive.is/ffCDr

- Skip lists, http://web.archive.org/web/20070212103148/http://eternallyco... / https://archive.is/nl3G8