查看ArrayList是否包含Java中的对象的最有效方法

我有一个Java的对象ArrayList.这些对象有四个字段,其中两个我用来将对象视为另一个.我正在寻找最有效的方法,给定这两个字段,看看数组是否包含该对象.

扳手是这些类是基于XSD对象生成的,所以我不能修改类本身来覆盖它们.equals.

有没有更好的方法,而不仅仅是循环并手动比较每个对象的两个字段,然后在找到时断开？这看起来很混乱,寻找更好的方法.

编辑: ArrayList来自一个解组到对象中的SOAP响应.

1> Wim Coenen..：

---

这取决于你需要的东西的效率.简单地遍历列表寻找满足某个条件的元素是O(n),但是如果你可以实现Equals方法,那么ArrayList.Contains也是如此.如果你不是在循环或内循环中这样做,这种方法可能就好了.

如果您真的需要不惜一切代价获得非常高效的查找速度,那么您需要做两件事:

解决生成类的问题:编写一个适配器类,它可以包装生成的类,并基于这两个字段实现equals()(假设它们是公共的).别忘了也实现hashCode()(*)

用该适配器包装每个对象并将其放在HashSet中. HashSet.contains()具有恒定的访问时间,即O(1)而不是O(n).

当然,构建此HashSet仍然具有O(n)成本.如果构建HashSet的成本与您需要执行的所有contains()检查的总成本相比可以忽略不计,那么您将获得任何收益.试图建立一个没有重复的列表就是这种情况.

---

*()实现hashCode()最好通过XOR'ing(^运算符)用于equals实现的相同字段的hashCodes(但乘以31以减少XOR产生0的机会)

---

@Jonas,虽然糟糕的hashCode()实现会导致访问时间变慢,但任何算法文本(特别是CLR(S)文本都会构建许多Collections数据结构 - http://www.amazon.com/Introduction -Algorithms-Third-Thomas-Cormen/dp/0262033844 /)将告诉您基于散列的数据结构是O(1)用于查找.重要的是要认识到O(1)不表示一步查找,而是与数据结构的大小无关的查找.因此,即使hashCode()s很差,查找时间也是O(1).Wim没有传播任何错误的信息,事实上他已经发现了.

---

@JonasKölker:来自文档:"这个类为基本操作(添加,删除,包含和大小)提供恒定的时间性能,假设散列函数在桶中正确地分散元素."

2> Fabian Steeg..：

---

您可以使用带有Java内置方法的Comparator进行排序和二分查找.假设您有一个这样的类,其中a和b是您要用于排序的字段:

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

您将定义您的比较器:

Comparator comparator = new Comparator() {
  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);

3> Michael Brew..：

---

鉴于您的约束,您将坚持使用强力搜索(或者如果将重复搜索则创建索引).你能详细说明它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);
   }
});

---

Guava的[Iterators.find()](http://guava-libraries.googlecode.com/svn/tags/release09/javadoc/index.html)非常相似,但支持泛型.

4> Michael Myer..：

---

如果列表已排序,您可以使用二进制搜索.如果没有,那就没有更好的方法了.

如果你这么做很多,那么第一次对列表进行排序几乎肯定是值得的.由于您无法修改类,因此您必须使用a Comparator来进行排序和搜索.