TreeMap возвращает ноль для значения, которое должно существовать для некоторых ключей объекта

Question

У меня проблема с TreeMap, для которого мы определили объект пользовательского ключа. Проблема в том, что после помещения нескольких объектов на карту и попытки извлечь с помощью того же ключа, который использовался для добавления на карту, я получаю нулевое значение. Я считаю, что это связано с тем, что у нас есть 2 точки данных на ключе. Одно значение всегда заполняется, а одно значение не всегда заполняется. Так что, похоже, проблема заключается в использовании compareTo и equals. К сожалению, бизнес-требования о том, как наши ключи определяют равенство, должны быть реализованы таким образом.

Я думаю, что это лучше всего иллюстрируется кодом.

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

Таким образом, проблема возникает, когда вы пытаетесь получить значение с карты после размещения на ней каких-либо предметов.

 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

Так почему же значение пусто после того, как оно просто введено? Я думаю, что алгоритм, используемый TreeMap, сортирует карту непоследовательным образом из-за того, что я использую compareTo и equals. Я открыт для предложений о том, как улучшить этот код. Спасибо

Answer 1

Ваш компаратор нарушает требование транзитивности .

Рассмотрим три объекта:

1. Объект A: sometimesPopulated="X" и alwaysPopulated="3".
2. Объект B: sometimesPopulated="Y" и alwaysPopulated="1".
3. Объект C: sometimesPopulated пуст и alwaysPopulated="2".

Используя ваш компаратор, A<B и B<C. Транзитивность требует, чтобы A<C. Однако, используя ваш компаратор, A>C.

Поскольку компаратор не выполняет свой контракт, TreeMap не может правильно выполнять свою работу.

Answer 2

Я считаю, что проблема в том, что вы обрабатываете два ключа с обоими пустыми полями как больше друг друга, что может запутать структуру.

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

Answer 3

Мне кажется, проблема в том, что вы возвращаете 1 из вашего compareTo, если одно из значений sometimesPopulated пустое или одно из значений alwaysPopulated пустое.Помните, что compareTo можно считать возвращением значения операции вычитания, а ваше не является транзитивным.(a - b) может == (b - a), даже если a! = b.

Я бы возвратил -1, если aKey sometimesPopulated не пусто, а локальный sometimesPopulated пуст,Если они одинаковы, я бы поступил так же с alwaysPopulated.

Я думаю, что ваша логика должна выглядеть примерно так:

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

Answer 4

Я думаю, что ваши методы equals, hashCode и compareTo должны использовать только поле, которое всегда заполнено.Это единственный способ гарантировать, что один и тот же объект всегда будет найден на карте, независимо от того, установлено его необязательное поле или нет.

Второй вариант, вы можете написать служебный метод, который пытается найти значение вmap и, если значение не найдено, пытается снова с тем же ключом, но с (или без) необязательным набором полей.