Bug in HashMap / ArrayList or wrong code?

Question

Tired up with trying to resolve the problem with this code:

public class MapTest {
    static class T{
        static class K{}
    }
    static Map<List<T.K>, List<String>> map = new HashMap<>();
    static List<String> test(List<T.K> list, String s){
        List<String> l = map.get(list);
        if (l == null){
            l = new ArrayList<String>();
            System.out.println("New value()");
            map.put(list, l);
        }
        l.add(s);
        return l;       
    }
    public static void main(String s[]){        
        ArrayList<T.K> list = new ArrayList<T.K>();
        test(list, "TEST");
        list.add(new T.K());
        List<String> l = test(list, "TEST1");
        System.out.println(l.size());
    }
}

It should create a new list-value for the map only once, but output is as follows:

New value
New value
1

it is something wrong happen with hashcode of the list after I insert value in it. I expect "new value" show up only once, and size will be 2, not 1. is it just JVM problem or something more general? mine one is Oracle JVM 1.8.0_65

This example shows why it is a bad idea to use mutable types a Map keys. `list.add(new T.K());` causes the list to generate a different hashcode, since it isn't empty anymore, therefore the map can't find the existing instance anymore. Btw: the JavaDoc of [`List#hashCode`](https://docs.oracle.com/javase/7/docs/api/java/util/List.html#hashCode%28%29) explains its behavior very well. — Tom, Jun 08 '16 at 18:00
In general: java standard libraries do not have bugs. If they have bugs, they are extremely subtle. Meaning: one can assume with great confidence that the library is right; and that ones ideas/assumptions ... are not. — GhostCat, Jun 08 '16 at 18:02
When you added a new T.K to your list, the toString() changed, hence why it's adding another value to your HashMap. The key is now different. Output your list to the console inside your test() method, to see what I mean. — ManoDestra, Jun 08 '16 at 18:05
@Jägermeister, that's a bit strong. I have personally found bugs in the Java standard library, as confirmed by accepted bug reports. And there are many, many bugs reported by others. Nevertheless, you are right that one's general posture should be that any misbehavior one observes is almost certainly because one's own code is bad, not because the standard library is buggy. — John Bollinger, Jun 08 '16 at 18:06
Apologies, I meant `hashCode()`. He could use `System.identityHashCode(list)`, if he wishes to return the reference. However, he shouldn't be using this kind of key IMO. http://stackoverflow.com/questions/580984/how-do-you-get-the-object-reference-of-an-object-in-java-when-tostring-and-h — ManoDestra, Jun 08 '16 at 18:16
@JohnBollinger Sure. I am coming from a probability point of view. Every software has bugs; but the longer that software is in the field; and the more people are using it ... your chances of hitting a real bug get smaller and smaller. On the other hand, I was asking my self what kind of statement would get me more "helpful flags" ;-) — GhostCat, Jun 09 '16 at 06:05

score 6 · Accepted Answer · answered Jun 08 '16 at 18:04

6

The hashcode of the list object changes when you put an item in it. You can see how the hashcode is calculated in the ArrayList.hashCode documentation.

In general, using a mutable object as the key for a map isn't going to work well. Per the Map 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.

Thus, when you add the list to the map a second time, the map doesn't see it as being "equal" to the first list (since it isn't according to .equals), so it adds it again.

answered Jun 08 '16 at 18:04

I actually don't clearly understand the idea behind calculating hash by items, but okay, thank you. I'm really tired today ;) – Павел Jun 08 '16 at 18:23
2

@Павел How would you differ List1 and List2 if you don't consider their items? – Tom Jun 08 '16 at 18:36
@Tom, I was thinking that equals make comparition independently of hashCodes, and hash is just like as usual Object.hashCode. I know I was wrong, will be more carefull then. Bad thing I already refactored my code, and then Joni mentioned that IdentityHashMap exists. I usually use object or string as a key, as it is more natural. But this time I was in need to store pairs of list and strings where strings were not unique, so I swap keys and values. As I only need sequential access, it doesn't suffer performance. But logic was broken, because I don't used IdentityHashMap, while I required to. – Павел Jun 10 '16 at 11:17

score 3 · Answer 2 · answered Jun 08 '16 at 18:43

3

If you want a map where keys are looked up by identity rather than by value, you can use the IdentityHashMap class.

answered Jun 08 '16 at 18:43

Joni

108,737
14
143
193

good note, thank you – Павел Jun 08 '16 at 19:19

Bug in HashMap / ArrayList or wrong code?

2 Answers2