Map containing itself as a value;

Question

Directly from this java doc:

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 such a map.

Why would the hashcode and equals no longer be well defined on such a map?

Answer 1

The relevant part form AbstractMap.equals which is used by most Map implementations:

            Iterator<Entry<K,V>> i = entrySet().iterator();
            while (i.hasNext()) {
                Entry<K,V> e = i.next();
                K key = e.getKey();
                V value = e.getValue();
                if (value == null) {
                    if (!(m.get(key)==null && m.containsKey(key)))
                        return false;
                } else {
                    if (!value.equals(m.get(key))) // would call equals on itself.
                        return false;
                }
            }

Adding the map as a value would result in an infinite loop.

Answer 2

The full quote of the paragraph from the Java Docs is:

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 such a map.

The AbstractMap.hashCode() method uses the hash code of the key value pairs in the map to compute a hash code. Therefore the hash code generated from this method would change every time the map is modified.

The hash code is used to compute the bucket to place a new entry. If the map was used as a key within itself then the computed bucket would be different everytime a new entry is updated/removed/modified. Therefore, future lookups with the map as a key will most likely fail because a differnt bucket is computed from the hash code. Future puts may not be able to detect that the key is already present in the map and then allow multiple entries that have the same key (but in different buckets)

Answer 3

Two maps are equal if the same keys map om the same values. (In some implementations.) So to check equality, the equality of every member should be checked.

Therefore, if a map contains itself, you would get an infinite recurssion of equality checks.

The same goes for hashes, as these can be calculated dependend on the hashes of the elements in the map.

Example:

Map<Int, Object> ma;
Map<Int, Object> mb;
Map<Int, Object> mc;

ma.put(1, ma);
ma.put(2, mb);
mc.put(1, ma);
mc.put(2, mb);

As a human, we can see ma and mc are equal from the definition. A computer would see 2 maps on mb (an empty map) in both maps, which is good. It would see 1 maps on another map in both mc and ma. It checks if these maps are equal. To determine this, it checks again if the two value for 1 are equals. And again.

Note that this is not the case for all implementations. Some implementations might check equality on the location in memory the object is saved, ... But every recursive check will loop infinitely.