Блог

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

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

 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 amp;amp; 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 значений одинакового размера. В других случаях это работает нормально. Когда более двух значений на карте имеют одинаковый размер, третье значение в новой отсортированной карте равно null и вызывает исключение NullPointerException при попытке получить к нему доступ.

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

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

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

Когда вы передаете a 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);
}
  

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

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

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

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

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

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

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

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

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

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

У меня была аналогичная проблема, что и у исходного плаката. У меня была древовидная карта, которую я хотел отсортировать по значению. Но когда я создал компаратор, который просматривал значение, у меня возникли проблемы из-за поломки компаратора, о котором говорил 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