java 使用 contains 或循环遍历列表有什么大的区别？

Any big difference between using contains or loop through a list?

提问by rfgamaral

Performance wise, is there really a big difference between using:

性能方面，使用以下方法是否真的有很大区别：

• ArrayList.contains(o) vs foreach|iterator
• LinkedList.contains(o) vs foreach|iterator

• ArrayList.contains(o) 与 foreach|迭代器
• LinkedList.contains(o) vs foreach|iterator

Of course, for the foreach|iterator loops, I'll have to explicitly compare the methods and return true or false accordingly.

当然，对于 foreach|iterator 循环，我必须明确比较这些方法并相应地返回 true 或 false。

The object I'm comparing is an object where equals()and hashcode()are both properly overridden.

我比较的对象是一个对象，其中equals()和hashcode()都被正确覆盖。

EDIT:Don't need to know about containsValue after all, sorry about that. And yes, I'm stupid... I realized how stupid my question was about containsKey vs foreach, nevermind about that, I don't know what I was thinking. I basically want to know about the ones above (edited out the others).

编辑：毕竟不需要知道 containsValue ，对此感到抱歉。是的，我很愚蠢……我意识到我的问题是关于 containsKey 与 foreach 的问题有多愚蠢，没关系，我不知道我在想什么。我基本上想知道上面的那些（编辑掉其他的）。

采纳答案by CPerkins

EDITED:

编辑：

With the new form of the question no longer including HashMap and TreeMap, my answer is entirely different. I now say no.

问题的新形式不再包括HashMap和TreeMap，我的答案完全不同。现在我说没有。

I'm sure that other people have answered this, but in both LinkedList and ArrayList, contains() just calls indexOf(), which iterates over the collection.

我确定其他人已经回答了这个问题，但是在 LinkedList 和 ArrayList 中，contains() 只调用 indexOf()，它会遍历集合。

It's possible that there are tiny performance differences, both between LinkedList and ArrayList, and between contains and foreach, there aren't any bigdifferences.

LinkedList 和 ArrayList 之间以及 contains 和 foreach 之间可能存在微小的性能差异，没有任何大的差异。

回答by stacker

This makes no differency since contains(o) calls indexOf(o) which simply loops like this:

这没什么区别，因为 contains(o) 调用 indexOf(o) ，它只是像这样循环：

for (int i = 0; i < size; i++)
    if (o.equals(elementData[i]))
       return i;

(Checked in ArrayList)

（在 ArrayList 中检查）

回答by Matthew Flaschen

Without benchmarking, contains should be faster or the same in all cases.

如果没有基准测试，包含在所有情况下都应该更快或相同。

For 1 and 2, it doesn't need to call the iterator methods. It can loop internally. Both ArrayList and LinkedList implement contains in terms of indexOf

对于 1 和 2，不需要调用迭代器方法。它可以在内部循环。ArrayList 和 LinkedList 都在 indexOf 方面实现了 contains

1. ArrayList- indexOf is a C-style for loop on the backing array.
2. LinkedList- indexOf walks the linked list in a C-style for loop.

1. ArrayList- indexOf 是支持数组上的 C 样式 for 循环。
2. LinkedList- indexOf 在 C 风格的 for 循环中遍历链表。

For 3 and 4, you have to distinguish between containsKey and containsValue.

对于 3 和 4，您必须区分 containsKey 和 containsValue。

3. HashMap, containsKey is O(1). It works by hashing the key, getting the associated bucket, then walking the linked list. containsValue is O(n) and works by simply checking every value in every bucket in a nested for loop.

3.  HashMap， containsKey 是 O(1)。它的工作原理是散列密钥，获取关联的存储桶，然后遍历链表。containsValue 是 O(n) 并且通过简单地检查嵌套 for 循环中每个存储桶中的每个值来工作。

4. TreeMap, containsKey is O(log n). It checks whether it's in range, then searches the red-black tree. containsValue, which is O(n), uses an in-order walk of the tree.

4.  TreeMap， containsKey 是 O(log n)。它检查它是否在范围内，然后搜索红黑树。containsValue，即 O(n)，使用树的有序遍历。

回答by Andrei Fierbinteanu

ArrayList.contains does

ArrayList.contains 确实

return indexOf(o) >= 0;

where

在哪里

public int indexOf(Object o) {
if (o == null) {
    for (int i = 0; i < size; i++)
    if (elementData[i]==null)
        return i;
} else {
    for (int i = 0; i < size; i++)
    if (o.equals(elementData[i]))
        return i;
}
return -1;
}

It's similar for LinkedList, only it uses .next() to iterate through the elements, so not much difference there.

它与 LinkedList 类似，只是它使用 .next() 来遍历元素，因此没有太大区别。

public int indexOf(Object o) {
    int index = 0;
    if (o==null) {
        for (Entry e = header.next; e != header; e = e.next) {
            if (e.element==null)
                return index;
            index++;
        }
    } else {
        for (Entry e = header.next; e != header; e = e.next) {
            if (o.equals(e.element))
                return index;
            index++;
        }
    }
    return -1;
}

HashMap.containKey uses the hash of the key to fetch all keys with that hash (which is fast) and then uses equals only on those keys, so there's an improvement there; but containsValue() goes through the values with a for.

HashMap.containKey 使用键的散列来获取具有该散列的所有键（速度很快），然后仅在这些键上使用 equals，因此有一个改进；但是 containsValue() 使用 for 遍历值。

TreeMap.containsKey seem to do an informed search using a comparator to find the Key faster, so still better; but containsValue still seems to go through the entire three until it finds a value.

TreeMap.containsKey 似乎使用比较器进行了明智的搜索以更快地找到 Key，所以仍然更好；但是 containsValue 似乎仍然遍历整个三个，直到找到一个值。

Overall I think you should use the methods, since they're easier to write than doing a loop every time :).

总的来说，我认为您应该使用这些方法，因为它们比每次都执行循环更容易编写:)。

回答by Krishna

I think using contains is better because generally the library implementation is more efficient than manual implementation of the same. Check out if you can during object construction or afterwards pass a comparator method that you have written which takes care of your custom equals and hashcode implementation.

我认为使用 contains 更好，因为通常库实现比相同的手动实现更有效。检查您是否可以在对象构造期间或之后传递您编写的比较器方法，该方法负责您的自定义 equals 和 hashcode 实现。

Thanks, Krishna

谢谢，克里希纳

回答by Ilia K.

Traversing the container with foreach/iterator is always O(n) time. ArrayList/LinkedList search is O(n) as well.

使用 foreach/iterator 遍历容器总是 O(n) 时间。ArrayList/LinkedList 搜索也是 O(n)。

HashMap.containsKey() is O(1) amortizedtime.

HashMap.containsKey() 是 O(1)分摊时间。

TreeMap.containsKey() is O(log n) time.

TreeMap.containsKey() 是 O(log n) 时间。

For both HashMap and TreeMap containsValue() is O(n), but there may be implementations optimized for containsValue() be as fast as containsKey().

对于 HashMap 和 TreeMap， containsValue() 都是 O(n)，但可能有针对 containsValue() 优化的实现与 containsKey() 一样快。