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

Question

我们能否找到包含自身为 element 的 list 的 hashcode？

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

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

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

现在我有两个问题：

为什么会有WhosebugError？
这样可以找到哈希码吗？

Answer 1

查看 AbstractList class 中 hashCode 方法的框架实现。

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

对于列表中的每个元素，调用 hashCode。在您的案例中，列表本身就是唯一的元素。现在这个电话永远不会结束。该方法递归调用自身，递归一直循环，直到遇到 WhosebugError。所以你无法通过这种方式找到hashCode。

Answer 2

因为当你从同一个函数调用同一个函数时，它会创建一个永不结束的递归条件。并且为了防止这个操作 JAVA will return java.lang.WhosebugError

下面是解释类似场景的示例代码：

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);
    }

}

Answer 3

Ravindra 的回答对第 1 点给出了很好的解释。评论问题 2：

Is it possible to find hash code in this way?

这里有一些循环。在这个堆栈溢出错误的上下文中，这两个中至少有一个是错误的：

列表的哈希码必须考虑其元素的哈希码
列表可以是它自己的元素

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

for (E e : this)
  if(e == this) continue; //contrived rules
  hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

使用这样的 class 而不是 ArrayList，你可以。

和ArrayList，第二点是错误的。所以如果面试官的意思是"Is it possible to find hash code in this way (with an array list)?"，那么答案是否定的，因为那是荒谬的。

Answer 4

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

Why there is WhosebugError ?

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

"The hash code of a list is defined to be the result of the following calculation:"
int hashCode = 1;
    for (E e : list)
         hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

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

Is it possible to find hash code in this way ?

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

Answer 5

符合 List 实现的哈希码 has been specified in the interface:

Returns the hash code value for this list. The hash code of a list is defined to be the result of the following calculation:
 int hashCode = 1;
 for (E e : list)
     hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
This ensures that list1.equals(list2) implies that list1.hashCode()==list2.hashCode() for any two lists, list1 and list2, as required by the general contract of Object.hashCode().

这并不要求实现看起来完全像那样（参见的替代方法），但是仅包含自身的列表的正确哈希码将是一个数字 x == 31 + x必须是true，换句话说，不可能计算出一个符合的数字。

Answer 6

没有，文档有答案

documentation of the List structure 明确指出：

Note: While it is permissible for lists to contain themselves as elements, extreme caution is advised: the equals and hashCode methods are no longer well defined on such a list.

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

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

Hash code of ArrayList that contains itself as element

java

java-8

stack-overflow

hashcode

没有，文档有答案