Iterating over EnumMap#entrySet

Question

Enumerating over Map#entrySet doesn't work as expected for all Map implementations, specially for EnumMap, IdentityHashMap and here is the sample code from Josh Bloch's puzzler presentation (Puzzle 5) -

public class Size {

    private enum Sex { MALE, FEMALE }

    public static void main(String[] args) { 
        printSize(new HashMap<Sex, Sex>()); 
        printSize(new EnumMap<Sex, Sex>(Sex.class)); 
    }

    private static void printSize(Map<Sex, Sex> map) { 
        map.put(Sex.MALE,   Sex.FEMALE); 
        map.put(Sex.FEMALE, Sex.MALE); 
        map.put(Sex.MALE,   Sex.MALE); 
        map.put(Sex.FEMALE, Sex.FEMALE); 
        Set<Map.Entry<Sex, Sex>> set = 
            new HashSet<Map.Entry<Sex, Sex>>(map.entrySet()); 
        System.out.println(set.size()); 
    }
}

and yes that produces the wrong result -

supposed to be

 2 
 2

but produces

2 
1

but if I try with below code - it produces the correct result

UPDATE
Though the size of the resulting Set is 2 but Entries are same.

public class Test{

 private enum Sex { MALE, FEMALE } 

    public static void main(String... args){
        printSize(new HashMap<Sex, String>());
        printSize(new EnumMap<Sex, String>(Sex.class));
    }


    private static void printSize(Map<Sex, String> map) {
        map.put(Sex.MALE,   "1");
        map.put(Sex.FEMALE, "2");
        map.put(Sex.MALE,   "3");
        map.put(Sex.FEMALE, "4");
        Set<Map.Entry<Sex, String>> set =
            new HashSet<Map.Entry<Sex, String>>(map.entrySet());
        System.out.println(set.size());
    }
}

I even tried the above code with the two different enum types as key and value.

This seems to be issue only if EnumMap has a same enum as a key and value.

I would like to know why is this? or I'm missing something.why it's not fixed when ConcurrentHashMap got fixed long back?

Answer 1

Have a look at the EnumMap.EntryIterator.next() implementation. This should be enough to figure out the problem.

A clue is that the resulting set is:

[FEMALE=2, FEMALE=2]

which is not the correct result.

The effect you see is due to the EnumMap.EntryIterator.hashCode() implementation (which is the Map.Entry here). It's

h = key ^ value

This results in the same hash value for the entries produced by

map.put(Sex.MALE,   Sex.MALE); 
map.put(Sex.FEMALE, Sex.FEMALE); 

a stable 0.

or

map.put(Sex.MALE,   Sex.FEMALE); 
map.put(Sex.FEMALE, Sex.MALE);

here it's an instable (for multiple executions) int value. You will always see the effect if key and value hashs are the same value because: a ^ b == b ^ a. This results in the same hash value for the Entry.

If entries have the same hash value they end up in the same bucket of the hash table and the equals will always work as they are the same object anyway.

With this knowledge we can now also produce the same effect with other types like Integer (where we know the hashCode implementation):

map.put(Sex.MALE,   Integer.valueOf(Sex.MALE.hashCode())); 
map.put(Sex.FEMALE, Integer.valueOf(Sex.MALE.hashCode()));

[FEMALE=1671711, FEMALE=1671711]

Bonus: The EnumMap implementation breaks the equals() contract:

EnumMap<Sex, Object> enumMap = new EnumMap<Sex, Object>(Sex.class);
enumMap.put(Sex.MALE, "1");
enumMap.entrySet().iterator().next().equals(enumMap.entrySet().iterator());

Throws:

Exception in thread "main" java.lang.IllegalStateException: Entry was removed
    at java.util.EnumMap$EntryIterator.checkLastReturnedIndexForEntryUse(EnumMap.java:601)
    at java.util.EnumMap$EntryIterator.getValue(EnumMap.java:557)
    at java.util.EnumMap$EntryIterator.equals(EnumMap.java:576)
    at com.Test.main(Test.java:13)

Answer 2

EnumMap.EntryIterator.next() returns this reference. You can verify it as follows:

Iterator<? extends Map.Entry<Sex, Sex>> e = map.entrySet().iterator();
while (e.hasNext()) {
    Map.Entry<Sex, Sex> x = e.next();
    System.out.println(System.identityHashCode(x));
}