LinkedList.contains执行速度

Question

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

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

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

Answer 1

我们来看看源代码(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可以在内部结构上工作,使用直接字段访问迭代,而不是使用an的for-each Iterator<E>,其方法还必须另外检查诸如此类的东西ConcurrentModificationException.

回到源代码,你会发现a 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())迭代a 作为客户端比LinkedList内部可以做的更昂贵.这是可以预料的,这就是为什么contains首先提供的原因.

内部工作带来LinkedList了巨大的优势,因为:

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

那么你能从中学到什么呢？熟悉API!看看已经提供了哪些功能; 它们可能比你不得不将它们复制为客户端更快.