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

Question

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

1) 将列表的起始引用设为 null 就足够了。

2) 除了将 start 置空外，我将所有内部节点的所有 next 指针都取消引用为 null。这对垃圾收集器有任何帮助吗？

我看到方法 2 中的混淆在 JDK 中用于 LinkedList 实现。但我没有看到 TreeMap 相同

我正在使用 JDK 8

Answer 1

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

简短的回答是，数据结构的正确操作不需要清除引用。由于您正在学习数据结构，因此我建议您不要在自己的实现中担心这个问题。我的预感(虽然我没有对此进行基准测试)是，在典型条件下，清除所有链接节点可能带来的任何好处都很少被注意到。

(此外，在典型条件下， LinkedList 的表现可能会优于 ArrayList 或 ArrayDeque 。有 是 基准测试说明了这一点。但在其他情况下，人们认为 LinkedList 的工作量比其他人更难.)

我很惊讶地得知 clear 的 LinkedList 操作将所有节点彼此断开以及与包含的元素断开链接。这是 code in JDK 8 的链接。此更改可追溯到 2003 年，此更改出现在 JDK 5 中。此更改由错误 JDK-4863813 跟踪。当单个节点从列表中取消链接时，该更改(或稍早的更改)会清除来自单个节点的下一个和上一个引用。那个错误报告中还有一个测试用例，这很有趣。

问题似乎是可以对 LinkedList 进行更改，这会创建垃圾节点，比垃圾收集器回收它们的速度更快。这最终会导致 JVM 内存不足。垃圾节点全部链接在一起的事实似乎也具有阻碍垃圾收集器的效果，使 mutator 线程更容易超过收集器线程。 (我不清楚让多个线程改变列表有多重要。在测试用例中，它们都在列表上同步，因此没有实际的并行性。)更改为 LinkedList 以取消节点之间的链接使其更容易让收集器完成其工作，因此显然使测试不再耗尽内存。

快进到 2009 年，当时 LinkedList 代码进行了“整容”。这由错误 JDK-6897553 跟踪并在此 email review thread 中讨论。 “整容”的最初动机之一是将 clear() 操作从 O(n) 减少到 O(1)，因为对于该错误的提交者来说，取消所有节点的链接似乎是不必要的。 (这对我来说似乎没有必要!)但是经过一些讨论，决定取消链接行为为垃圾收集器提供了足够的好处来保留它并记录它。

该评论还说取消链接节点

is sure to free memory even if there is a reachable Iterator

这是指一个有点病态的案例，如下所示:

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

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

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

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