为什么不是LinkedList.Clear（）O（1）

问题描述

我假设LinkedList.Clear（）在我正在处理的项目上是O（1），因为我使用LinkedList来消耗我需要高吞吐量的清除和重用LinkedList的消费者中的BlockingQueue。 / p>

原来这个假设是错误的，因为（OpenJDK）代码这样做：

 条目< E> e = header.next; 
 while（e！= header）{
 Entry< E> next = e.next; 
 e.next = e.previous = null; 
 e.element = null; 
 e =下一个; 
} 
  

这有点令人惊讶，有没有什么好理由LinkedList.Clear无法'简单地忘记它的header.next和header.previous成员？

解决方案

我正在寻找的版本中的源代码Eclipse中的（build 1.7.0-ea-b84）上面有这个评论：

  //清除所有链接节点之间是不必要的，但是：
 //  - 如果被丢弃的节点居住在
 //多于一代
 //，则有助于世代GC  - 即使在那里也确保释放内存是一个可达到的迭代器
  

这使得他们为什么这么做是相当明确的，尽管我同意它警告它将O（1）操作变为O（n）。

I was assuming LinkedList.Clear() was O(1) on a project I'm working on, as I used a LinkedList to drain a BlockingQueue in my consumer that needs high throughput, clearing and reusing the LinkedList afterwards.

Turns out that assumption was wrong, as the (OpenJDK) code does this:

    Entry<E> e = header.next;
    while (e != header) {
        Entry<E> next = e.next;
        e.next = e.previous = null;
        e.element = null;
        e = next;
    }

This was a bit surprising, are there any good reason LinkedList.Clear couldn't simply "forget" its header.next and header.previous member ?

解决方案

The source code in the version I'm looking at (build 1.7.0-ea-b84) in Eclipse have this comment above them:

// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
//   more than one generation
// - is sure to free memory even if there is a reachable Iterator

That makes it reasonably clear why they're doing it, although I agree it's slightly alarming that it turns an O(1) operation into O(n).

这篇关于为什么不是LinkedList.Clear（）O（1）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！