java - 如何在Java中为单向链表节点高效实现hashCode()？

Question

Eclipse 实现了 hashCode()单向链表的 Node 类的函数如下:

class Node{
    int val;
    Node next;

    public Node(int val){
        this.val = val;
        next = null;
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((next == null) ? 0 : next.hashCode());
        result = prime * result + val;
        return result;
    }
}

现在hashCode()一个节点的哈希值取决于跟随它的节点的哈希码。

所以，每次调用hashCode()将在链表的长度上花费摊销的线性时间。因此使用 HashSet<Node>将变得不可行。

解决这个问题的一种方法是缓存 hashCode 的值在一个变量中(称之为散列)，以便它只计算一次。但即使在这种情况下，一旦任何节点的 val 发生变化，hash 也会变得无效。同样，修改 hashCode 将花费线性时间。当前节点之后的节点数。

那么对于这样的链表Node，有哪些好的哈希实现方式呢？

Answer 1

阅读您的问题后，我的第一个想法是: LinkedList 是什么意思？做？深入研究源代码，我们发现没有 hashCode()。或 equals()定义在内部 LinkedList.Node类(link to source)。

为什么这是有道理的？好吧，节点通常是内部数据结构，只对列表本身可见。它们不会被放入集合或任何其他需要比较相等性和哈希码的数据结构中。没有外部代码可以访问它们。

你在问题​​中说:

Thus using a HashSet<Node> will become unfeasible.

但我认为您没有必要将您的节点放在这样的数据结构中。根据定义，您的节点将相互链接并且不需要额外的类来促进这种关系。并且除非您计划在您的列表之外公开此类(这不是必需的)，否则它们永远不会以 HashSet 结束。 .

我建议您关注 LinkedList.Node建模并避免在您的节点上创建这些方法。外部列表可以将其哈希码和相等性基于存储在节点中的值(而不是节点本身)，这就是 LinkedList 的方式。是吗 - 见 AbstractList (link to source)。

_{源链接指向 OpenJDK 源，但在这种情况下它们与 Oracle JDK 提供的源相同}