关于清空链表的Java最佳实践

Question

关于清空链表的Java最佳实践

javacollectionsgarbage-collectionjava-8

5

我正在使用Java编写一个数据结构——链表（为了学习，我没有使用任何标准的Java库），我想通过将引用设置为null来清除数据结构。请建议哪种方法更好：

1）只需将列表的起始引用设置为null即可。

2）除了将起始引用设置为null外，我还将所有内部节点的下一个指针解除引用，这样做有助于垃圾收集器吗？

我注意到在JDK中LinkedList实现中采用了第二种方法，但是我没有在TreeMap中看到同样的方法。

我正在使用JDK 8。

- Debapriya Biswas

1

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8-b132/java/util/LinkedList.java#LinkedList.clear%28%29 - assylias

3

两种方法都可以使用。(2)会影响实时行为，可能会花费时间。(2)的重点是特别是长度为N的双向链表可能需要N个垃圾步骤，但一个垃圾回收可以执行多个步骤。具体取决于所使用的垃圾回收算法。但由于缺失可达性是垃圾回收的主要要求，我不会过多关注它。实时行为更加重要。 - Joop Eggen

1

如果你的数据结构类似于Java的LinkedList实现，那么我认为这两种方法都不太好。第二种方法会更好，因为分代GC可以做得更好。 - TheLostMind

1

LinkedList和TreeMap的主要区别在于后者对实际代码有重要意义。如果您关心性能，就不会使用LinkedList。因此，当LinkedList浪费CPU周期来“帮助垃圾收集器”时，这并不重要... - Holger

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Stuart Marks · Accepted Answer

这是一个有趣的问题，答案有着悠久的历史和微妙的权衡。

简短的答案是，清除引用对于数据结构的正确操作并非必要。由于您正在学习数据结构，我建议您不要在自己的实现中担心这个问题。我的直觉（尽管我没有对此进行基准测试）是，在典型条件下，清除所有链接节点可能会产生的任何好处很少会在常规情况下被注意到。

（此外，在典型条件下，LinkedList 将被 ArrayList 或 ArrayDeque 超越。有一些基准测试可以说明这一点。虽然很容易想出工作负载，其中 LinkedList 能够胜过其他数据结构，但这比人们想象的更为罕见。）

我很惊讶地发现，LinkedList 的 clear 操作会将所有节点及其包含的元素从彼此之间和列表中解除链接。这里是指向 JDK 8 代码的链接。这个更改可以追溯到2003年，并在JDK 5中出现。这个更改被 JDK-4863813 bug 跟踪。当节点从列表中解除链接时，该更改（或稍早的更改）会清除各个节点的下一个和上一个引用。该 bug 报告中还有一个有趣的测试案例。

问题似乎在于可以更快地对LinkedList进行更改，从而创建垃圾节点，而垃圾回收器无法及时回收它们。这最终导致JVM内存不足。所有垃圾节点都链接在一起的事实似乎也会阻碍垃圾收集器，使得修改器线程更容易超过收集器线程。(我不清楚多个线程修改列表的重要性。在测试用例中，它们都在列表上同步，因此没有实际的并行性。)将LinkedList更改为将节点从彼此解除链接使收集器更容易完成其工作，因此显然使测试不再耗尽内存。

快进到2009年，LinkedList代码进行了"翻新"。这个过程被bug JDK-6897553跟踪，并在电子邮件审查线程中讨论。 "翻新" 的最初动机之一是将clear()操作从O(n)降低到O(1)，因为该bug的提交者认为解除所有节点的链接似乎是不必要的。（对我来说肯定是不必要的！）但经过一些讨论后，决定保留解除链接行为以提供足够的利益给垃圾收集器并记录它。

评论还说，解除节点的链接

即使有一个可达的迭代器，也一定会释放内存

这是指以下某种病态情况：

// fields in some class
List<Obj> list = createAndPopulateALinkedList();
Iterator<Object> iterator;

void someMethod() {
    iterator = list.iterator();
    // ...
    list.clear();
}

迭代器指向链表中的一个节点。即使列表已被清除，迭代器仍保留一个节点，并且由于该节点具有下一个和上一个引用，因此列表中以前的所有节点仍然存在。在clear()中取消链接所有节点可以让这些节点被收集。不过，我认为这是相当病态的，因为很少将迭代器存储在字段中。通常，迭代器在单个方法内创建、使用和丢弃，最常见的情况是在单个for循环内。

现在，关于TreeMap。我不认为LinkedList取消链接其节点而TreeMap没有的原因是根本性的。人们可能认为整个JDK代码库都是一致维护的，因此如果LinkedList取消链接其节点是一个好的实践，那么也应该对TreeMap进行更新。但遗憾的是，情况并非如此。最有可能的是，某个客户遇到了LinkedList的病态行为，并在那里进行了更改，但是从未观察到类似的TreeMap行为。因此，没有动力更新TreeMap。