Self Referential Collections throws stack overflow

Question

While learning Self Referential Collection I come up with where it is throwing Stack overflow error.

Please find the source code below.

import java.util.*;

public class TestSelfColl {

public static void main(final String[] args) {
    test(new ArrayList<Collection<?>>());
    test(new LinkedList<Collection<?>>());
    test(new HashSet<Collection<?>>());
    test(new LinkedHashSet<Collection<?>>());

}

private static void test(final Collection<Collection<?>> collection) {
    collection.add(collection);
    System.out.println(collection);
    try {
        System.out.println(collection.hashCode());
    } catch (final StackOverflowError err) {
        System.out.println(err + " for " + collection.getClass());
    }
  }

  }

Really want to know why this error is coming .

My expectation was i will get Output as :

[(this Collection)]

123

..

But in contrast i am getting ..

[(this Collection)]

java.lang.StackOverflowError for class java.util.ArrayList

...

Answer 1

It doesn't happen for AbstractCollection, since that class doesn't override Object's hashCode.

However, if you add an ArrayList as a member of itself, ArrayList's hashCode runs into infinite recursion, since an ArrayList's hashCode (implemented in AbstractList) is a function of its elements' hashCodes :

public int hashCode() {
    int hashCode = 1;
    for (E e : this)
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode()); // e.hashCode() is a self call in your example
    return hashCode;
}

The reason that toString doesn't cause the same infinite recursion is this check (in AbstractCollection, which is not overridden by ArrayList) :

public String toString() {
    Iterator<E> it = iterator();
    if (! it.hasNext())
        return "[]";

    StringBuilder sb = new StringBuilder();
    sb.append('[');
    for (;;) {
        E e = it.next();
        sb.append(e == this ? "(this Collection)" : e); // here self calls are prevented
        if (! it.hasNext())
            return sb.append(']').toString();
        sb.append(',').append(' ');
    }
}

Answer 2

AbstractCollection.toString() has a simple check to stop recursion for collections containing themselves.

Adding the same check to AbstractSet.hashCode() and AbstractList.hashCode() will solve it