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

我有一个Java对象的ArrayList。 对象有四个字段,其中两个我会用来考虑对象等于另一个。 我正在寻找最有效的方式,给这两个领域,看看数组是否包含该对象。

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

有什么更好的方法比循环和手动比较每个对象的两个领域,然后打破时发现? 这似乎很混乱,寻找更好的方法。

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

这取决于你需要多less效率。 简单地遍历列表寻找满足一定条件的元素是O(n),但是ArrayList.Contains也可以实现Equals方法。 如果你没有在循环或内部循环中这样做,这种方法可能就好了。

如果你真的需要非常高效的查找速度,你需要做两件事情:

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

当然,构build这个HashSet仍然有O(n)的成本。 如果构buildHashSet的成本与所有需要执行的contains()检查的总成本相比可以忽略不计,那么您只能获得任何东西。 试图build立一个没有重复的列表是这样的情况。


*( )实现hashCode()最好是通过XOR'ing(^运算符)与你正在使用的相同字段的hashCode(但乘以31来减lessXOR产生0的机会)

您可以使用带有Java内置方法的比较器进行sorting和二进制search。 假设你有一个这样的类,其中a和b是你想用来sorting的字段:

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

最后做二进制search:

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

鉴于你的限制,你坚持蛮力search(或创build一个索引,如果search将被重复)。 你可以详细说明如何生成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); } }); 

如果列表已sorting ,则可以使用二进制search 。 如果没有,那么没有更好的办法。

如果你这么做了,那么第一次分类清单几乎肯定值得。 既然你不能修改类,你将不得不使用Comparator来进行sorting和search。

即使equals方法正在比较这两个字段,那么在逻辑上,它将与您手动执行的代码相同。 好吧,这可能是“混乱”,但它仍然是正确的答案

有什么更好的方法比循环和手动比较每个对象的两个领域,然后打破时发现? 这似乎很混乱,寻找更好的方法。

如果你关心的是可维护性,你可以做一下Fabian Steeg的build议(这就是我所要做的),尽pipe它可能不是“最高效的”(因为你必须首先对数组进行sorting,然后执行二进制search),但肯定是最干净的和更好的select。

如果你真的关心效率,你可以创build一个自定义的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的build议会更好,更容易实现(虽然这样做会更有效率)

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

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

也许TreeSet会是一个更好的容器。 你得到O(日志N)插入和检索,并有序的迭代(但不会允许重复)。

LinkedHashMap可能对你的用例更好,也检查一下。

如果您是我的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(); 

基于字段值作为关键字构build这些对象的HashMap可能是值得的,从性能的angular度来看,例如填充地图一次,非常有效地find对象

如果你需要在同一个列表中search很多时间,它可能会回报build立一个索引。

迭代一次,然后用你正在查找的等于值作为键和相应的节点作为值构build一个HashMap。 如果您需要全部而不是给定的任何等值,则让映射具有列表的值types,并在初始迭代中构build整个列表。

请注意,在做这件事之前你应该测量一下,因为构build索引的开销可能只是遍历直到find预期的节点。

有三个基本的select:

1)如果检索性能是最重要的,并且这样做是实际的,则使用一次构build的散列表格的forms(并且如果清单改变则更改为/)。

2)如果列表方便地sorting或对其进行sorting并且O(log n)检索足够,则进行sorting和search。

3)如果O(n)检索速度足够快,或者如果操作/维护数据结构或替代数据不切实际,则遍历列表。

在编写比简单迭代更复杂的代码之前,值得思考一些问题。

  • 为什么需要不同的东西? (时间)performance? 优雅? 可维护性? 重用? 所有这些都是好的原因,分开或一起,但他们影响解决scheme。

  • 你对这个数据结构有多less控制? 你能影响它是如何build造的? 以后pipe理?

  • 数据结构(和底层对象)的生命周期是什么? 它是一次build立起来的,从来没有改变,或高度dynamic? 你的代码是否可以监视(甚至改变)它的生命周期?

  • 还有其他重要的限制,比如内存占用? 关于重复的信息是否重要? 等等。

我会说最简单的解决scheme是包装对象,并委托包含调用包裹类的集合。 这与比较器类似,但不会强制您对结果集合进行sorting,您可以简单地使用ArrayList.contains()。

 public class Widget { private String name; private String desc; public String getName() { return name; } public void setName(String name) { this.name = name; } public String getDesc() { return desc; } public void setDesc(String desc) { this.desc = desc; } } public abstract class EqualsHashcodeEnforcer<T> { protected T wrapped; public T getWrappedObject() { return wrapped; } @Override public boolean equals(Object obj) { return equalsDelegate(obj); } @Override public int hashCode() { return hashCodeDelegate(); } protected abstract boolean equalsDelegate(Object obj); protected abstract int hashCodeDelegate(); } public class WrappedWidget extends EqualsHashcodeEnforcer<Widget> { @Override protected boolean equalsDelegate(Object obj) { if (obj == null) { return false; } if (obj == getWrappedObject()) { return true; } if (obj.getClass() != getWrappedObject().getClass()) { return false; } Widget rhs = (Widget) obj; return new EqualsBuilder().append(getWrappedObject().getName(), rhs.getName()).append(getWrappedObject().getDesc(), rhs.getDesc()).isEquals(); } @Override protected int hashCodeDelegate() { return new HashCodeBuilder(121, 991).append( getWrappedObject().getName()).append( getWrappedObject().getDesc()).toHashCode(); } }