HashMap key problems

Question

I'm profiling some old java code and it appears that my caching of values using a static HashMap and a access method does not work.

Caching code (a bit abstracted):

static HashMap<Key, Value> cache = new HashMap<Key, Value>();

public static Value getValue(Key key){
    System.out.println("cache size="+ cache.size());                
    if (cache.containsKey(key)) {
        System.out.println("cache hit");
        return cache.get(key);
    } else {
        System.out.println("no cache hit");
        Value value = calcValue();
        cache.put(key, value);
        return value;
    }
}

Profiling code:

for (int i = 0; i < 100; i++)
{ 
    getValue(new Key());
}

Result output:

 cache size=0
 no cache hit
 (..)
 cache size=99
 no cache hit

It looked like a standard error in Key's hashing code or equals code. However:

 new Key().hashcode == new Key().hashcode // TRUE
 new Key().equals(new Key()) // TRUE

What's especially weird is that cache.put(key, value) just adds another value to the hashmap, instead of replacing the current one.

So, I don't really get what's going on here. Am I doing something wrong?

edit Ok, I see that in the real code the Key gets used in other methods and changes, which therefore get's reflected in the hashCode of the object in the HashMap. Could that be the cause of this behaviour, that it goes missing?

Answer 1

On a proper @Override of equals/hashCode

I'm not convinced that you @Override (you are using the annotation, right?) hashCode/equals properly. If you didn't use @Override, you may have defined int hashcode(), or boolean equals(Key), neither of which would do what is required.

---

On key mutation

If you are mutating the keys of the map, then yes, trouble will ensue. From the documentation:

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.

Here's an example:

Map<List<Integer>,String> map =
    new HashMap<List<Integer>,String>();
List<Integer> theOneKey = new ArrayList<Integer>();
map.put(theOneKey, "theOneValue");

System.out.println(map.containsKey(theOneKey)); // prints "true"
theOneKey.add(42);
System.out.println(map.containsKey(theOneKey)); // prints "false"

By the way, prefer interfaces to implementation classes in type declarations. Here's a quote from Effective Java 2nd Edition: Item 52: Refer objects by their interfaces

[...] you should favor the use of interfaces rather than classes to refer to objects. If appropriate interface types exist, then parameters, return values, variables, and fields should all be declared using interface types.

In this case, if at all possible, you should declare cache as simply a Map instead of a HashMap.

Answer 2

I'd recommend double and triple checking the equals and hashCode methods. Note that it's hashCode, not hashcode.

Answer 3

Looking at the (abstracted) code, everything seems to be in order. It may be that the actual code is not like your redacted version, and that this is more a reflection of how you expect the code to work and not what is happening in practice!

If you can post the code, please do that. In the meantime, here are some pointers to try:

• After adding a Key, use exactly the same Key instance again, and verify that it produces a cache hit.
• In your test, verify the hashcodes are equal, and that the objects are equal.
• Is the Map implementation really a HashMap? WeakHashMap will behave in the way you describe once the keys are no longer reachable.

Answer 4

I'm not sure what your Key class is, but (abstractly similarly to you) what I'd do for a simple check is:

Key k1 = new Key();
Key k2 = new Key();
System.out.println("k1 hash:" + k1.hashcode);
System.out.println("k2 hash:" + k2.hashcode);
System.out.println("ks equal:" + k1.equals(k2));
getValue(k1);
getValue(k2);

if this code shows the anomaly -- same hashcode, equal keys, yet no cache yet -- then there's cause to worry (or, better, debug your Key class;-). The way you're testing, with new Keys all the time, might produce keys that don't necessarily behave the same way.