10

性能方面，使用之间真的有很大区别：

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

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

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

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

4

6 回答 6

9

编辑：

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

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

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

于 2010-05-21T21:56:22.233 回答
6

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

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

（在 ArrayList 中检查）

于 2010-05-21T22:11:33.087 回答
3

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

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

  1. ArrayList - indexOf 是后备数组上的 C 风格 for 循环。
  2. LinkedList - indexOf 以 C 风格的 for 循环遍历链表。

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

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

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

于 2010-05-21T21:55:58.057 回答
2

ArrayList.contains 确实

return indexOf(o) >= 0;

在哪里

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

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 使用键的散列来获取具有该散列的所有键（这很快），然后仅在这些键上使用 equals，因此那里有改进；但是 containsValue() 使用 for 遍历值。

TreeMap.containsKey 似乎使用比较器进行知情搜索以更快地找到密钥，因此更好；但是 containsValue 似乎仍然会遍历整个三个，直到找到一个值。

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

于 2010-05-21T22:10:26.910 回答
0

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

谢谢，克里希纳

于 2010-05-21T21:58:14.187 回答
0

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

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

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

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

于 2010-05-21T22:06:03.990 回答