Java TreeMap malfunctioning

Question

I have a TreeMap:

final Map<UserSetting, ItemsIntersectionAndComplement> _usersSimilar = new TreeMap<UserSetting, ItemsIntersectionAndComplement>(new Comparator<UserSetting>() {

@Override
public int compare(UserSetting lhs, UserSetting rhs) {

int prec = (lhs.id()).compareTo(rhs.id());
return lhs.totalMatch > rhs.totalMatch ? -1 : (lhs.totalMatch < rhs.totalMatch ) ? 1 : prec;
}
});

And when checking wether key exist, it respond false, but at a specific nth position I see that item. How is it possible? And in previous iteration item was added.

if (!_usersSimilar.containsKey(rating2.userSetting())) { // <-- CHECKING HERE EXISTENCE

    ItemsIntersectionAndComplement iiac = new ItemsIntersectionAndComplement();
    iiac.intersection.add(rating2.item());
    rating2.userSetting().totalMatch = 1;
    _usersSimilar.put(rating2.userSetting(), iiac);
} else {
  //.. SOME CODE, BUT CALL DOES NOT REACH IT
}

public class UserSetting extends _UserSetting {
    public UserSetting() {
    }

    int totalMatch;
}

Mutable keys in a map are not a good idea. [This](http://stackoverflow.com/questions/7842049/are-mutable-hashmap-keys-a-dangerous-practice) is about `HashMap`, but a similar argument can be made for `TreeMap` too. In similar cases it usually turns out `Map` is the wrong data structure altogether, and what you really need is a sorted `List`. — biziclop, Dec 21 '16 at 10:30
`lhs.totalMatch > rhs.totalMatch ? -1 : ...` — Looks like you swapped the lhs and rhs. — MC Emperor, Dec 21 '16 at 10:47

Eran · Answer 1 · 2016-12-21T10:08:24.087

if (!_usersSimilar.containsKey(rating2.userSetting())) { // <-- CHECKING HERE EXISTENCE

    ItemsIntersectionAndComplement iiac = new ItemsIntersectionAndComplement();
    iiac.intersection.add(rating2.item());
    rating2.userSetting().totalMatch = 1;
    _usersSimilar.put(rating2.userSetting(), iiac);
}

The key you are searching for in the Map and the key you put in the Map have different state, since you are updating rating2.userSetting().totalMatch inside your if clause.

Therefore it's quite possible the key you are searching for doesn't exist in the Map but the key you are adding exists in the Map.

score 1 · Answer 2 · answered Dec 21 '16 at 10:13

1

In the Javadoc for TreeMap, you read:

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.

Since you have not overridden equals, in your case the comparator is not consistent with equals. You have to equip your UserSetting class with an equals method, for example:

public boolean equals(Object o) {
    if (this == o) {
        return true;
    }
    if (!(o instanceof UserSetting)) {
        return false;
    }
    UserSetting s = (UserSetting)o;
    return id == s.id && totalMatch = s.totalMatch;
}

answered Dec 21 '16 at 10:13

Hoopje

12,677
8
34
50

2

I'd recommend using `o.getClass() != getClass()` instead of `instanceof`, as this may lead to asymmetric `equals` behaviour when it comes to subclassing... – Florian Albrecht Dec 21 '16 at 10:18
I put in `equals` in `UserSetting` but it has no effect, and `equals` not get called. Any idea why? – János Dec 21 '16 at 10:29
@János `equals` is not used by `TreeMap`. – Eran Dec 21 '16 at 11:19
Although it is a good idea to have a consistent `equals` method, I think the real problem of your code was identified by Eran. Java maps assume that keys are not modified as long a they are part of the collection, and you do modifiy a key. – Hoopje Dec 21 '16 at 11:19

Alex T · Answer 3 · 2016-12-21T11:25:36.610

Eran is right in his answer above. Your TreeMap is broken because you are updating totalMatch. This code reproduces the problem.

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class HashMapWithComparatorTest {
    public static void main(String[] args) {
        final Map<UserSetting, String> _usersSimilar = new TreeMap<UserSetting, String>(new Comparator<UserSetting>() {

            @Override
            public int compare(UserSetting lhs, UserSetting rhs) {

                int prec = (lhs.id()).compareTo(rhs.id());
                return lhs.totalMatch > rhs.totalMatch ? -1 : (lhs.totalMatch < rhs.totalMatch ) ? 1 : prec;
            }
        });

        UserSetting setting1 = new UserSetting(2, 1);
        UserSetting setting2 = new UserSetting(3, 1);
        UserSetting setting3 = new UserSetting(1, 1);
        UserSetting setting4 = new UserSetting(1, 1);
        UserSetting setting5 = new UserSetting(2, 2);

        _usersSimilar.put(setting1, "test");
        _usersSimilar.put(setting2, "test");
        _usersSimilar.put(setting3, "test");
        _usersSimilar.put(setting4, "test");


        System.out.println("Before touching totalMatch:");
        System.out.println(_usersSimilar.containsKey(setting1));
        System.out.println(_usersSimilar.containsKey(setting2));
        System.out.println(_usersSimilar.containsKey(setting3));
        System.out.println(_usersSimilar.containsKey(setting4));
        System.out.println(_usersSimilar.containsKey(setting5));

        setting1.totalMatch++;
        setting1.totalMatch++;

        setting2.totalMatch--;
        setting2.totalMatch--;

        setting3.totalMatch++;
        setting3.totalMatch++;

        setting4.totalMatch--;
        setting4.totalMatch--;

        setting5.totalMatch++;
        setting5.totalMatch++;

        System.out.println("After changing totalMatch:");
        System.out.println(_usersSimilar.containsKey(setting1));
        System.out.println(_usersSimilar.containsKey(setting2));
        System.out.println(_usersSimilar.containsKey(setting3));
        System.out.println(_usersSimilar.containsKey(setting4));
        System.out.println(_usersSimilar.containsKey(setting5));
    }

    private static class UserSetting {
        private int id;
        public int totalMatch;

        public Integer id() {
            return id;
        }

        public UserSetting(int id, int totalMatch) {
            this.id = id;
            this.totalMatch = totalMatch;
        }
    }
}

Java TreeMap malfunctioning

3 Answers3