在Java中判断ArrayList是否包含一个对象的最有效方法是什么？

Question

我在Java中有一个对象的ArrayList。这些对象有四个字段，其中两个字段用于判断该对象是否等同于另一个对象。鉴于这两个字段，我正在寻找最有效的方法来确定该数组是否包含该对象。

问题在于这些类是根据XSD对象生成的，因此我无法修改类本身以覆盖.equals方法。

除了循环遍历并手动比较每个对象的这两个字段，然后在找到时跳出外，是否有更好的方法？这种方法看起来很混乱，我正在寻找更好的方法。

编辑：ArrayList来自未组合为对象的SOAP响应。

- Parrots

---

也许 ArrayList.indexOf() 是最清晰和有效的方法。 - Siamak

Answer 1

这取决于你需要多么高效。简单地迭代列表寻找满足某个条件的元素是O(n)的，但如果你能实现Equals方法，ArrayList.Contains也是O(n)的。如果你不是在循环或内部循环中进行这个过程，这种方法可能就可以了。

如果你真的需要非常高效的查找速度，需要做两件事：

1. 绕过生成的类：编写一个适配器类，可以包装生成的类，并基于这两个字段实现equals()（假设它们是公共的）。不要忘记还要实现hashCode()(*)。
2. 使用该适配器包装每个对象并将其放入HashSet中。HashSet.contains()具有恒定的访问时间，即O(1)，而不是O(n)。

当然，构建此HashSet仍然具有O(n)成本。只有当构建HashSet的成本与你需要执行的所有contains()检查的总成本相比可以忽略时，你才会获得任何收益。尝试构建一个没有重复项的列表就是这样一种情况。

---

* () 实现hashCode()最好是通过对用于equals实现的相同字段的哈希码进行异或(^运算符)运算来完成，但乘以31以降低异或得到0的概率。

- wcoenen

---

"HashSet.contains() 具有恒定的访问时间，即 O(1)" -- 你能指出一个证明吗？这不是非常依赖于哈希函数吗？如果不是，为什么不只是说“在实践中很快”？否则，我认为你正在传播错误信息（虽然可能是出于最好的意图 :)) - Jonas Kölker

根据文档，这个类在哈希函数将元素正确地分散在桶中的情况下，提供了基本操作（添加、删除、包含和大小）的常数时间性能。 - Wim Coenen

@Jonas，一个糟糕的hashCode()实现会导致访问时间变慢，但任何算法文本（特别是许多Collections数据结构所基于的CLR(S)文本- http://www.amazon.com/Introduction-Algorithms-Third-Thomas-Cormen/dp/0262033844/）都会告诉你，基于哈希的数据结构在查找时是O(1)的。重要的是要意识到，O(1)不表示一步查找，而是与数据结构的大小无关的查找。因此，即使hashCode()较差，查找时间仍为O(1)。Wim没有传播错误信息，事实上他说的很准确。 - dimo414

Answer 2

你可以使用Java内置的排序和二分查找方法中的Comparator。假设你有一个像这样的类，其中a和b是你想用来进行排序的字段：

class Thing { String a, b, c, d; }

您需要定义自己的比较器（Comparator）：

Comparator<Thing> comparator = new Comparator<Thing>() {
  public int compare(Thing o1, Thing o2) {
    if (o1.a.equals(o2.a)) {
      return o1.b.compareTo(o2.b);
    }
    return o1.a.compareTo(o2.a);
  }
};

然后对您的列表进行排序：

Collections.sort(list, comparator);

最后进行二分查找：

int i = Collections.binarySearch(list, thingToFind, comparator);

- Fabian Steeg

---

这是最简单的方法。HashSet需要难以分析的时间。这个解决方案等同于STL set。 - Overflown

为什么 HashSet 更难分析？你知道它的渐进运行时间，可以对它进行性能分析。那么它更难分析的是什么？ - Wim Coenen

另一个不错的答案。在构建包装类之前，我会倾向于这样做。尤其是如果你正在查看非常大的数据集，我认为这可能更有效（从空间上来说肯定如此）。 - dimo414

这种方法比仅使用contains要慢，时间复杂度为O(N)，平均为N/2，因为排序的时间复杂度为O(N logN)，而二分查找的时间复杂度仍为O(log N)。 如果列表是静态的且需要重复搜索，则此方法是可行的，因为您可以对其进行一次排序并多次搜索。 - RobMcZag

Answer 3

考虑到你的限制，你只能使用暴力搜索（或创建索引，如果搜索将会重复）。你能否详细说明一下如何生成 ArrayList -- 也许在那里有一些空间。

如果你只是想要更漂亮的代码，请考虑使用Apache Commons Collections类，尤其是CollectionUtils.find()，这是现成的语法糖：

