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

如果列表是 解决了，你可以使用 二进制搜索。如果不是，那么没有更好的方法。

如果您经常这样做，那么第一次对列表进行排序几乎肯定是值得的。因为不能修改类，所以必须使用 Comparator来进行排序和搜索。

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

考虑到您的约束，您只能使用强制搜索(或者如果重复搜索，则创建索引)。您能详细说明 ArrayList是如何生成的吗——也许还有一些回旋余地。

如果您所要寻找的只是更漂亮的代码，那么可以考虑使用 Apache Commons Collection 类，特别是 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);
}
});

从性能的角度来看，根据字段值作为键来构建这些对象的 HashMap 是值得的，例如，一次性填充 Maps 并非常有效地查找对象

如果需要在同一列表中多次搜索，那么构建索引可能会有所收获。

迭代一次，构建一个 HashMap，使用您正在查找的 equals 值作为键，并使用适当的节点作为值。如果您需要 all 而不是任何给定的 equals 值，那么让 map 具有 list 的 value 类型，并在初始迭代中构建整个 list。

请注意，在执行此操作之前应该进行度量，因为构建索引的开销可能会盖过只是遍历，直到找到期望的节点。

这取决于你需要多高的效率。简单地遍历列表，寻找满足某个条件的元素是 O (n) ，但 ArrayList 也是如此。包含是否可以实现 Equals 方法。如果您不是在循环或内部循环中执行此操作，那么这种方法可能就很好。

如果你真的不惜一切代价需要非常高效的查找速度，你需要做两件事:

1. 解决这个问题 生成: 编写一个适配器类 可以包装生成的类和 实现基于 等于()的 在这两个领域(假设他们 别忘了 实施 HashCode ()(*)
2. 用该适配器包装每个对象，然后 把它放进哈希集里。 包含() 具有常量 存取时间，即 O (1)而非 O (n)。

当然，构建这个 HashSet 仍然有 O (n)成本。只有当构建 HashSet 的成本与所有需要执行的包含()检查的总成本相比微不足道时，您才能获得任何收益。试图建立一个没有重复的列表就是这种情况。

您可以使用带有 Java 内置方法的 Compator 进行排序和二进制搜索。假设您有这样一个类，其中 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);

有三种基本选择:

1)如果检索性能是至关重要的，并且这样做是切实可行的，那么使用一次性构建的散列表形式(并且随着列表的改变而改变)。

2)如果 List 是方便排序的，或者排序是可行的，而 O (log n)检索是充分的，那么排序和搜索。

3)如果 O (n)检索足够快，或者操作/维护数据结构或替代方法不切实际，则在 List 上迭代。

在编写比简单迭代 List 更复杂的代码之前，有必要思考一些问题。

• 为什么需要不同的东西？(时间)表演？优雅？可维护性？重复使用？所有这些都是可以的理由，不管是分开的还是一起的，但是它们会影响解决方案。

• 您对所讨论的数据结构有多少控制权？你能影响它的建造方式吗？后来管理？

• 数据结构(和底层对象)的生命周期是什么？它是一下子建立起来，从未改变过，还是高度动态的？您的代码能够监视(甚至改变)它的生命周期吗？

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

有没有比循环遍历并手动比较每个对象的两个字段然后在找到时中断更好的方法？这看起来太混乱了，在寻找更好的方法。

如果你关心的是可维护性，你可以按照 法比安・斯蒂格的建议去做(我也会这么做) ，虽然它可能不是“最有效率”的(因为你必须先对数组排序，然后执行二进制搜索) ，但是肯定是最干净和更好的选择。

如果您真的关心效率，您可以创建一个自定义 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 方法的良好实现，而您可能没有这种实现。相反，您使用散列“ that field you know”，它使一个对象等于另一个对象。

当然，从头开始实现 List 比我上面的代码片段要棘手得多，这就是为什么我说 法比安・斯蒂格建议会更好，更容易实现(尽管这样的东西会更有效率)

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

我认为最简单的解决方案是包装对象并将包含调用委托给包装类的集合。这与比较器类似，但不强制您对结果集合进行排序，您可以简单地使用 ArrayList.include ()。

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


}

也许你需要的不是名单。

也许 树集会是一个更好的容器。您将获得 O (logN)插入和检索，以及有序迭代(但不允许重复)。

LinkedHashMap 可能对您的用例更好，也可以检查一下。

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