Hash code of ArrayList that contains itself as element

Question

Can we find the hashcode of a list that contains itself as element?

I know this is a bad practice, but this is what the interviewer asked.

When I ran the following code it throws a StackOverflowError:

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

Now here I have two questions:

1. Why is there a StackOverflowError?
2. Is it possible to find the hash code in this way?

Answer 1

The hash code for conforming List implementations 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().

This doesn’t require that the implementation looks exactly like that (see How to compute the hash code for a stream in the same way as List.hashCode() for an alternative), but the correct hash code for a list only containing itself would be a number for which x == 31 + x must be true, in other words, it is impossible to calculate a conforming number.

Answer 2

Check out the skeletal implementation of the hashCode method in AbstractList class.

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

For each element in the list, this calls hashCode. In your case list has itself as it's sole element. Now this call never ends. The method calls itself recursively and the recursion keeps winding until it encounters the StackOverflowError. So you can not find the hashCode this way.

Answer 3

You have defined a (pathological) list that contains itself.

Why there is StackOverflowError ?

According to the javadocs (i.e. the specification), the hashcode of a List is defined to a function of the hashcode of each of its elements. It says:

"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());

So to compute the hashcode of a, you first compute the hashcode of a. That is infinitely recursive and leads quickly to a stack overflow.

Is it possible to find hash code in this way ?

No. If you consider the algorithmic specification above in mathematical terms, the hashcode of a List that contains itself is a non-computable function. It is not possible to compute it this way (using the above algorithm) or any other way.

Answer 4

No, the documentation has an answer

The documentation of the List structure explicitly states:

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.

There's not much more to say beyond that - according to the Java specification, you won't be able to calculate hashCode for a list that contains itself; other answers go into detail why it's so, but the point is that it is known and intentional.