Search code examples
javahashmapconcurrenthashmap

Why can ConcurrentHashMap elements also be trees

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?

Solution

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