In Java, what precautions should be taken when using a Set as a key in a Map?

Question

I'm not sure what are prevailing opinions about using dynamic objects such as Sets as keys in Maps.

I know that typical Map implementations (for example, HashMap) use a hashcode to decide what bucket to put the entry in, and that if that hashcode should change somehow (perhaps because the contents of the Set should change at all, then that could mess up the HashMap by causing the bucket to be incorrectly computed (compared to how the Set was initially inserted into the HashMap).

However, if I ensure that the Set contents do not change at all, does that make this a viable option? Even so, is this approach generally considered error-prone because of the inherently volatile nature of Sets (even if precautions are taken to ensure that they are not modified)?

It looks like Java allows one to designate function arguments as final; this is perhaps one minor precaution that could be taken?

Do people even do stuff like this in commercial/open-source practice? (put List, Set, Map, or the like as keys in Maps?)

I guess I should describe sort of what I'm trying to accomplish with this, so that the motivation will become more clear and perhaps alternate implementations could be suggested.

What I am trying to accomplish is to have something of this sort:

class TaggedMap<T, V> {
  Map<Set<T>, V> _map;
  Map<T, Set<Set<T>>> _keys;
}

...essentially, to be able to "tag" certain data (V) with certain keys (T) and write other auxiliary functions to access/modify the data and do other fancy stuff with it (ie. return a list of all entries satisfying some criteria of keys). The function of the _keys is to serve as a sort of index, to facilitate looking up the values without having to cycle through all of _map's entries.

In my case, I intend to specifically use T = String, V = Integer. Someone I talked to about this had suggested substituting a String for the Set, viz, something like:

class TaggedMap<V> {
  Map<String, V> _map;
  Map<T, Set<String>> _keys;
}

where the key in _map is of the sort "key1;key2;key3" with keys separated by delimiter. But I was wondering if I could accomplish a more generalised version of this rather than having to enforce a String with delimiters between the keys.

Another thing I was wondering was whether there was some way to make this as a Map extension. I was envisioning something like:

class TaggedMap<Set<T>, V> implements Map<Set<T>, V> {
  Map<Set<T>, V> _map;
  Map<T, Set<Set<T>>> _keys;
}

However, I was not able to get this to compile, probably due to my inferior understanding of generics. With this as a goal, can anyone fix the above declaration so that it works according to the spirit of what I had described or suggest some slight structural modifications? In particular, I am wondering about the "implements Map, V>" clause, whether it is possible to declare such a complex interface implementation.

Answer 1

You are correct that if you ensure that

1. The Set contents are not modified, and
2. The Sets themselves are not modified

That it is perfectly safe to use them as keys in a Map.

It's difficult to ensure that (1) is not violated accidentally. One option might be to specifically design the class being stored inside the Set so that all instances of that class are immutable. This would prevent anyone from accidentally changing one of the Set keys, so (1) would not be possible. For example, if you use a Set<String> as a key, you don't need to worry about the Strings inside the Set changing due to external modification.

You can make (2) possible quite easily by using the Collections.unmodifiableSet method, which returns a wrapped view of a Set that cannot be modified. This can be done to any Set, which means that it's probably a very good idea to use something like this for your keys.

Hope this helps! And if your user name means what I think it does, good luck learning every language! :-)