包含自身作为元素的 ArrayList 的哈希码

Question

我们可以发现hashcode的list是本身含有的element？

我知道这是一个不好的做法，但这是面试官问的。

当我运行以下代码时，它会抛出一个StackOverflowError：

public class Main {
    public static void main(String args[]) {
        ArrayList<ArrayList> a = new ArrayList();
        a.add(a);
        a.hashCode();
    }
}

现在我有两个问题：

1. 为什么有一个StackOverflowError？
2. 是否可以通过这种方式找到哈希码？

Answer 1

接口中指定了符合List实现的哈希码：

返回此列表的哈希码值。列表的哈希码定义为以下计算的结果：

 int hashCode = 1;
 for (E e : list)
     hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

这可确保list1.equals(list2)意味着list1.hashCode()==list2.hashCode()对于任何两个列表，list1并list2根据需要通过的总承包合同Object.hashCode()。

这并不要求实现看起来完全一样（请参阅如何以与 List.hashCode() 相同的方式计算流的哈希码以获取替代方案），但仅包含自身的列表的正确哈希码将是一个x == 31 + x必须为 的数字true，换句话说，不可能计算出符合要求的数字。

Answer 2

查看类中hashCode方法的骨架实现AbstractList。

public int hashCode() {
    int hashCode = 1;
    for (E e : this)
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    return hashCode;
}

对于列表中的每个元素，这会调用hashCode. 在您的案例列表中，它是唯一的元素。现在这个电话永远不会结束。该方法以递归方式调用自身，并且递归不断缠绕，直到遇到StackOverflowError. 所以你找不到hashCode这种方式。

Answer 3

您已经定义了一个包含自身的（病理）列表。

为什么有StackOverflowError？

根据javadocs（即规范），a 的hashcodeList被定义为其每个元素的hashcode 的函数。它说：

“列表的哈希码定义为以下计算的结果：”

int hashCode = 1;
    for (E e : list)
         hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

因此，要计算 的哈希码a，首先要计算 的哈希码a。这是无限递归的，并很快导致堆栈溢出。

是否可以通过这种方式找到哈希码？

不。如果您从数学角度考虑上述算法规范，则List包含自身的 a的哈希码是一个不可计算的函数。不可能以这种方式（使用上述算法）或任何其他方式计算它。

Answer 4

不，文档有答案

List 结构的文档明确指出：

注意：虽然允许列表将自身包含为元素，但建议格外小心：equals 和 hashCode 方法不再在此类列表上明确定义。

除此之外没有什么可说的——根据 Java 规范，您将无法为包含自身的列表计算 hashCode；其他答案详细说明了为什么会这样，但关键是它是已知且有意的。