212Creating Sets from Maps

Author: Dr. Heinz M. KabutzDate: 2013-07-19Java Version: 6Category: Language

Abstract: Maps and Sets in Java have some similarities. In this newsletter we show a nice little trick for converting a map class into a set.

Welcome to the 212th issue of The Java(tm) Specialists' Newsletter, sent to you from the wonderful Island of Crete. Three weeks ago, I had the great privilege of being interviewed for Greek citizenship. The interview was in Greek, which meant I had to be able to both understand the question and then formulate an answer in at least passable Greek. I also had to be able to read and write Greek. I started learning a bit of Greek to impress my then future father-in-law in 1991. I have also lived in Greece for the last seven years. So if I had any brain cells at all, I really should have aced the interview. Unfortunately my worst subjects at school were history and geography, which most of the questions were about. As of writing, I do not know whether I passed or failed. All I know is that I enjoyed the panel interview with five examiners. And I think they also had fun, since they kept me there for 50 minutes. The other candidates were done in just 25. We ended up talking about Java, our Cretan Java Unconference and many other topics that were not really in their set of questions. If I failed, I'll be invited back next year again for another fun session of discussing Greek history, politics and geography.

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

Creating Sets from Maps

Seeing that it is summer here in Crete, this will be a short newsletter. Just one small tip that I picked up a few months ago and that has surprised quite a few people.

You probably know that the HashSet is just a wrapper around the HashMap, with the Set methods exposed. Similarly, the TreeSet is a wrapper around the TreeMap. The Map does not allow us to iterate over it directly. Thus the following would not work:

Map<String, Double> salaries = new HashMap<>();
for(double salary : salaries) { // does not compile
}

We can iterate over the set of keys, over the collection of values or over the set of entries. Values can have duplicates, which is why a collection is returned. Keys can never have duplicates, so both the keys and the entries can be returned as sets.

Thus if we wanted to iterate over just the values, we could do this:

Map<String, Double> salaries = new HashMap<>();
for (double salary : salaries.values()) {
}

Or over the keys would be:

Map<String, Double> salaries = new HashMap<>();
for (String name : salaries.keySet()) {
}

And lastly, over the entries would be:

Map<String, Double> salaries = new HashMap<>();
for (Map.Entry<String, Double> entry : salaries.entrySet()) {
  String name = entry.getKey();
  double salary = entry.getValue();
}

An approach I have often seen is when programmers get the keySet and then iterate through the set to find the values with get(), such as:

Map<String, Double> salaries = new HashMap<>();
for (String name : salaries.keySet()) { // less efficient way to
  double salary = salaries.get(name);   // iterate over entries
}

Intuitively, 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.

import java.util.*;
import java.util.concurrent.*;

public class ConcurrentSetTest {
  public static void main(String[] args) {
    Set<String> names = Collections.newSetFromMap(
        new ConcurrentHashMap<String, Boolean>()
    );
    names.add("Brian Goetz");
    names.add("Victor Grazi");
    names.add("Heinz Kabutz");
    names.add("Brian Goetz");
    System.out.println("names = " + names);
  }
}

The newSetFromMap() method obviously only exposes the methods that are in Set. Thus if your map has a richer interface than the standard Map, you would need to still write your own wrapper for it.

I hope you enjoyed this little snippet of information. If you ever looked for the ConcurrentHashSet, now you know how to get one.

Kind regards

Heinz

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive