Java / 编程技巧
9 分钟 读完 (大约 1284 个字) 0次访问

210819-实战小技巧9：List.subList使用不当StackOverflowError

文章目录
  1. 1. subList
  2. 2. StackOverflowError分析
  3. 3. 小结
  • II. 其他
    1. 1. 一灰灰Blog： https://liuyueyi.github.io/hexblog
    2. 2. 声明
    3. 3. 扫描关注

    • 实战小技巧：List.subList使用不当StackOverflowError

    相信每个小伙伴都使用过List.subList来获取子列表，日常使用可能没啥问题，但是，请注意，它的使用，很可能一不小心就可能导致oom

    1. subList

    场景复现，如基于list实现一个小顶堆

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    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() {
        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);
        }
    }

    上面这个执行完毕之后，居然出现栈溢出

    1
    2
    3
    4
    5
    6
    7
    // ....
    [2147462802, 2147462803, 2147462804, 2147462805, 2147462806]
    [2147462801, 2147462802, 2147462803, 2147462804, 2147462805]

    java.lang.StackOverflowError
    	at java.util.ArrayList$SubList.add(ArrayList.java:1057)
    	at java.util.ArrayList$SubList.add(ArrayList.java:1057)

    从实现来看，感觉也没啥问题啊， 我们稍微改一下上面的返回

    1
    2
    3
    4
    5
    6
    7
    8
    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));
    }

    再次执行，却没有异常；所以关键点就在与

    • list.subList的使用上

    2. StackOverflowError分析

    接下来我们主要看一下list.subList的实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    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;
        }
        ...
    }

    上面返回的子列表是ArrayList的一个内部类SubList，它拥有一个指向父列表的成员parrent

    也就是说，从源头的ArryList开始，后面每次调用subList，这个指代关系就深一层

    然后它的add方法也很有意思

    1
    2
    3
    4
    5
    6
    7
    public void add(int index, E e) {
        rangeCheckForAdd(index);
        checkForComodification();
        parent.add(parentOffset + index, e);
        this.modCount = parent.modCount;
        this.size++;
    }

    重点看 parent.add(parentOffset + index, e);，添加的数据实际上是加在最源头的ArrayList上的，也就是说，虽然你现在拿到的SubList，只有几个元素，但是它对应的数组，可能超乎你的想象

    当然上面这个异常主要是以为调用栈溢出（一直往上找parent）

    这里反应的另外一个重要问题则是内存泄漏，就不继续说了

    如果需要解决上面这个问题，改造方法如下

    1
    2
    3
    4
    public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new ArrayList<>(new SubList(this, 0, fromIndex, toIndex));
    }s

    3. 小结

    jdk提供的原生方法虽然非常好用，但是在使用的时候，也需要多家注意，一不小心就可能掉进坑里；这也告诉我们多看源码是有必要的

    最后一句关键知识点小结：

    • ArrayList.subList 返回的是内部类，与原ArrayList公用一个数组，只是限定了这个数组的起始下标和结束下标而已
    • 在使用subList，请注意是否会存在内存泄露和栈溢出的问题

    系列博文

    II. 其他

    1. 一灰灰Blog： https://liuyueyi.github.io/hexblog

    一灰灰的个人博客，记录所有学习和工作中的博文，欢迎大家前去逛逛

    2. 声明

    尽信书则不如，以上内容，纯属一家之言，因个人能力有限，难免有疏漏和错误之处，如发现bug或者有更好的建议，欢迎批评指正，不吝感激

    3. 扫描关注

    一灰灰blog

    QrCode

    # JDK, 编程技巧

    喜欢这篇文章？打赏一下作者吧

    210820-实战小技巧10：不可变容器
    210818-实战小技巧8：容器的初始化大小指定

    评论

    关注我
    Google Play    Android

    链接

    最新文章

    标签云

    AES Android Arthas AutoCloseable BeanUtil BloomFilter BufferedImage BugFix Bugfix CURL Chrome DNS Docker Dubbo ElasticSearch Email FastJson Git GitHub Grafana Groovy Gson Guava HashMap IDEA IO ImageMagic InfluxDB InputStream Iterator JDK JNDI JVM Jackson Java JavaAgent JavaScript JavaWeb Jquery Json LRU Linux List MD5 Map Maven Mongo MongoDB MongoDb MySql Mybatis Mysql Nginx Node OGNL Prometheus ProtoStuff Python QlExpress QuickAlarm QuickMedia RMI RabbitMQ ReactJS Redis SSL Shell Socket Solr Spring SpringBoot Vue WebSocket WebView Win10 Yaml ZooKeeper css curl dns ffmpeg git gitalk google grep hexo hostname jdk logger markdown named ncat python ssh ssl time tmux zsh 专业词汇 乱码 二维码 代理 内购 分库分表 反射 吐槽 子系统 工具 并发 序列化 手记 技术方案 指南 教程 方案设计 时区 时间窗口 爬虫 编程技巧 证书 问题记录 随笔

    标签

    AES 1
    Android 4
    Arthas 1
    AutoCloseable 1
    BeanUtil 2
    BloomFilter 1
    BufferedImage 2
    BugFix 2
    Bugfix 2
    CURL 2
    Chrome 2
    DNS 1
    Docker 5
    Dubbo 1
    ElasticSearch 7
    Email 1
    FastJson 1
    Git 3
    GitHub 1
    Grafana 3
    Groovy 1
    Gson 5
    Guava 5
    HashMap 1
    IDEA 4
    IO 2
    ImageMagic 2
    InfluxDB 17
    InputStream 1
    Iterator 1
    JDK 36
    JNDI 3
    JVM 3
    Jackson 1
    Java 75
    JavaAgent 2
    JavaScript 2
    JavaWeb 2
    Jquery 1
    Json 1
    LRU 1
    Linux 11
    List 1
    MD5 1
    Map 1
    Maven 4
    Mongo 2
    MongoDB 4
    MongoDb 10
    MySql 3
    Mybatis 2
    Mysql 21
    Nginx 7
    Node 1
    OGNL 4
    Prometheus 1
    ProtoStuff 2
    Python 142
    QlExpress 4
    QuickAlarm 1
    QuickMedia 3
    RMI 3
    RabbitMQ 9
    ReactJS 1
    Redis 9
    SSL 1
    Shell 21
    Socket 2
    Solr 1
    Spring 26
    SpringBoot 2
    Vue 1
    WebSocket 1
    WebView 2
    Win10 2
    Yaml 1
    ZooKeeper 1
    css 3
    curl 1
    dns 1
    ffmpeg 1
    git 2
    gitalk 1
    google 1
    grep 1
    hexo 1
    hostname 1
    jdk 1
    logger 1
    markdown 1
    named 1
    ncat 1
    python 2
    ssh 1
    ssl 1
    time 1
    tmux 2
    zsh 1
    专业词汇 1
    乱码 1
    二维码 3
    代理 1
    内购 1
    分库分表 1
    反射 3
    吐槽 1
    子系统 1
    工具 5
    并发 3
    序列化 1
    手记 6
    技术方案 22
    指南 6
    教程 21
    方案设计 1
    时区 1
    时间窗口 3
    爬虫 5
    编程技巧 15
    证书 1
    问题记录 1
    随笔 1

    分类

    归档

    分类

    归档

    Your browser is out-of-date!

    Update your browser to view this website correctly. Update my browser now

    ×