TreeMap не сортируется должным образом

Question

Я пытаюсь отсортировать TreeMap по «весу». Но по какой-то причине он удаляет записи с одинаковым значением веса, даже если ключи разные.

Ниже приведен код:

class Edge  {
    int source;
    int destination;
    int weight;

    public Edge(int source, int destination, int weight) {
        this.source = source;
        this.destination = destination;
        this.weight = weight;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + destination;
        result = prime * result + source;
        result = prime * result + weight;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Edge other = (Edge) obj;
        if (destination != other.destination)
            return false;
        if (source != other.source)
            return false;
        if (weight != other.weight)
            return false;
        return true;
    }

    @Override
    public String toString() {
        return "Edge [source=" + source + ", destination=" + destination + ", weight=" + weight + "]";
    }
}

Данные HashMap:

{Край [источник = 0, пункт назначения = 1, вес = 5] = 5, Край [источник = 1, пункт назначения = 2, вес = 4] = 4, край [источник = 2, пункт назначения = 3, вес = 5] = 5, ребро [источник = 0, место назначения = 3, вес = 6] = 6, ребро [источник = 0, пункт назначения = 2, вес = 3] = 3, край [источник = 1, пункт назначения = 3, вес = 7] = 7}

Map<Edge, Integer> treemap = new TreeMap<>(new MyWeightComp());
    treemap.putAll(map);

Компаратор древовидной карты:

 class MyWeightComp implements Comparator<Edge>{

    @Override
    public int compare(Edge e1, Edge e2) {
        return e1.weight-e2.weight;
    }
}

Данные после сортировки:

{Край [источник = 0, место назначения = 2, вес = 3] = 3, Край [источник = 1, место назначения = 2, вес = 4] = 4, Край [источник = 0, место назначения = 1, вес = 5] = 5, Край [источник = 0, пункт назначения = 3, вес = 6] = 6, Край [источник = 1, пункт назначения = 3, вес = 7] = 7}

Итак, вы можете видеть, что по какой-то причине данные с одинаковым весом удаляются, даже если ключ является комбинацией источника и получателя.

Answer 1

Все Карты удаляют дубликаты, и если CompareTo возвращает 0, предполагается, что это тот же ключ.

class MyWeightComp implements Comparator<Edge> {

    @Override
    public int compare(Edge e1, Edge e2) {
        int cmp = Integer.compare(e1.weight, e2.weight); // handle overflows.
        if (cmp == 0)
            cmp = Integer.compare(e1.source, e2.source);
        if (cmp == 0)
            cmp = Integer.compare(e1.destination, e2.destination);
        return cmp;
    }
}

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

Последовательность ключей, которую необходимо обеспечить, составляет compare(a, b) == -compare(b, a) или, точнее, sign(compare(a, b)) == -sign(compare(b, a))

Answer 2

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

Прежде всего, существует ключевое различие между List и Set / Map.Списки могут содержать дубликаты, Наборы не могут содержать дубликаты, Карты не могут содержать дубликаты ключей (это относится к стандартным картам, а не, например, к multimaps ).Фактически, Наборы реализованы внутри с использованием Карт.

Как Map решает, какой элемент является дубликатом?

HashMap использует две функции Object.hashCode и Object.equals.Вы можете поместить операторы print в эти функции:

    System.out.println(String.format("Edge.hashCode.%d.%d.%d", source, destination, weight));
    System.out.println(String.format("Edge.equals.%d.%d.%d", source, destination, weight));

Давайте предположим следующий список из 7 ребер:

    List<Edge> edges = Arrays.asList(
            new Edge(0, 1, 5),
            new Edge(1, 2, 4),
            new Edge(2, 3, 5),
            new Edge(0, 3, 6),
            new Edge(0, 3, 6), // duplicate
            new Edge(0, 2, 3),
            new Edge(1, 3, 7)
    );

