Java：如果存在相同参数的对象，则不添加新对象

Question

这是我的对象构造函数

static class Edge {
    int source; // source node
    int destination; // destination node
    int weight; // weight of the edge
    int predecessor; // previous node
    public Edge() {};
    public Edge(int s, int d, int w) { source = s; destination = d; weight = w; }
}

现在，这是我创建一个新 Edge 对象的语句，

edges.add(new Edge(nodeStart, tempDest, tempWeight));

如果已经使用相同的参数（nodeStart，tempDest）创建了一个对象，我需要跳过该语句

基本上，我不想添加相同的边两次。

edges.add(new Edge(0, 1, tempWeight));
edges.add(new Edge(0, 1, tempWeight));

如果发生这种情况，我想确保它只添加一次，而不是添加新的相同对象。

Answer 1

这似乎是一个工厂的候选者，您可以在工厂实现中检查现有对象的标准，并返回已经存在的对象..只是我的 2 美分...

Answer 2

根据您的评论，我认为您真正需要的只是一个定制的 ArrayList。

附注，根据您对其他答案的评论，您似乎需要通过索引而不是参数进行大量随机访问。也就是说，您表明您希望按照添加边的顺序而不是通过指定唯一化参数来获取边，并且您可能希望以高度非顺序的方式访问该顺序。对于随机访问情况，此数据结构的性能将优于上面提出的自定义 Set，因为它付出了 O(N) 插入时间的高昂前期成本，其中N随着集合的大小而增长；然而，当您进行随机访问时，您将获得与 ArrayList 提供的同样出色的 O(1) 按索引检索时间。相比之下，对于自定义 Set，即使您扩展 LinkedHashSet 来维护访问顺序，您也需要花费 O(1) 插入时间，但要按顺序迭代条目，则需要 O(N)，随机访问 时间。

基本上，您预先支付唯一化约束，然后就忘记它。如果是套装，您需要稍后支付访问时间限制。当然，故事还没有结束，肯定有一个让双方都满意的解决方案。假设我们保留更多数据（啊，内存与 CPU/时间），并且在下面的数据结构中，我们不是通过列表搜索来找出是否已经有相关的 Edge，而是维护一个内部 Set。当我们进行插入时，我们首先尝试在集合中查找边（O(1)），当找不到边时，我们将其添加到集合和到列表。现在，我们必须保留一个额外的 Set （这就是内存成本），以避免在插入期间查看 List 的时间损失。

到目前为止一切都很好，但我们现在还需要定义一个哈希函数，它可以为您认为唯一的内容生成唯一的哈希代码。换句话说，我们要宽松地确保： hashCode(Edge a) != hashCode(Edge b) 其中 a != b 应该容纳一些令人难以置信的大空间a 和 b 在您定义的某种意义上是不同的。如果您定义了这样一个函数，您仍然必须支付保留集合的内存成本，但如果您真的关心插入成本，那么这可能还不错。

这是简单的直接列表概念，它很容易修改为也维护一个集合，并且如果您想使用混合方法，您可以修改下面的 contains 函数来检查集合而不是检查搜索列表。

public class EdgeArrayList extends ArrayList<Edge>{
    @Override
    public boolean add(Edge e){
        if(contains(e)){
            return false;
        }
        super.add(e);
        return true;
    }

    @Override
    public boolean contains(Object o){
        if(!(o instanceof Edge))
            return false;

        Edge e = (Edge) o;

        for(Edge item : this){
            if(item.source == e.source && 
               item.destination == e.destination && 
               item.weight == e.weight){
                return true;
            }
        }
       return false;
   }

}

然后用法将按照您的建议进行，其中已包含在 EdgeArrayList 中的边将不会被添加：

EdgeArrayList foo = new EdgeArrayList();
foo.add(new Edge(0, 0, 0));
foo.add(new Edge(0, 0, 0));

在此 foo 的末尾仅包含带有以下内容的 Edge 的第一个实例 ：所有参数设置为0（我已经测试过，它确实有效）。

这里有一些陷阱——检查新的Edge不是列表将会导致对当前列表N大小的O(N)命中。

Answer 3

使用 Set 而不是 List 来存储边缘对象并正确定义边缘 equals 和 hashCode。这将防止逻辑上相等的重复。

Answer 4

要说你不想要“重复”，首先你必须告诉java你如何认为两条边相等。您可以使用 equals 方法来执行此操作（否则 java 无法知道 Edge 类的两个对象何时相等）。
当您为对象提供 equals 方法时，您必须为对象提供 hashCode 。请参阅此问题以获取解释。
（实际上，您覆盖这些方法。这两个方法的默认实现都存在于所有java对象扩展的java.lang.Object中）

因此，首先您必须告诉java什么时候有两个边是平等的。向您的类添加一个 equals 方法和一个 hashcode 方法。有关详细信息，请参阅贾斯汀的回答。

完成后，您必须确保边缘对象集合没有重复项。为此，您可以使用HashSet。 （而不是列表。List 可以有重复项。Set 不能。这个教程给出了很好的解释）

在语句中，edges.add...,edges 应该是一个 HashSet（或任何集合的实现）。
HashSet; Edge = new HashSet();

完成此操作后，您将拥有一个唯一边缘的列表（呃，集合）。

如果您需要仅一个List而不是集合，则可以从此Set创建一个List：

ArrayList EdgesAsList = new ArrayList< ;边缘>（边缘）;

Answer 5

另一种可能的方法是仅检查 edges.contains() 在添加新边之前。

Edge newEdge = new Edge(nodeStart, tempDest, tempWeight);
if (!edges.contains(newEdge))
    edges.add(newEdge);

您需要在 Edge 中正确实现 equals 方法才能使其正常工作。有关该代码，请参阅我的其他答案。

注意：这种方式比使用Set排除重复项要慢得多。

Answer 6

正确的方法是将 edges 设为 Set。然后正确覆盖 hashcode 和 equals。

因此，您应该像这样声明 edges：

Set<Edge> egdes = new HashSet<Edge>();

并且您应该像这样实现 hashCode 和 equals：

public boolean equals(Object o) {
    if (o == null) return false;
    if (o == this) return true;
    if (!(o instanceof Edge)) return false;
    Edge oEdge = (Edge) o;
    return this.source == oEdge.source && 
           this.destination == oEdge.destination && 
           this.weight == oEdge.weight;
}

public int hashCode(){
    return source * 3 + dest * 11 + weight * 13;
}

您应该阅读如何正确实现 equals 和 hashCode。我的例子并不好。但总体的想法已经传达了。