Horrendous performance & large heap footprint of Java 8 constructor reference?

The computeIfAbsent signature is the following:

V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)

So the mappingFunction is the function which receives one argument. In your case K = Integer and V = List<Integer>, so the signature becomes (omitting PECS):

Function<Integer, List<Integer>> mappingFunction

When you write ArrayList::new in the place where Function<Integer, List<Integer>> is necessary, compiler looks for the suitable constructor which is:

public ArrayList(int initialCapacity)

So essentially your code is equivalent to

map.computeIfAbsent(index, i->new ArrayList<>(i)).add(index);

And your keys are treated as initialCapacity values which leads to pre-allocation of arrays of ever increasing size, which, of course, quite fast leads to OutOfMemoryError.

In this particular case constructor references are not suitable. Use lambdas instead. Were the Supplier<? extends V> used in computeIfAbsent, then ArrayList::new would be appropriate.

In the first case (ArrayList::new) you are using the constructor which takes an initial capacity argument, in the second case you are not. A large initial capacity (index in your code) causes a large Object[] to be allocated, resulting in your OutOfMemoryErrors.

Here are the two constructors' current implementations:

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

Something similar happens in HashSet, except the array is not allocated until add is called.