排序列表中有相同的值，但不同的身份

的元素，我知道有几十个类似这样的问题，但我无法找到一个答案，我的具体问题。对不起，如果我错过了 - 请告诉我在哪里看，如果它存在！排序列表中有相同的值，但不同的身份

这个问题似乎很常见的对我说：我需要通过对象的某些属性排序对象的列表，只有列表中有每个对象一次。具体来说，我正在实现A *路径查找，并需要按节点的F值排序的打开列表。

我试图用一个TreeSet与比较两个节点的F值，这样的比较：

public class NodeFComparator implements Comparator<Node> { 

    @Override 
    public int compare(Node arg0, Node arg1) { 
     return (arg0.getF() - arg1.getF()); 
    } 

}

类节点是这样看：

public class Node { 

    PathableMap parentmap; 
    Point coord; // coordinates on the map 
    private Node parent; // parent node: used by astar to backtrace shortest path 

    (etc etc) 

    /* 
    * F-value of a node is the sum of the distance from start + distance to target. 
    * The nodes are searched in the order of that value. 
    */ 
    public int getF() { 
     return getG() + getH(); 
    } 

    @Override 
    public int hashCode() { 
     final int prime = 65537; 
     return prime * coord.x + coord.y; 
    } 

    @Override 
    public boolean equals(Object obj) { 
     if (this == obj) 
      return true; 
     if (obj == null) 
      return false; 
     if (getClass() != obj.getClass()) 
      return false; 
     Node other = (Node) obj; 
     if (coord == null) { 
      if (other.coord != null) 
       return false; 
     } else if (!coord.equals(other.coord)) 
      return false; 
     return true; 
    } 

}

问题这个解决方案似乎是，如果两个不同的节点具有相同的f值（这一直发生），换句话说比较器返回0，TreeSet似乎将它视为Node1 == Node2，并且不会将第二个节点到列表或做一些其他奇怪的事情，因为我的openli st错过了应该在那里的节点。

所以，我能想到的与现有类这样做的唯一方法是使用一个简单的ArrayList和每个I节点追加到它的时间排序。

是否真的在Java或Apache的百科全书没有集合类：

通过对象的任何属性保留对象的排序列表
已经快速查找并插入次
一样简单用作其他集合类？

我不解。

来源

2014-02-27 jackthehipster

什么类节点是？如果它是你的习惯，你是否正确实现了equals/hashCode合约？ –

节点非常复杂，我在问题中添加了一个简短的版本。 – jackthehipster

如果添加第二个比较，如果getF（）等于另一个getF（），那么它应该可以解决您的问题。在那里你可以使用.toString（）并将其与其他的进行比较.toString（） – Tomas

如果您想要比较相等的元素（在本例中具有相同的f值），请不要使用集合。 A *算法通常是相对于优先级队列定义，如Java 5的出现在Java集合API提供一个PriorityQueue实现：

import java.util.PriorityQueue; 

. . . 

PriorityQueue nodes = new PriorityQueue<Node>(new NodeFComparator());

来源

2014-02-27 18:42:06

将研究，thx ...但是a * openlist不需要重复的值。 – jackthehipster

对不起，具有相同f值的值，即比较相等的值。我将编辑我的答案以反映这一点。 –

thx david。现在我明白你的意思了......在此期间，我用比较黑客做了它，但我认为你的方式更优雅。下次我会使用PriorityQueue。 – jackthehipster

你说得对，你可以使用ArrayList，而不是TreeSet的，因为它不会删除是重复（根据您传递给它的比较器）项目。

您可以添加节点到一个ArrayList，当你准备对它进行排序，调用从集合类中的方法，

Collections.sort(myList, myComparator)

来源

2014-02-27 18:27:24 ktm5124

我知道这会起作用，但是每次添加一个节点时，对这个愚蠢的列表进行排序看起来真是太浪费了......如果我使用大型地图，性能不会很好！ – jackthehipster

列表完成后，您可以对其进行排序。但是对于现代的CPU，只要你的清单不是一百万记录长，你就不必担心性能。关键是要使用最适合您的数据结构。如果你想要进行常量查找，你可以使用一个HashMap，并将其转换为一个有序的列表。 – ktm5124

我不同意你的发言。表现总是很重要。如果你不在乎，该软件很糟糕。 –

只要改变你的比较一点：

public class NodeFComparator implements Comparator<Node> { 
    @Override 
    public int compare(Node arg0, Node arg1) { 
     int result = arg0.getF() - arg1.getF(); 
     if (result == 0) 
      return arg0.hashCode() - arg1.hashCode(); 
     return result; 
    } 
}

这将返回具有不同f值的节点的正确结果，并且当节点具有相同的f值时，它们将通过它们的散列码进行比较。除了散列码之外，您可以使用其他任何独特的属性，但是我选择了散列码，因为它们几乎是唯一的，每个对象都有它们。

来源

2014-02-27 18:28:17 tbodt

是的，就像user3340630建议的一样。我认为这是一条路。谢谢。将尝试，尽快接受你的答案！ – jackthehipster

我不得不改变大卫康拉德的正确答案。他的回答在下面解释。简而言之：你的方式有时只能起作用，但是证明有大量节点不稳定（换句话说，就是大地图）。而且在较小的地图上，它可能导致探路者的越野行为。我强烈建议不要使用该技术，而是使用PriorityQueue！ – jackthehipster

如果比较方法并不一致等于你得到落实要小心哪些集合班你得使用。TreeSet在这里不是一个好的选择。一种替代方法是查看Guava库中的Multimap实现https://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Multimap

来源

2014-02-27 19:54:14

排序列表中有相同的值，但不同的身份

回答

相关问题