TreeMap not sorting properly

user_1986787 0
Viewed 307

I am trying to sort a TreeMap according to "weight". But for some reason it is deleting entries with the same weight value even though the keys are different.

Below is the code:

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 + "]";
    }
}

Data of HashMap:

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

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

Comparator of the Treemap:

 class MyWeightComp implements Comparator<Edge>{

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

Data after sorting:

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

So you can see that, for some reason the data with the same weight is getting deleted even though the key is a combination of source and destination.

data-structures sorting java
3 Answers

All the Maps delete duplicates and if compareTo returns 0, it is assumed to be the same key.

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

If you have fields which are not important for sorting, you still have to choose an arbitrary but consistent ordering if you don't want them to be ignored for the purposes of duplicates.

The key consistency you need to ensure is compare(a, b) == -compare(b, a) or more accurately sign(compare(a, b)) == -sign(compare(b, a))

user_576950

TreeMap compare keys using comparator.

Your comparator return 0 for two keys with same weight. So from TreeMap perspective such keys are equal.

user_36569040

This has already been answered by Peter and talex. I will add a slightly deeper analysis, since you mentioned learning data structures.

First of all, there is a key difference between List and Set/Map. Lists can contain duplicates, Sets cannot contain duplicates, Maps cannot contain duplicate keys (this applies to standard Maps, not to e.g. multimaps). In fact, Sets are internally implemented using Maps.

How does a Map decide, which item is a duplicate?

HashMap uses two functions Object.hashCode and Object.equals. You can put print statements into these functions:

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

Let's assume following list of 7 Edges:

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

Now, lets put items into the 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));

The produced output shows, how the HashMap decides, which items are duplicates and which are not:

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

You can see, that the HashMap knew, that first four items were not duplicates, because they had different hashcodes. Fifth value had the same hashcode as fourth value and HashMap needed to confirm, that this was really the same Edge by using equals. HashMap will contain 6 items:

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]

Let's put same items into a 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));

This time, hashCode and equals are not used at all. Instead, only compare is used:

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 will contain only 5 items:

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]

As already suggested, you can 'fix' this by comparing not only by weight, but also by all other fields. Java8 provides a nice API for comparing "chains" of properties:

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

However, this may indicate, that you should have not used the TreeMap for sorting at all. After all, your initial requirements probably were following:

  • sort by weight
  • keep all edges
  • ordering of Edges with same weights is not important

In this case, you should probably simply use a list and sort it:

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

Or using Java8 streams:

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

Source code from these examples can be found here.

user_8596730
Related