TreeMap putall issue while using new comparator

Question

TreeMap<String, Integer> map1 = new TreeMap<String, Integer>();
map1.put("A", 1); map1.put("B", 2); map1.put("C", 3);
TreeMap<String, Integer> map2 = new TreeMap<>((str1, str2) -> map1.get(str1) - map1.get(str2) > 0 ? -1 : 1);
map2.putAll(map1);
Iterator<String> iterator = map2.keySet().iterator();
    while(iterator.hasNext()) {
        String key = iterator.next();
        System.out.println(key + "  " + map2.get(key) + " " + map1.get(key));
}

Output of this is

C  null 3

B  null 2

A  null 1

Please explain why I am getting null values from map2, even after doing map2.putAll(map1)

Strangely when I iterate through entry iterator is giving the right output

    Iterator<Entry<String, Integer>> entryIterator = map2.entrySet().iterator();
    while(entryIterator.hasNext()) {
        Entry<String, Integer> entry = entryIterator.next();
        System.out.println(entry.getKey() + " " + entry.getValue());
    }

EDIT As answered issue was with comparator. It is working with

    TreeMap<String, Integer> map2 = new TreeMap<>((str1, str2) -> str1.equals(str2) ? 0 : map1.get(str1) - map1.get(str2) > 0 ? -1 : 1);

Not related to the question but your comparison logic is prone to integer overflow issues. — Chetan Kinger, Jul 17 '15 at 07:19
See http://stackoverflow.com/questions/109383/how-to-sort-a-mapkey-value-on-the-values-in-java and http://stackoverflow.com/questions/2864840/treemap-sort-by-value. — M A, Jul 17 '15 at 08:10

M A · Accepted Answer · 2015-07-17T07:22:31.950

2

You missed returning zero in the comparator when the map values are equal:

TreeMap<String, Integer> map2 = new TreeMap<>(
    new Comparator<String>() {

        @Override
        public int compare(String str1, String str2) {
            if(map1.get(str1).equals(map1.get(str2))) {
                return 0;
            }
            return map1.get(str1) - map1.get(str2) > 0 ? -1 : 1;
        }
    });

From the documentation of TreeMap:

Note that the ordering maintained by a tree map, like any sorted map, and whether or not an explicit comparator is provided, must be consistent with equals if this sorted map is to correctly implement the Map interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Map interface is defined in terms of the equals operation, but a sorted map performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal. The behavior of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface.

edited Jul 17 '15 at 07:22

answered Jul 17 '15 at 07:15

M A

71,713
13
134
174

I have not added 0, since it will override the keys in case two values are same. Anyway question is why I am getting null values, while key is there. – ankushb Jul 17 '15 at 07:17
@ankushb You're getting null because the comparator implementation is wrong again. The `TreeMap` relies on the comparator to check the existence of a key. – M A Jul 17 '15 at 07:20
@manouti This still prints *A null 1*. Also, I don't completely understand why the values are `null` when it's the keys that are the ones being sorted. – Chetan Kinger Jul 17 '15 at 07:44
@CKing The OP is sorting `map2` by value, not by key. In this case, the `TreeMap` has a comparator that is inconsistent with the `Object.equals()` method contract, hence it cannot find a value corresponding to a key. – M A Jul 17 '15 at 07:51
@manouti I skimmed through the code and assumed that the OP was sorting on the keys. Thanks for pointing that out. – Chetan Kinger Jul 17 '15 at 07:58

score 0 · Answer 2 · answered Jul 17 '15 at 07:24

Check the TreeMap source code

final Entry<K,V> getEntryUsingComparator(Object key) {
    @SuppressWarnings("unchecked")
        K k = (K) key;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = cpr.compare(k, p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
    }
    return null;
}

it using comparator to get the entry, like binary search. your comparator return 0, then TreeMap never can find the entry, so return null.

TreeMap putall issue while using new comparator

2 Answers2