如何有效地实现hashCode（）单链表节点在Java？

Question

Eclipse通过以下方式为单链表的Node类实现hashCode（）函数：

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（）的每次调用都将在链表长度上花费摊销的线性时间。因此，使用哈希集

解决这一问题的一种方法是将hashCode的值缓存在变量中（称之为hash），以便只计算一次。但是即使在这种情况下，一旦任何节点的val被更改，散列也将变得无效。同样，修改跟随当前节点的节点的hashCode需要线性时间。

那么，对于这样的链表节点，有什么好的实现哈希的方法呢？




Answer 1

你必须问问自己什么样的散列质量对你来说是有价值的。唯一的限制是确保具有相同顺序的相同编号的另一个列表具有相同的哈希。这是通过使用contant数和第一个数以及限制5个数来实现的。多少数字对您有意义取决于数据的结构。例如，如果始终存储从1开始的连续升序数字，并且差值仅为长度，则很难进行优化。如果它在int的整个范围内是完全随机的，那么第一个数字将很好地完成这项工作。我会说，有多少数字能为你提供最佳的比率是通过测量得出的。

最后，您需要的是碰撞（放在同一个桶中的对象）和计算时间之间的良好比例。生成的实现通常试图最大化计算时间，为开发人员提供很大的改进空间

关于包含值的变化：java.util.HashSet（分别是它持有的HashMap）将计算它自己的哈希值，并缓存它。因此，如果HashSet中包含的对象一旦更改到哈希更改的程度，就无法再次找到。

Answer 2

读到你的问题时，我的第一个想法是：LinkedList做什么？深入研究源代码，我们发现在内部链接列表上没有定义hashCode（）或equals（）。节点类（链接到源）。

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

你在问题中说：

因此，使用哈希集

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

我建议您遵循链接列表。节点建模并避免在节点上创建这些方法。外部列表可以根据节点中存储的值（而不是节点本身）来确定其哈希代码和相等性，这就是LinkedList的工作方式-请参见AbstractList（链接到源代码）。

_{源代码链接指向OpenJDK源代码，但在本例中，它们与Oracle JDK提供的源代码相同}