CODEWITHSUNDEEP
javasortingdictionarytreemap
JavaKungFu
JavaKungFu

Reputation: 1314

TreeMap returning null for value that should exist for some object keys

I have an issue with a TreeMap that we have defined a custom key object for. The issue is that after putting a few objects into the map, and trying to retrieve with the same key used to put on the map, I get a null. I believe this is caused by the fact that we have 2 data points on the key. One value is always populated and one value is not always populated. So it seems like the issue lies with the use of compareTo and equals. Unfortunately the business requirement for how our keys determine equality needs to be implemented this way.

I think this is best illustrated with code. 

public class Key implements Comparable<Key> {

    private String sometimesPopulated;
    private String alwaysPopulated;

    public int compareTo(Key aKey){

        if(this.equals(aKey)){
            return 0;
        }

        if(StringUtils.isNotBlank(sometimesPopulated) && StringUtils.isNotBlank(aKey.getSometimesPopulated())){
            return sometimesPopulated.compareTo(aKey.getSometimesPopulated());
        }
        if(StringUtils.isNotBlank(alwaysPopulated) && StringUtils.isNotBlank(aKey.getAlwaysPopulated())){
            return alwaysPopulated.compareTo(aKey.getAlwaysPopulated());
        }
        return 1;
    }

    public boolean equals(Object aObject){

        if (this == aObject) {
            return true;
        }

        final Key aKey = (Key) aObject;

        if(StringUtils.isNotBlank(sometimesPopulated) && StringUtils.isNotBlank(aKey.getSometimesPopulated())){
            return sometimesPopulated.equals(aKey.getSometimesPopulated());
        }
        if(StringUtils.isNotBlank(alwaysPopulated) && StringUtils.isNotBlank(aKey.getAlwaysPopulated())){
            return alwaysPopulated.equals(aKey.getAlwaysPopulated());
        }

        return false;
    }

So the issue occurs when trying to get a value off the map after putting some items on it. 

 Map<Key, String> map = new TreeMap<Key, String>();
    Key aKey = new Key(null, "Hello");
    map.put(aKey, "world");
    //Put some more things on the map...
    //they may have a value for sometimesPopulated or not
    String value = map.get(aKey); // this = null

So why is the value null after just putting it in? I think the algorithm used by the TreeMap is sorting the map in an inconsistent manner because of the way I'm using compareTo and equals. I am open to suggestions on how to improve this code. Thanks

Upvotes: 3

Views: 4385

Answers (4)

Gray
Gray

Reputation: 116878

I think the problem is that you are returning 1 from your compareTo if either of the sometimesPopulated values is blank or either of the alwaysPopulated values is blank. Remember that compareTo can be thought of returning the value of a subtraction operation and your's is not transitive. (a - b) can == (b - a) even when a != b.

I would return -1 if the aKey sometimesPopulated is not blank and the local sometimesPopulated is blank. If they are the same then I would do the same with alwaysPopulated.

I think your logic should be something like:

public int compareTo(Key aKey){
    if(this.equals(aKey)){
        return 0;
    }

    if (StringUtils.isBlank(sometimesPopulated)) {
        if (StringUtils.isNotBlank(aKey.getSometimesPopulated())) {
            return -1;
        }
    } else if (StringUtils.isBlank(aKey.getSometimesPopulated())) {
        return 1;
    } else {
        int result = sometimesPopulated.compareTo(aKey.getSometimesPopulated());
        if (result != 0) {
           return result;
        }
    }
    // same logic with alwaysPopulated
    return 0;
}

Upvotes: 1

NPE
NPE

Reputation: 500327

Your comparator violates the transitivity requirement.

Consider three objects:

  1. Object A: sometimesPopulated="X" and alwaysPopulated="3".
  2. Object B: sometimesPopulated="Y" and alwaysPopulated="1".
  3. Object C: sometimesPopulated is blank and alwaysPopulated="2".

Using your comparator, A<B and B<C. Transitivity requires that A<C. However, using your comparator, A>C.

Since the comparator doesn't fulfil its contract, TreeMap is unable to do its job correctly.

Upvotes: 4

Peter Lawrey
Peter Lawrey

Reputation: 533500

I believe the problem is that you are treating two keys with both blank fields as greater than each other which could confuse the structure.

class Main {
    public static void main(String... args) {
        Map<Key, String> map = new TreeMap<Key, String>();
        Key aKey = new Key(null, "Hello");
        map.put(aKey, "world");
        //Put some more things on the map...
        //they may have a value for sometimesPopulated or not
        String value = map.get(aKey); // this = "world"
        System.out.println(value);
    }
}

class Key implements Comparable<Key> {
    private final String sometimesPopulated;
    private final String alwaysPopulated;

    Key(String alwaysPopulated, String sometimesPopulated) {
        this.alwaysPopulated = defaultIfBlank(alwaysPopulated, "");
        this.sometimesPopulated = defaultIfBlank(sometimesPopulated, "");
    }

    static String defaultIfBlank(String s, String defaultString) {
        return s == null || s.trim().isEmpty() ? defaultString : s;
    }

    @Override
    public int compareTo(Key o) {
        int cmp = sometimesPopulated.compareTo(o.sometimesPopulated);
        if (cmp == 0)
            cmp = alwaysPopulated.compareTo(o.alwaysPopulated);
        return cmp;
    }
}

Upvotes: 1

Olivier Croisier
Olivier Croisier

Reputation: 6149

I think your equals, hashCode and compareTo methods should only use the field that is always populated. It's the only way to ensure the same object will always be found in the map regardless of if its optional field is set or not.

Second option, you could write an utility method that tries to find the value in the map, and if no value is found, tries again with the same key but with (or without) the optional field set.

Upvotes: 0

Related Questions