LinkedList.contains执行速度

为什么Methode LinkedList.contains（）比这样的实现运行得快：

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

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

Answer 1

我们来看看java.util.LinkedList 的源代码 （OpenJDK版本）

 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的for-each，其方法还必须另外检查ConcurrentModificationException等内容。

回到源代码，您会发现LinkedList的Iterator返回的E next()方法如下：

 private class ListItr implements ListIterator { //... 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; “繁忙” e = e.next; 在LinkedList.contains ！ LinkedList的iterator()实际上是一个ListIterator ，它具有更丰富的function。 你的for-each循环中不需要它们，但遗憾的是你无论如何都必须为它们付费。 更不用说所有那些对ConcurrentModificationException防御性检查都必须执行，即使在迭代它时不会对列表进行任何修改。

---

结论

所以，是的，使用for-each（或更直接地，使用iterator()/listIterator() ）将LinkedList迭代为客户端比LinkedList本身在内部可以做的更昂贵。 这是可以预料的，这就是为什么首先提供contains原因。

内部工作为LinkedList了巨大的优势，因为：

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

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

Answer 2

我决定对此进行测试并得出一些有趣的结果

import java.util.LinkedList;

公共类包含{

 private LinkedList items = new LinkedList(); public Contains(){ this.addToList(); } private void addToList(){ for(int i=0; i<2000; i++){ this.items.add("ItemNumber" + i); } } public boolean forEachLoop(String searchFor){ for(String item : items){ if(item.equals(searchFor)) return true; } return false; } public boolean containsMethod(String searchFor){ if(items.contains(searchFor)) return true; return false; } 

}

和一个JUnit测试用例：

import static org.junit.Assert.assertEquals; import org.junit.Test; public class ContainsTest { @Test public void testForEachLoop(){ Contains c = new Contains(); boolean result = c.forEachLoop("ItemNumber1758"); assertEquals("Bug!!", true, result); } @Test public void testContainsMethod(){ Contains c = new Contains(); boolean result = c.containsMethod("ItemNumber1758"); assertEquals("Bug!!", true, result); } }
import static org.junit.Assert.assertEquals; import org.junit.Test; public class ContainsTest { @Test public void testForEachLoop(){ Contains c = new Contains(); boolean result = c.forEachLoop("ItemNumber1758"); assertEquals("Bug!!", true, result); } @Test public void testContainsMethod(){ Contains c = new Contains(); boolean result = c.containsMethod("ItemNumber1758"); assertEquals("Bug!!", true, result); } } 

这个有趣的事情是当我运行JUnit测试时，结果是： - testForEachLoop（） - 0.014s - testContainsMethod（） - 0.025s

这是真的还是我做错了什么？