java - LinkedList.contains 执行速度

Question

为什么 Methode LinkedList.contains() 比这样的实现运行得更快:

for (String s : list) 
   if (s.equals(element))
     return true;
return false;

我没有看到这与实现(我认为搜索对象不是空值)、相同的迭代器和等于操作之间有很大区别

Answer 1

我们来看看the source code (OpenJDK 版本)java.util.LinkedList

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

如您所见，这是一个线性搜索，就像 for-each 解决方案一样，因此它不会渐进地更快。看看您的数字如何随着更长的列表而增长会很有趣，但这可能是一个较慢的常数因素。

原因是这个 indexOf在内部结构上工作，使用直接字段访问进行迭代，而不是使用 Iterator<E> 的 for-each ，其方法还必须另外检查 ConcurrentModificationException 之类的内容等

回到源头，你会发现E next() Iterator<E> 返回的方法的 LinkedList是以下内容:

private class ListItr implements ListIterator<E> {
   //...
   public E next() {
      checkForComodification();
      if (nextIndex == size)
      throw new NoSuchElementException();

      lastReturned = next;
      next = next.next;
      nextIndex++;
      return lastReturned.element;
  }
  final void checkForComodification() {
      if (modCount != expectedModCount)
         throw new ConcurrentModificationException();
  }

这比 e = e.next; 相当“繁忙”在LinkedList.contains ! iterator()的 LinkedList实际上是一个 ListIterator , 具有更丰富的特征。在您的 for-each 循环中不需要它们，但不幸的是您无论如何都必须为它们付费。更不用说所有那些针对 ConcurrentModificationException 的防御性检查了必须执行，即使在迭代列表时不会对列表进行任何修改。

---

结论

所以是的，迭代一个 LinkedList作为使用 for-each 的客户端(或者更直接地说，使用它的 iterator()/listIterator() )比 LinkedList 更昂贵自己内部可以做。这是可以预料的，这就是为什么 contains首先提供。

内部工作给出 LinkedList巨大的优势，因为:

• 它可以在防御性检查中偷工减料，因为它知道它没有违反任何不变量
• 它可以走捷径并使用其内部表示

那么你能从中学到什么？ 熟悉 API! 查看已经提供了哪些功能；它们可能比您必须将它们复制为客户端更快。