Сортировка Java TreeMap по значению не работает, если более двух значений имеют одно и то же свойство сортировки

Question

Я хочу отсортировать Java TreeMap на основе некоторого атрибута значения. Чтобы быть конкретным, я хочу отсортировать TreeMap<Integer, Hashset<Integer>> на основе размера Hashset<Integer>. Для этого я сделал следующее:

A Класс компаратора:

private static class ValueComparer implements Comparator<Integer> {
    private Map<Integer, HashSet<Integer>>  map = null;
    public ValueComparer (Map<Integer, HashSet<Integer>> map){
        super();
        this.map = map;
    }

@Override
    public int compare(Integer o1, Integer o2) {
        HashSet<Integer> h1 = map.get(o1);
        HashSet<Integer> h2 = map.get(o2);

        int compare = h2.size().compareTo(h1.size());

        if (compare == 0 && o1!=o2){
            return -1;
        }
        else {
            return compare;
        }
    }
}

Пример использования:

TreeMap<Integer, HashSet<Integer>> originalMap = new TreeMap<Integer, HashSet<Integer>>();

//load keys and values into map

ValueComparer comp = new ValueComparer(originalMap);
TreeMap<Integer, HashSet<Integer>> sortedMap = new TreeMap<Integer, HashSet<Integer>>(comp);
sortedMap.putAll(originalMap);

Проблема:

Это не работает, если originalMap содержит более 2 значений одинакового размера. В других случаях все работает нормально. Когда более двух значений на карте имеют одинаковый размер, третье значение в новой отсортированной карте равно нулю и выдает исключение NullPointerException, когда я пытаюсь получить к нему доступ.

Я не могу понять, в чем проблема. Хорошо, если кто-то укажет.

Обновление: Вот пример, который работает, когда два значения имеют одинаковый размер: http://ideone.com/iFD9c В приведенном выше примере, если вы раскомментируете строки 52-54, этот код потерпит неудачу - вот в чем моя проблема.

Answer 1

Обновление: вы не можете вернуть -1 из ValueComparator только потому, что хотите избежать дублирования ключей, которые нельзя удалить.Проверьте контракт на Comparator.compare.

---

Когда вы передаете Comparator на TreeMap, вы вычисляете («новое») место для размещения записи. Ни один (вычисленный) ключ не может существовать более одного раза в TreeMap.

---

Если вы хотите отсортировать orginalMap по размеру значения, вы можете сделать это следующим образом:

public static void main(String[] args) throws Exception {

    TreeMap<Integer, HashSet<Integer>> originalMap = 
        new TreeMap<Integer, HashSet<Integer>>();

    originalMap.put(0, new HashSet<Integer>() {{ add(6); add(7); }});
    originalMap.put(1, new HashSet<Integer>() {{ add(6); }});
    originalMap.put(2, new HashSet<Integer>() {{ add(9); add(8); }});


    ArrayList<Map.Entry<Integer, HashSet<Integer>>> list = 
        new ArrayList<Map.Entry<Integer, HashSet<Integer>>>();
    list.addAll(originalMap.entrySet());

    Collections.sort(list, new Comparator<Map.Entry<Integer,HashSet<Integer>>>(){
        public int compare(Map.Entry<Integer, HashSet<Integer>> o1,
                           Map.Entry<Integer, HashSet<Integer>> o2) {

            Integer size1 = (Integer) o1.getValue().size();
            Integer size2 = (Integer) o2.getValue().size();
            return size2.compareTo(size1);
        }
    });

    System.out.println(list);
}

Answer 2

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

Подумай об этом. Чтобы получить элемент из дерева, вам необходимо выполнить сравнение, но для выполнения сравнения вам нужно получить элементы.

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

Answer 3

Ваша логика сравнения (которую я не уверен, что следую, почему вы возвращаете -1, если заданные размеры равны, но их ключи разные) не должна влиять на то, что возвращает сама карта, когда вы вызываете get(key).

Вы уверены, что не вставляете нулевые значения в исходную карту? Как выглядит этот код?

Answer 4

Ваш компаратор не соблюдает контракт компаратора: если compare(o1, o2) < 0, то compare(o2, o1) должно быть > 0.Вы должны найти детерминированный способ сравнения ваших элементов, когда оба размера одинаковы, а целые числа не идентичны.Возможно, вы могли бы использовать System.identityHashCode() целых чисел для сравнения их в этом случае.

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

Примечание: пример кода компаратора использует map и data для ссылки на ту же карту.

Answer 5

У меня была такая же проблема, как у оригинального постера. У меня был TreeMap, я хотел отсортировать по значению. Но когда я сделал компаратор, который посмотрел на стоимость, у меня возникли проблемы из-за поломки компаратора, о котором говорил JB. Я смог использовать свой собственный компаратор и все еще соблюдать контракт. Когда значение, на которое я смотрел, было равным, я вернулся к сравнению ключей. Я не заботился о порядке, если значения были равны.

    public int compare(String a, String b) {
    if(base.get(a)[0] == base.get(b)[0]){ //need to handle when they are equal
        return a.compareTo(b);
    }else if (base.get(a)[0] < base.get(b)[0]) {
        return -1;
    } else {
        return 1;
    } // returning 0 would merge keys

Answer 6

Если вы не можете использовать компаратор, который возвращает 0 с множеством, это может сработать: Добавьте все элементы в originalMap.entrySet() к ArrayList, а затем отсортируйте ArrayList, используя ValueComparer, изменив его на return 0 по необходимости.

Затем добавьте все записи в отсортированном ArrayList в LinkedHashMap.