Concurrent hashmap size() method complexity

Question

I'm wondering if the size() method invoked on ConcurrentHashMap is of the same complexity as the size() method for usual HashMap.

Answer 1

It isn't. In my version of the JDK, HashMap.size() has O(1) complexity, whereas ConcurrentHashMap.size() in the best case has to iterate over the segments. In the worst case it will lock all segments, which can be a pretty expensive operation in a multithreaded scenario.

Of course, which is faster is a different question altogether. The answer largely depends on how many threads are accessing the map, and what it is exactly that they are doing.