This is the 19th day of my participation in the August Wenwen Challenge.More challenges in August

List. SubList is used incorrectly StackOverflowError

SubList can be used to retrieve sublists. SubList can be used to retrieve sublists. SubList can be used to retrieve sublists

1. subList

Scenario repetition, such as implementing a small top heap based on a list

public List<Integer> minStack(List<Integer> list, int value, int stackSzie) {
    list.add(value);
    if (list.size() < stackSzie) {
        return list;
    }
    list.sort(null);
    return list.subList(0, stackSzie);
}

@Test
public void testFix(a) {
    List<Integer> list = new ArrayList<>();
    for (int i = Integer.MAX_VALUE; i > Integer.MIN_VALUE; i--) {
        list.add(i);
        list = minStack(list, i, 5); System.out.println(list); }}Copy the code

After the above execution, there is a stack overflow

/ /... [2147462801, 2147462802, 2147462803, 2147462804, 2147462805, 2147462806] 2147462805] java.lang.StackOverflowError at java.util.ArrayList$SubList.add(ArrayList.java:1057) at java.util.ArrayList$SubList.add(ArrayList.java:1057)Copy the code

From the implementation point of view, it doesn’t feel like a problem. Let’s change the above return slightly

public List<Integer> minStack(List<Integer> list, int value, int stackSzie) {
    list.add(value);
    if (list.size() < stackSzie) {
        return list;
    }
    list.sort(null);
    return new ArrayList<>(list.subList(0, stackSzie));
}
Copy the code

Execute again, but no exception; So the key point is with

  • List. SubList

2. StackOverflowError analysis

Next we’ll focus on the implementation of list.sublist

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this.0, fromIndex, toIndex);
}

private class SubList extends AbstractList<E> implements RandomAccess {
    private final AbstractList<E> parent;
    private final int parentOffset;
    private final int offset;
    int size;
  
    SubList(AbstractList<E> parent,
            int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount; }... }Copy the code

The SubList returned above is an inner class of ArrayList, SubList, that has a parent member pointing to the parent list

That is, starting with the ArryList at the source, the reference gets deeper each time subList is called

And then its add method is also interesting

public void add(int index, E e) {
    rangeCheckForAdd(index);
    checkForComodification();
    parent.add(parentOffset + index, e);
    this.modCount = parent.modCount;
    this.size++;
}
Copy the code

Parent. Add (parentOffset + index, e); The added data is actually added to the original ArrayList, which means that even though you have a SubList that has only a few elements, its corresponding array is bigger than you might think

Of course, the above exception is mainly because the call stack overflow (go up to the parent).

Another important problem reflected here is memory leaks

If you want to solve the above problem, it is also very simple, the following transformation can be

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new ArrayList<>(new SubList(this.0, fromIndex, toIndex));
}
Copy the code

3. Summary

JDK provides native methods although very easy to use, but in the use of time, also need more attention, accidentally may fall into the pit; It also tells us that it is necessary to read the source code

Summary of the last key point:

  • ArrayList.subListIt returns an inner class that shares an array with the original ArrayList, except that the array’s starting and ending indices are specified
  • In the use ofsubList, please note whether there are memory leaks and stack overflows

Series of blog posts

  • Practical tip 1: String placeholder replacement -JDK version
  • Practice Tip 2: Array and list are rotated
  • Practice Tip 3: String and container transfer
  • Practical tip 4: Elegant string concatenation implementation
  • Practice tip 5: Hump and underline turn each other
  • Practice Tip 6: Special use of enumeration
  • Practice Tip 7: Sort carefully

II. The other

1. A gray Blog:liuyueyi.github.io/hexblog

A gray personal blog, recording all the study and work in the blog, welcome everyone to go to stroll

2. Statement

As far as the letter is not as good, the above content is purely one’s opinion, due to the limited personal ability, it is inevitable that there are omissions and mistakes, if you find bugs or have better suggestions, welcome criticism and correction, don’t hesitate to appreciate

  • Micro Blog address: Small Gray Blog
  • QQ: a gray /3302797840
  • Wechat official account: One Grey Blog