Java Record是否适合表示图节点及正确使用方法

图论中表示图结构的经典实现方式之一如下：

class Node {
  String value;
  List<Node> children;

  // 构造方法、equals等方法省略
}

本问题围绕Java 14引入的Record新特性展开。
具体疑问为：在实现DFS这类图算法时，使用如下所示的Node声明是否存在潜在陷阱？

record Node(String value, List<Node> children) {}

其中一个潜在问题与Record自动生成的equals/hashCode方法有关：对于存在循环引用的Node结构，Record默认实现的这两个方法会触发无限递归，最终抛出StackOverflow（栈溢出）错误。
例如，如下使用Set集合实现DFS的代码就会触发该问题：

import java.util.*;

class SO {
    
  static void dfs(Node n, Set<Node> visited) {
    if (n == null) return;
    System.out.println("visited " + n.value());
    for (Node child : n.children()) {
      if (visited.contains(child)) continue;
      visited.add(child);
      dfs(child, visited);
    }
  }

  public static void main(String[] args) {
    var a = new Node("a", new ArrayList<>());
    var b = new Node("b", new ArrayList<>());
    a.children().add(b);
    b.children().add(a);
    dfs(a, new HashSet<>());
  }

}

record Node(String value, List<Node> children) {}

上述代码运行后会抛出栈溢出错误，报错信息如下：

% java SO.java
visited a
Exception in thread "main" java.lang.StackOverflowError
    at Node.hashCode(SO.java:25)
    at java.base/java.util.ArrayList.hashCodeRange(ArrayList.java:595)
    at java.base/java.util.ArrayList.hashCode(ArrayList.java:582)
    at java.base/java.util.Objects.hashCode(Objects.java:103)
    at Node.hashCode(SO.java:25)
    ... <省略其余栈帧> ...

该现象不代表Record普遍不适用于图算法实现。这个问题本质是默认生成的equals/hashCode语义和图节点的去重需求不匹配：哪怕不用Record，只要是普通类写equals/hashCode时把邻接节点列表纳入计算，碰到循环引用一样会触发栈溢出，只是Record默认会按所有字段生成这两个方法，更容易踩坑而已。
使用Record实现图算法时，可通过以下方式规避问题：

• 自定义equals和hashCode实现，不将邻接节点列表纳入计算逻辑。图节点的身份判定通常只和节点唯一标识有关，和邻接关系无关。如果value是节点唯一标识，可以仅基于该字段实现两个方法：

record Node(String value, List<Node> children) {
  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Node node = (Node) o;
    return Objects.equals(value, node.value);
  }

  @Override
  public int hashCode() {
    return Objects.hash(value);
  }
}

• 图遍历时使用基于引用相等的访问标记集合，不依赖Node自身的equals/hashCode。比如用Collections.newSetFromMap(new IdentityHashMap<>())代替HashSet存储已访问节点，这类集合仅通过对象内存地址判断是否为同一个节点，完全不会调用对象的equals和hashCode方法，从根源上避免递归调用问题，是图遍历场景下通用性更强的方案。对前述报错示例，仅修改visited集合的初始化逻辑即可正常运行：

dfs(a, Collections.newSetFromMap(new IdentityHashMap<>()));

• 如果要实现不可变图，建议在Record构造器中对children列表做防御性拷贝，直接存入不可变列表，避免节点构造完成后再修改邻接关系，减少循环引用带来的不可预期问题。

内容的提问来源于stack exchange，提问作者Jobin Jacob Kavalam