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的数据:

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

树形图的比较:

 class MyWeightComp implements Comparator<Edge>{

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

排序后的数据:

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

因此,您可以看到,由于某种原因,即使密钥是源和目标的组合,也会删除具有相同权重的数据.

先谢谢你.您的帮助.

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