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

Most efficient way to see if an ArrayList contains an object in Java

提问by Parrots

I have an ArrayList of objects in Java. The objects have four fields, two of which I'd use to consider the object equal to another. I'm looking for the most efficient way, given those two fields, to see if the array contains that object.

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

The wrench is that these classes are generated based on XSD objects, so I can't modify the classes themselves to overwrite the .equals.

关键是这些类是基于 XSD 对象生成的，所以我不能修改类本身来覆盖.equals.

Is there any better way than just looping through and manually comparing the two fields for each object and then breaking when found? That just seems so messy, looking for a better way.

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

Edit:the ArrayList comes from a SOAP response that is unmarshalled into objects.

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

采纳答案by Wim Coenen

It depends on how efficient you need things to be. Simply iterating over the list looking for the element which satisfies a certain condition is O(n), but so is ArrayList.Contains if you could implement the Equals method. If you're not doing this in loops or inner loops this approach is probably just fine.

这取决于你需要的东西有多高效。简单地遍历列表以查找满足特定条件的元素是 O(n)，但如果您可以实现 Equals 方法，那么 ArrayList.Contains 也是如此。如果您不在循环或内部循环中执行此操作，则此方法可能很好。

If you really need very efficient look-up speeds at all cost, you'll need to do two things:

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

1. Work around the fact that the class is generated: Write an adapter class which can wrap the generated class and which implement equals()based on those two fields (assuming they are public). Don't forget to also implement hashCode()(*)
2. Wrap each object with that adapter and put it in a HashSet. HashSet.contains()has constant access time, i.e. O(1) instead of O(n).

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

Of course, building this HashSet still has a O(n) cost. You are only going to gain anything if the cost of building the HashSet is negligible compared to the total cost of all the contains() checks that you need to do. Trying to build a list without duplicates is such a case.

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

---

---

* () Implementing hashCode() is best done by XOR'ing (^ operator) the hashCodes of the same fields you are using for the equals implementation (but multiply by 31to reduce the chance of the XOR yielding 0)) 实现 hashCode() 最好通过 XOR'ing (^ operator) 用于 equals 实现的相同字段的 hashCode 来完成（但乘以 31以减少 XOR 产生 0 的机会）

回答by Michael Myers

If the list is sorted, you can use a binary search. If not, then there is no better way.

如果列表已排序，则可以使用二进制搜索。如果没有，那就没有更好的办法了。

If you're doing this a lot, it would almost certainly be worth your while to sort the list the first time. Since you can't modify the classes, you would have to use a Comparatorto do the sorting and searching.

如果您经常这样做，那么第一次对列表进行排序几乎肯定是值得的。由于您无法修改类，因此您必须使用 aComparator进行排序和搜索。

回答by oxbow_lakes

Even if the equals method werecomparing those two fields, then logically, it would be just the same code as you doing it manually. OK, it might be "messy", but it's still the correct answer

即使equals方法是比较这两个领域，那么在逻辑上，它会为你做手工是一样的代码。好吧，这可能是“乱七八糟”，但它仍然是正确答案

回答by Michael Brewer-Davis

Given your constraints, you're stuck with brute force search (or creating an index if the search will be repeated). Can you elaborate any on how the ArrayListis generated--perhaps there is some wiggle room there.

考虑到您的限制，您只能使用蛮力搜索（或者在重复搜索时创建索引）。您能否详细说明如何ArrayList生成 - 也许那里有一些回旋余地。

If all you're looking for is prettier code, consider using the Apache Commons Collections classes, in particular CollectionUtils.find(), for ready-made syntactic sugar:

如果您正在寻找更漂亮的代码，请考虑使用 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);
   }
});

回答by Rocket Surgeon

Building a HashMap of these objects based on the field value as a key could be worthwhile from the performance perspective, e.g. populate Maps once and find objects very efficiently

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

回答by Thorbj?rn Ravn Andersen

If you need to search many time in the same list, it may pay off to build an index.

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