ArrayList haystack = // ...
final Object needleField1 = // ...
final Object needleField2 = // ...

Object found = CollectionUtils.find(haystack, new Predicate() {
   public boolean evaluate(Object input) {
      return needleField1.equals(input.field1) && 
             needleField2.equals(input.field2);
   }
});

- Michael Brewer-Davis

---

Guava的Iterators.find()非常相似，但支持泛型。 - Ed Staub

Answer 4

如果列表已经排序，你可以使用二分查找。如果没有，则没有更好的方法。

如果你经常这样做，第一次排序列表肯定是值得的。由于你不能修改类，因此必须使用Comparator进行排序和搜索。

- mmyers

---

这不太可能比手动搜索更快，因为听起来他的集合没有排序。 - oxbow_lakes

不幸的是，它是按照我不关心的两个字段之一进行排序的。我可以使用自定义比较器根据一个有助于二进制搜索的字段进行排序，但我觉得这在整体速度方面帮助不大 :| - Parrots

@Parrots：是否可以先排序，然后再进行所有的搜索？如果是这样，并且列表中有相当数量的对象（比如50个），那么二分查找肯定会更快。 - Michael Myers

二分查找肯定比普通的线性查找快得多。这是在假设您获得整个列表并且只需要对其进行一次排序的情况下，否则使用二分查找获得的速度优势将会丧失。有10,000个元素的情况下，二分查找=14次比较，而不使用二分查找=10000次比较。 - MahlerFive

如果底层列表实现不是ArrayList而是某种HashSet，那会更快，不是吗？ - OscarRyz

Answer 5

即使 equals 方法比较了这两个字段，逻辑上来说，它只是你手动比较的同样代码。好吧，可能有些“混乱”，但仍然是正确的答案。

- oxbow_lakes

Answer 6

如果您是我的ForEach DSL的用户，可以使用Detect查询来完成此操作。

Foo foo = ...
Detect<Foo> query = Detect.from(list);
for (Detect<Foo> each: query) 
    each.yield = each.element.a == foo.a && each.element.b == foo.b;
return query.result();

- Adrian Kuhn

Answer 7

是否有更好的方法，而不是只是循环遍历并手动比较每个对象的两个字段，然后在找到时停止？这似乎非常混乱，寻找更好的方法。

如果您关心可维护性，您可以像 Fabian Steeg 建议的那样做（这就是我会做的），虽然它可能不是“最有效”的（因为您必须先对数组进行排序，然后执行二进制搜索），但肯定是最干净和更好的选择。

如果您真的关心效率，您可以创建一个自定义 List 实现，使用您对象中的字段作为哈希，并使用 HashMap 作为存储。但可能这会太多了。

然后，您需要将填充数据的位置从 ArrayList 更改为 YourCustomList。

例如：

 List list = new ArrayList();

 fillFromSoap( list );

至：

 List list = new MyCustomSpecialList();

 fillFromSoap( list );

实现将类似于以下内容：

class MyCustomSpecialList extends AbstractList  { 
    private Map<Integer, YourObject> internalMap;

    public boolean add( YourObject o ) { 
         internalMap.put( o.getThatFieldYouKnow(), o );
    }

    public boolean contains( YourObject o ) { 
        return internalMap.containsKey( o.getThatFieldYouKnow() );
    }

}

几乎就像一个HashSet，这里的问题是HashSet依赖于hashCode方法的良好实现，而您可能没有。相反，您使用“您知道的那个字段”作为哈希值，该字段使一个对象等于另一个对象。

当然，从头开始实现List比我上面的代码片段要棘手得多，这就是为什么我说Fabian Steeg的建议更好、更容易实现（尽管像这样的东西更有效率）。

告诉我们最终你做了什么。

- Oscar Reyes

Answer 8

也许列表不是你所需要的。

也许TreeSet会是更好的容器。它可以实现O(log N)的插入和检索，并且有序迭代（但不允许重复项）。

对于你的用例，LinkedHashMap可能更好，也可以进行查看。

- Ben Hardy

Answer 9

基于字段值构建一个HashMap，将这些对象作为键可能从性能角度来看是值得的，例如只需一次填充Maps，就可以非常高效地查找对象。

- Rocket Surgeon

---

仅当搜索多次时返回。 - cletus

Answer 10

如果您需要在同一列表中多次搜索，建立索引可能会有所回报。

通过一次迭代，建立一个HashMap，将您要查找的equals值作为键，适当节点作为值。如果您需要给定equals值的全部而不是任何一个，则让映射具有列表类型的值，并在初始迭代中构建整个列表。

请注意，在执行此操作之前，应该先进行测量，因为建立索引的开销可能会超过仅遍历直到找到预期节点的开销。

- Thorbjørn Ravn Andersen