Stack overflow problem in HashMap.hashCode() and possible fix

[sinelaw]

Problem can be reproduced with four lines of code:

HashMap<String,Object> testMap = new HashMap<String, Object>();
testMap.put("me", testMap);
HashMap<Object,Object> testMap2 = new HashMap<Object, Object>();
testMap2.put(testMap, null); // <---- causes a stack overflow.


The problem is in the following line of HashMap.hashCode():
> result += keyHashCode(unmaskNullKey(key)) ^ valueHashCode(values[i]);
since value[i] could equal this (the current instance), valueHashCode
will recurse into hashCode causing an infinite recursion and stack
overflow. It can be fixed by not calling valueHashCode on values that
are this instance.

Is this a bug or a "feature"?


Thanks!

EntireOne, Inc.

[sinelaw]

BTW, here's my temporary workaround:

private class FixedHashMap extends HashMap {
protected boolean _inHashCode = false;
@Override
public int hashCode() {
int result = 0;
if (_inHashCode ) { return result; }
_inHashCode = true;
result = super.hashCode();
_inHashCode = false;
return result;

[Patrick Julien]

This behavior happens outside of GWT too in regular Java. This has
nothing to do with GWT. HashMap does not support null values or keys

> --
> http://groups.google.com/group/Google-Web-Toolkit-Contributors

[Miroslav Pokorny]

@Patrick

The reason for the StackOverflowError is one map has been added to itself, which makes no sense even in regular java. The bug is in the client code and not HashMap in regular java or GWT.

@Sinelaw
The sensible thing is to not add a map to itself and therefore the bug is inthe client code and not map. invoking equals on the broken map will also cause a SOE.

[sinelaw]

mP,
This is not a bug in the client, because this is exactly what the client in my case is trying to represent (a recursive graph of maps). It's not a "bug" to represent that structure.

However since "regular" Java does not support this (i just checked), I agree that GWT should emulate Java's behavior.

In my case I'll use the wrapper type I described above, and you're right - I'll have to override equals too.

[Thomas Broyer]

Have you seen this note in the javadoc for java.lang.Map:

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.

– http://download.oracle.com/javase/6/docs/api/java/util/Map.html

Instead of using a Map directly, maybe you should use an wrapper object that implements equals() and hashCode() independently of the content of the Map.

Or, instead of using the Map itself as the key, use a "sentinel" object (e.g. public static final Object THIS_MAP = new Object(); )

(that being said, I'm having a hard time figuring out what could represent a Map that contains itself as a key)

[sinelaw]

Thanks for the link,

Notice however that I'm not using the map as a key in itself, but as a
value in itself, and as a key in another unrelated map.

> Map that contains itself as a *key*)

[sinelaw]

Thomas - Also, regarding your suggestions the wrapper object is in
fact what I'm using for now (my second post mentioned that). But I
don't see how a sentinel would help me in my real use case of a
complex graph of circular references between maps, since it will be
hard to keep track of which sentinel represents which map.

On Jan 3, 11:36 am, Thomas Broyer <t.bro...@gmail.com> wrote:

> Map that contains itself as a *key*)

[sinelaw]

Here's my complete wrapper. It's rather simplistic and could probably use some optimization in .equals, but I didn't try an awful lot.

Comments welcome.

/**
 * A wrapper of HashMap that support recursion in values (can contain itself as a value) and still calculate
 * hashCode and equals correctly.
 */
public  class FixedHashMap<K,V> extends HashMap<K,V> {

    protected boolean _inHashCode = false;

    protected HashSet<FixedHashMap<?,?>> _inEqualsWith = new HashSet<FixedHashMap<?,?>>();

   
    @Override
    public int hashCode() {
        int result = 0;
        if (_inHashCode ) { return result; }
        _inHashCode = true;
        result = super.hashCode();
        _inHashCode = false;
        return result;
    }
   

    /**
     * Equals needs to fix the case of comparing two recursive maps. The rest is handled by the default implementation.
     */
    @Override
    public boolean equals(Object other) {
        if (this == other) {
            return true;
        }
        if (null == other) {
            return false;
        }
        if (!(other instanceof HashMap)) {
            return false;
        }
        if (!(other instanceof FixedHashMap)) {
            // We assume other is a non-recursive map,
            // and the default .equals doesn't recurse infinitely
            return super.equals(other);
        }
        // It may be a recursive map.
        FixedHashMap<?, ?> savedOther = (FixedHashMap<?, ?>) other;
        if (this._inEqualsWith.contains(savedOther)) {
            // We are already comparing ourselves with this object!
            // Return 'true' because the final result will be the conjunction ('and')
            // of this result and all the other entries. If all the other entries are equal,
            // we can say the maps are equal.
            return true;
        }
        this._inEqualsWith.add(savedOther);
        boolean res = super.equals(other);
        this._inEqualsWith.remove(savedOther);
        return res;
    }
}

[Thomas Broyer]

On Monday, January 3, 2011 10:42:28 AM UTC+1, sinelaw wrote:

Thomas - Also, regarding your suggestions the wrapper object is in
fact what I'm using for now (my second post mentioned that).

You're subclassing HashMap, not wrapping a Map.

But I
don't see how a sentinel would help me in my real use case of a
complex graph of circular references between maps, since it will be
hard to keep track of which sentinel represents which map.

yes, sorry I misread your initial 4-lines repro case.

So , I think you'd to use a wrapper object that implements equals and hashCode independently of the content of the wrapped map; something like:

// do not implement Map, as it would break the contract for Map.hashCode and Map.equals

class Wrapper<K, V> {

  private final Map<K, V> map;

  public Wrapper(Map<K,V> map) {

    this.map = map;

  }

  public final Map<K, V> get() {

    return map;

  }

  @Overrides

  public boolean equals(Object obj) {

    if (obj == this) {

      return true;

    }

    if (obj instanceof Wrapper) {

      // use identity comparison: 2 wrappers are equal if they wrap the very same map, independently of its content

      return map == ((Wrapper) obj).map;

    }

    return false;

  }

  @Overrides

  public int hashCode() {

    // not the best for performances, but at least does not violates the Object.hashCode/equals contract

    return 31;

  }

}

  

Best would probably be to use a subclass of Map that keeps a reference to the "key" object so as to maintain a 1:1 bidirectional relationship between maps and their keys (and that way, you don't even have to implement the hashCode and equals methods, the default implementations are sufficient):

class MapWithKey<K, V> extends HashMap<K, V> {

  public final class Key<K, V> {

    public MapWithKey<K, V> getMap() {

      return MapWithKey.this;

    }

  }

  private final Key<K, V> key = new Key<K, V>();

  public final Key<K, V> getKey() { return key; }

}

Then, instead of testMap2.put(testMap, null), you'd use testMap2.put(testMap.getKey(), null);