How to use Sets as keys in Java Maps

Question

Hi,

I have a Map that uses a Set for the key type, like this:

Map<Set<Thing>, Val> map;

When I query map.containsKey(myBunchOfThings), it returns false, and I don't understand why. I can iterate through each key in the keyset and verify there is a key that (1) has the same hashCode, and (2) is equals() to myBunchOfThings.

System.out.println(map.containsKey(myBunchOfThings)); // false.
for (Set<Thing> k : map.keySet()) {
  if (k.hashCode() == myBunchOfThings.hashCode() && k.equals(myBunchOfThings) {
     System.out.println("Fail at life."); // it prints this.
  }
}

Do I just fundamentally misunderstand the contract for containsKey? Is there a secret to using sets (or more generally, collections) as keys to maps?

Answer 1

Did you modify the set after insertion? If so, it's possible the set got sorted into a different bucket than the one it's looking in. When iterating, it does find your set, because it looks in the whole map.

I believe the contract for HashMap states you're not allowed to modify the hashcode for objects used as a key,

Answer 2

Are you passing the exact set (the set you want to find) when comparing for the key?

Answer 3

You should strive to use immutable types as keys for Maps. Collections and sets are generally very easily mutable so usually are a bad idea to use this way.

If you want to use many key values as a Map key you should use a class implementation designed for that purpose, like Apache Commons Collections MultiKey.

If you really must use a Set or Collection as a key, first make it immutable (Collections.unmodifiableSet(...)) and then do not keep a reference to the mutable backing object.

Another difficulty with using Collections as keys is that they could be constructed in a different order. Only a sorted collection will have a high likely-hood of matching. For instance, if you use a sequentially ordered ArrayList but construct the list in a different way the second time it will not match the key - the hash code and order of values is different.

EDIT: I stand corrected on this statement below, never having had to use Set for a ket. I just read a portion of the hashCode implementation in AbstractHashSet. This uses a simple total of all values so is not dependent of the order. Equals also checks that one set contains all values in the other set. However, this still is true with other kinds of Collections in the Java (ArrayList order does matter).

If your collection is actually a HashSet, the creation order can matter as well. In fact a hash managed collection of any kind will be even more problematic as any capacity changes trigger a rebuild of the entire collection which can reorder the elements. Think of collisions of hashes which are stored in the order the collision occur (a simple linked chain of all elements where the transformed hash value is the same).

Answer 4

Key should not be mutated while used in the map. The Map java doc says:

Note: great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map. A special case of this prohibition is that it is not permissible for a map to contain itself as a key. While it is permissible for a map to contain itself as a value, extreme caution is advised: the equals and hashCode methods are no longer well defined on a such a map.

I knew this issue, but never made the test until now. I elaborate then a bit more:

   Map<Set<String>, Object> map  = new HashMap<Set<String>, Object>();

   Set<String> key1 = new HashSet<String>();
   key1.add( "hello");

   Set<String> key2 = new HashSet<String>();
   key2.add( "hello2");

   Set<String> key2clone = new HashSet<String>();
   key2clone.add( "hello2");

   map.put( key1, new Object() );
   map.put( key2, new Object() );

   System.out.println( map.containsKey(key1)); // true
   System.out.println( map.containsKey(key2)); // true
   System.out.println( map.containsKey(key2clone)); // true

   key2.add( "mutate" );

   System.out.println( map.containsKey(key1)); // true
   System.out.println( map.containsKey(key2)); // false
   System.out.println( map.containsKey(key2clone)); // false (*)

   key2.remove( "mutate" );

   System.out.println( map.containsKey(key1)); // true
   System.out.println( map.containsKey(key2)); // true
   System.out.println( map.containsKey(key2clone)); // true

After key2 is mutated, the map does not contains it anymore. We could think that the map "indexes" the data when they are added and we would then expect that is still contains the key2 clone (line marked with *). But funny enough, this is not the case .

So, as the java doc says, keys should not be mutated otherwise behavior is unspecified. Period.

I guess that's what happens in your case.