Iterate once through, and build a HashMap with the equals value you are looking for as the key and the appropriate node as the value. If you need all instead of anyone of a given equals value, then let the map have a value type of list and build the whole list in the initial iteration.

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

Please note that you should measure before doing this as the overhead of building the index may overshadow just traversing until the expected node is found.

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

回答by Fabian Steeg

You could use a Comparator with Java's built-in methods for sorting and binary search. Suppose you have a class like this, where a and b are the fields you want to use for sorting:

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

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

You would define your 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);
  }
};

Then sort your list:

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

Collections.sort(list, comparator);

And finally do the binary search:

最后进行二分查找：

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

回答by Jeremy Rishel

There are three basic options:

有三个基本选项：

1) If retrieval performance is paramount and it is practical to do so, use a form of hash table built once (and altered as/if the List changes).

1）如果检索性能是最重要的并且这样做是可行的，请使用一种构建一次的哈希表形式（并在列表更改时进行更改）。

2) If the List is conveniently sorted or it is practical to sort it and O(log n) retrieval is sufficient, sort and search.

2）如果List方便排序或者排序是可行的并且O(log n)检索就足够了，排序和搜索。

3) If O(n) retrieval is fast enough or if it is impractical to manipulate/maintain the data structure or an alternate, iterate over the List.

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

Before writing code more complex than a simple iteration over the List, it is worth thinking through some questions.

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

• Why is something different needed? (Time) performance? Elegance? Maintainability? Reuse? All of these are okay reasons, apart or together, but they influence the solution.

• How much control do you have over the data structure in question? Can you influence how it is built? Managed later?

• What is the life cycle of the data structure (and underlying objects)? Is it built up all at once and never changed, or highly dynamic? Can your code monitor (or even alter) its life cycle?

• Are there other important constraints, such as memory footprint? Does information about duplicates matter? Etc.

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

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

• 数据结构（和底层对象）的生命周期是什么？它是一次性建立起来从不改变的，还是高度动态的？你的代码可以监控（甚至改变）它的生命周期吗？

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

回答by OscarRyz

Is there any better way than just looping through and manually comparing the two fields for each object and then breaking when found? That just seems so messy, looking for a better way.

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

If your concern is maintainability you could do what Fabian Steegsuggest ( that's what I would do ) although it probably isn't the "most efficient" ( because you have to sort the array first and then perform the binary search ) but certainly the cleanest and better option.

如果您关心的是可维护性，您可以按照Fabian Steeg 的建议进行操作（这就是我会做的），尽管它可能不是“最有效的”（因为您必须先对数组进行排序，然后再执行二分查找），但肯定是最干净的和更好的选择。

If you're really concerned with efficiency, you can create a custom List implementation that uses the field in your object as the hash and use a HashMap as storage. But probably this would be too much.

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

Then you have to change the place where you fill the data from ArrayList to YourCustomList.

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

Like:

喜欢：

 List list = new ArrayList();

 fillFromSoap( list );

To:

到：

 List list = new MyCustomSpecialList();

 fillFromSoap( list );

The implementation would be something like the following:

实现将类似于以下内容：

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

}

}

Pretty much like a HashSet, the problem here is the HashSet relies on the good implementation of the hashCode method, which probably you don't have. Instead you use as the hash "that field you know" which is the one that makes one object equals to the other.

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

Of course implementing a List from the scratch lot more tricky than my snippet above, that's why I say the Fabian Steegsuggestion would be better and easier to implement ( although something like this would be more efficient )

当然，从头开始实现一个 List 比我上面的片段要复杂得多，这就是为什么我说Fabian Steeg 的建议会更好更容易实现（尽管这样的事情会更有效）

Tell us what you did at the end.

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

回答by jonathan.cone

I would say the simplest solution would be to wrap the object and delegate the contains call to a collection of the wrapped class. This is similar to the comparator but doesn't force you to sort the resulting collection, you can simply use ArrayList.contains().

我会说最简单的解决方案是包装对象并将 contains 调用委托给包装类的集合。这类似于比较器，但不强制您对结果集合进行排序，您可以简单地使用 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();
        }

    }