Теперь давайте поместим элементы в HashMap:

    Map<Edge, Integer> hashMap = new HashMap<>();
    edges.forEach(edge -> hashMap.put(edge, edge.weight));
    hashMap.forEach((edge, value) -> System.out.printf("%s%n", edge));

Полученный результат показывает, как HashMap решает, какие элементы являются дубликатами, а какие нет:

Edge.hashCode.0.1.5
Edge.hashCode.1.2.4
Edge.hashCode.2.3.5
Edge.hashCode.0.3.6
Edge.hashCode.0.3.6
Edge.equals.0.3.6
Edge.hashCode.0.2.3
Edge.hashCode.1.3.7

Вы можете видеть, что HashMap знал, что первые четыре элементане были дубликатами, потому что у них были разные хэш-коды.Пятое значение имеет тот же хеш-код, что и четвертое значение, и HashMap необходимо было подтвердить, что это действительно тот же Edge при использовании equals.HashMap будет содержать 6 элементов:

Edge [source=0, destination=1, weight=5]
Edge [source=1, destination=2, weight=4]
Edge [source=2, destination=3, weight=5]
Edge [source=0, destination=3, weight=6]
Edge [source=0, destination=2, weight=3]
Edge [source=1, destination=3, weight=7]

Давайте поместим те же самые элементы в TreeMap:

    SortedMap<Edge, Integer> treeMap = new TreeMap<>(new MyWeightComp());
    edges.forEach(edge -> treeMap.put(edge, edge.weight));
    treeMap.forEach((edge, value) -> System.out.printf("%s%n", edge));

На этот раз hashCode и equals не используются ввсе.Вместо этого используется только compare:

Edge.compare.0.1.5:0.1.5 // first item = 5
Edge.compare.1.2.4:0.1.5 // 4 is less than 5
Edge.compare.2.3.5:0.1.5 // 5 is already in the map, this item is discarded
Edge.compare.0.3.6:0.1.5 // 6 is more than 5
Edge.compare.0.3.6:0.1.5 // 6 is already in the map, this item is discarded
Edge.compare.0.3.6:0.3.6 // 6 is already in the map, this item is discarded
Edge.compare.0.2.3:0.1.5 // 3 is less than 5
Edge.compare.0.2.3:1.2.4 //   and also less than 4
Edge.compare.1.3.7:0.1.5 // 7 is more than 5
Edge.compare.1.3.7:0.3.6 //   and also more than 6

TreeMap будет содержать только 5 элементов:

Edge [source=0, destination=2, weight=3]
Edge [source=1, destination=2, weight=4]
Edge [source=0, destination=1, weight=5]
Edge [source=0, destination=3, weight=6]
Edge [source=1, destination=3, weight=7]

Как уже предлагалось, вы можете «исправить» это, сравнив не толькопо весу, но и по всем другим областям.Java8 предоставляет хороший API для сравнения «цепочек» свойств:

    Comparator<Edge> myEdgeComparator = Comparator
            .comparingInt(Edge::getWeight)
            .thenComparing(Edge::getSource)
            .thenComparing(Edge::getDestination);

Однако это может указывать на то, что вам не следовало использовать TreeMap для сортировки вообще.В конце концов, ваши первоначальные требования, вероятно, были следующими:

• сортировка по весу
• сохранение всех ребер
• порядок кромок с одинаковыми весами не важен

В этом случае вам, вероятно, следует просто использовать список и отсортировать его:

    List<Edge> list = new ArrayList<>(edges);
    list.sort(myEdgeComparator);
    list.forEach(System.out::println);

Или используя потоки Java8:

    List<Edge> list2 = edges.stream().sorted(myEdgeComparator).collect(Collectors.toList());
    list2.forEach(System.out::println);

Исходный код из этих примеров может бытьнайдено здесь .

Answer 3

TreeMap сравнение ключей с помощью компаратора.

Ваш компаратор возвращает 0 для двух ключей с одинаковым весом. Таким образом, с точки зрения TreeMap такие ключи равны.