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

Question

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

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

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

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

Answer 1

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

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

1. 解决生成类的问题:编写一个适配器类,它可以包装生成的类,并基于这两个字段实现equals()(假设它们是公共的).别忘了也实现hashCode()(*)
2. 用该适配器包装每个对象并将其放在HashSet中. HashSet.contains()具有恒定的访问时间,即O(1)而不是O(n).

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

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

Answer 2

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

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

您将定义您的比较器:

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);

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);
   }
});

Answer 4

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

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