包含自身的ArrayList的哈希码

Question

我们能否找到包含自身作为元素的列表的哈希码？

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

[当我尝试运行此代码时，它抛出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实现has been specified in the interface的哈希码：

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

 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()。

这不需要实现看起来完全一样（替代方法，请参见Object.hashCode()），但是仅包含自身的列表的正确哈希码将是How to compute the hash code for a stream in the same way as List.hashCode()必须为x == 31 + x的数字，换句话说，不可能计算出符合数。

Answer 2

检查true类中hashCode方法的基本实现。

AbstractList

对于列表中的每个元素，此调用

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

。在您的情况下，列表本身就是唯一的元素。现在，此呼叫永无止境。该方法递归调用自身，直到遇到stackoverflow错误。

Answer 3

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

为什么有hashCode？

根据StackOverflowError（即规范），javadocs的哈希码被定义为其每个元素的哈希码的函数。它说：

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

List

因此要计算

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

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

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

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

进行计算。

Answer 4

因为当您从同一个函数调用同一个函数时，它将创建递归条件，该条件永远不会结束。为了防止此操作，JAVA将返回List

下面是解释类似情况的示例代码：

java.lang.StackOverflowError

Answer 5

[拉文德拉的答案很好地解释了第1点。对问题2进行评论]]

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

这里有些圆形。在此堆栈溢出错误的情况下，这2个中的至少一个必须是错误的：

• 列表的哈希码必须考虑其元素的哈希码
• 列表可以成为其自己的元素就可以了

现在，因为我们正在处理

public class RefTest {

    public static void main(String... strings) {
        RefTest rf = new RefTest();
        rf.message(message("test"));
    }

    public static String message2(String s){
        return message(s);
    }

    public static String message(String s){
        return message2(s);
    }

}   

，所以第一点是固定的。换句话说，也许您需要一种不同的实现方式才能有意义地计算递归列表的哈希码...可以扩展ArrayList并跳过添加元素的哈希码，例如

ArrayList
可以使用此类而不是for (E e : this)
  if(e == this) continue; //contrived rules
  hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
。>
使用ArrayList，第二点是错误的。因此，如果面试官的意思是“是否可以通过这种方式找到哈希码（带有数组列表）？”

，那么答案是否定的，因为这很荒谬。