[JavaSpecialists 212] - Creating Sets from Maps

[JavaSpecialists 212] - Creating Sets from Maps

tuitively, it seems to me that the approach of iterating over the entry set should be much faster. The iteration is O(n). However, if the HashMap is well balanced, then we should get O(1) performance on the lookup call to get(), thus the complexity of the two approaches is the same. There might be a small difference, but they should both scale linearly. This is not true with other types of maps, such as the TreeMap. The lookup complexity is O(log n), thus the complexity of the second loop would be O(n x log n).

There are lots of maps available and for some of them, as we saw already with TreeMap and HashMap, we have corresponding set implementations. These sets are thin wrappers around the Map and thus have the same complexity and concurrency behaviour.

Now for the tip. In one of the exercises for my Concurrency Specialist Course I needed a fast, thread-safe HashSet. Initially, I used a ConcurrentHashMap with a dummy value. However, in Java 6, a method newSetFromMap() was added to the java.util.Collections class for creating new sets based on maps. The generic type parameter K of the map should be the element type inside the set and the V should be a Boolean, used to confirm the presence of the element.

Read full article from [JavaSpecialists 212] - Creating Sets from Maps