I see that a ConcurrentHashMap stores its (key, value) pairs in a list of Node. However, a Node can also be organised as a TreeBin.
So the underlying data structure of a ConcurrentHashMap is a list which has elements that are either standalone or trees.
Why isn't the data structure either a list or a tree?
What is the usefulness of this more complicated implementation?
The binary tree structure allows for easy sorting of elements, either by their natural order, or by hash code if the items are not otherwise comparable. For a rather large hash bucket, this allows for quick retrieval of elements.
In a smaller hash bucket, however, the cost of maintaining this tree is far greater than any savings that come from searching a tree structure. In this case, a list will, on average, be more efficient.
