CODEWITHSUNDEEP
javadictionaryset
omnilinguist
omnilinguist

Reputation: 581

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

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.

Upvotes: 9

Views: 646

Answers (3)

Stephen C
Stephen C

Reputation: 719239

@templatetypedef's answer is basically correct. You can only safely use a Set as a key in some data structure if the set's state cannot change while it is a key. If the set's state changes, the invariants of the data structure are violated and operations on it will give incorrect results.

The wrappers created using Collections.unmodifiableSet can help, but there is a hidden gotcha. If the original set is still directly reachable, the application could modify it; e.g.

public void addToMap(Set key, Object value);
    someMap.put(Collections.unmodifiableSet(key), value);
}

// but ...

Set someKey = ...
addToMap(someKey, "Hi mum");
...
someKey.add("something");  // Ooops ...

To guarantee that this can't happen, you need to make a deep copy of the set before you wrap it. That could be expensive.

Another problem with using a Set as a key is that it can be expensive. There are two general approaches to implementing key / value mappings; using hashcode method or using a compareTo method that implements an ordering. Both of these are expensive for sets.

Upvotes: 0

user41871
user41871

Reputation:

As you mention, sets can change, and even if you prevent the set from changing (i.e., the elements it contains), the elements themselves may change. Those factor into the hashcode.

Can you describe what you are trying to do in higher-level terms?

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 372982

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! :-)

Upvotes: 9

Related Questions