Fix tests (unordered map) for Java 8 compatibility

These tests assumed that Map iteration was ordered by keys
lexicographically.  However, Map iteration order is not guaranteed and
seems to have changed in JDK 8, so the tests did not pass anymore.  This
fix make sure we do not assume any particular order, yet check that the
Exception message contains all the expected information.