ConcurrentSkipListMap

Similar to ConcurrentHashMap but using Skip List for the datastructure to make the map sorted in order. As a result, the time complexity is:

• Add: $O(log(n))$
• Put: $O(log(n))$

[!note]
The reason that it doesn't use TreeMap (sorted map but using Red Black Tree) is because keeping a TreeMap thread safe is too difficult.

The performance though is the same $O(log(n))$