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));
}

Answer 3

The problem is not with the map but with the implementation of EntryIterator and the HashSet specification that accept only not equal elements.

In case 1 and 2 maps should have two elements, you can verify that calling

map.entrySet().size();

The 'problem' is in the implementation of EntryIterator by EnumMap class, as this is a puzzle try to figure out itself why.

ps. use debugger.

Edit:

This is what you are really doing is:

    Set<Map.Entry<Sex, Sex>> set =  new HashSet<Map.Entry<Sex, Sex>>();



    Iterator<Map.Entry<Sex, Sex>> e = entrySet.iterator();
    while (e.hasNext()) {
        set.add(e.next());
    }

Remember that HashSet is implemented over HashMap, the values added to hashMap based on hashcode and equality.

BTW Everything in explained in OP link to the puzzle. The bug is in the equal method that after second invocation of method next(), change the way of working and compare the class type than a values return o == this;.