Strange Java HashMap behavior - can't find matching object

Question

I've been encountering some strange behavior when trying to find a key inside a java.util.HashMap, and I guess I'm missing something. The code segment is basically:

HashMap<Key, Value> data = ...
Key k1 = ...

Value v = data.get(k1);
boolean bool1 = data.containsKey(k1);
for (Key k2 : data.keySet()) {
    boolean bool2 = k1.equals(k2);
    boolean bool3 = k2.equals(k1);
    boolean bool4 = k1.hashCode() == k2.hashCode();
    break;
}

That strange for loop is there because for a specific execution I happen to know that data contains only one item at this point and it is k1, and indeed bool2, bool3 and bool4 will be evaluated to true in that execution. bool1, however, will be evaluated to false, and v will be null.

Now, this is part of a bigger program - I could not reproduce the error on a smaller sample - but still it seems to me that no matter what the rest of the program does, this behavior should never happen.

EDIT: I have manually verified that the hash code does not change between the time the object was inserted to the map and the time it was queried. I'll keep checking this venue, but is there any other option?

Answer 1

This behavior could happen if the hash code of the key were changed after it was inserted in to the map.

Here's an example with the behavior you described:

public class Key
{
int hashCode = 0;

@Override
public int hashCode() {
    return hashCode;
}

@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Key other = (Key) obj;
    return hashCode == other.hashCode;
}

public static void main(String[] args) throws Exception {
    HashMap<Key, Integer> data = new HashMap<Key, Integer>();
    Key k1 = new Key();
    data.put(k1, 1);

    k1.hashCode = 1;

    boolean bool1 = data.containsKey(k1);
    for (Key k2 : data.keySet()) {
        boolean bool2 = k1.equals(k2);
        boolean bool3 = k2.equals(k1);
        boolean bool4 = k1.hashCode() == k2.hashCode();

        System.out.println("bool1: " + bool1);
        System.out.println("bool2: " + bool2);
        System.out.println("bool3: " + bool3);
        System.out.println("bool4: " + bool4);

        break;
    }
}
}

Answer 2

Is this application multi-threaded? If so, another thread could change the data between the data.containsKey(k1) call and the data.keySet() call.

Answer 3

From the API description of the Map interface:

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.

Also, there are very specific requirements on the behavior of equals() and hashCode() for types used as Map keys. Failure to follow the rules here will result in all sorts of undefined behavior.

Answer 4

If equals() returns true for two objects, then hashCode() should return the same value. If equals() returns false, then hashCode() should return different values. For Reference:

http://www.ibm.com/developerworks/java/library/j-jtp05273.html

Answer 5

Perhaps the Key class looks like

Key
{
    boolean equals = false ;

    public boolean equals ( Object oth )
    {
         try
         {
              return ( equals ) ;
         }
         finally
         {
              equals = true ;
         }
    }
}

Answer 6

If you're certain the hash code does not change between the time the key is inserted and the time you do the contains check, then there is something seriously wrong somewhere. Are you sure you're using a java.util.HashMap and not a subclass of some sort? Do you know what implementation of the JVM you are using?

Here's the source code for java.util.HashMap.getEntry(Object key) from Sun's 1.6.0_20 JVM:

final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;

As you can see, it retrieves the hashCode, goes to the corresponding slot in the table, then does an equals check on each element in that slot. If this is the code you're running and the hash code of the key has not changed, then it must be doing an equals check which must be failing.

The next step would be for you to give us some more code or context - the hashCode and equals methods of your Key class at a minimum.

Alternatively, I would recommend hooking up to a debugger if you can. Watch what bucket your key is hashed to, and step through the containsKey check to see where it's failing.