4

我在 Java 中实现了一个 A* 算法，并且我使用 TreeSet 作为保持打开列表排序的简单方法。如果您不熟悉 A*，它基本上是一个获取从 A 到 B 的最短路径的函数，并且打开列表是一个节点列表（在我的情况下Tiles）是根据它们与 B 的接近程度排序的。

我的对象实现了一个compareTo()排序功能，如下所示：

@Override
public int compareTo( Tile b ) 
{
    return ( this.f< b.f) ? -1 : ( this.f> b.f) ? 1 : 0;
}

当我尝试将一些图块添加到打开列表时，我的问题就出现了 - TreeSet 似乎用于compareTo()检查对象是否已经存在，而不是equals(). 由于两个不同Tiles的值可能具有相同的f值，因此 TreeSet 认为该对象已经存在于列表中并且不会添加它。

根据文档（或至少，我是如何阅读它的），它应该使用equals：

“如果指定的元素不存在，则将其添加到此集合。更正式地说，如果集合不包含元素 e2，则将指定的元素 e 添加到此集合，这样(e==null ? e2==null : e.equals( e2))。” （强调我的）。

如何equals()在调用add()或排序contains()时使用 TreeSet？compareTo()对于信息，我的Tile类不会覆盖该equals()函数，因此它应该获得默认的return a == b.

如果 TreeSet 无法实现我想要做的事情，那么我应该使用什么合适的集合？

4

3 回答 3

6

这是预期的行为，根据 TreeSet 文档：

请注意，如果要正确实现 Set 接口，集合维护的顺序（无论是否提供显式比较器）必须与 equals 一致。（参见 Comparable 或 Comparator 以了解与 equals 一致的精确定义。）这是因为 Set 接口是根据 equals 操作定义的，但 TreeSet 实例使用其 compareTo（或 compare）方法执行所有元素比较，所以两个从集合的角度来看，这种方法认为相等的元素是相等的。一个集合的行为是明确定义的，即使它的顺序与equals不一致；它只是不遵守 Set 接口的一般约定。

调用时无法TreeSet使用或。最好的办法是通过比较属性以及其他任何关心的属性来使您的方法与方法一致。equalsaddcontainscompareToequalsfequals

于 2013-05-16T17:11:14.390 回答
0

我希望以下示例对 SO 用户有所帮助。我有类似的情况，我处理的方式是使用 id 除了 value。就我而言，值是指频率。

请注意“填充文本”的使用 - 如果您进行字符串比较，这很重要，否则 3>11。

public int compareTo(Object o) {
		String oText= o.getValue()+"";
		oText = String.format("%20s",oText).replace(' ', '0')+o.getName();
		paddedText = this.value +""; 
		paddedText=String.format("%20s",paddedText).replace(' ', '0') + this.name;
	        return oText.compareTo(paddedText);
	}

于 2015-01-08T16:36:32.913 回答
0

这里的答案已经让我创造了这个。我将把它留在这里，因为似乎仍然只有解决方案的要点。

    @Override
    public int compare(TileState lhs, TileState rhs) {
        int compare = (lhs.getTaxicab + lhs.mMoves.size())
                - (rhs.getTaxicab + rhs.mMoves.size());
        if (compare == 0 && !lhs.equals(rhs)) return 1;
        return compare;
    }

当您的比较方法返回 0 时，您只需要担心。

如果是这种情况并且 equals 将返回 false，则返回 0 以外的任何值。

于 2015-10-10T11:33:54.277 回答