资讯专栏INFORMATION COLUMN

老哥你真的知道ArrayList#sublist的正确用法么

loonggg / 3495人阅读

摘要:我们有这么一个场景,给你一个列表,可以动态的新增,但是最终要求列表升序,要求长度小于,可以怎么做这个还不简单,几行代码就可以了测试验证上面的代码先不考虑性能的优化方面,有没有问题写了个简单的测试,我们来看下会出现什么情况启动参数修改

我们有这么一个场景,给你一个列表,可以动态的新增,但是最终要求列表升序,要求长度小于20,可以怎么做?

这个还不简单,几行代码就可以了

public List trimList(List list, int add) {
    list.add(add);
    list.sort(null);
    if (list.size() > 20) {
        list = list.subList(0, 20);
    }
    return list;
}

1. 测试验证

上面的代码先不考虑性能的优化方面,有没有问题?

写了个简单的测试case,我们来看下会出现什么情况

@Test
public void testTri() throws InterruptedException {
    List list = new ArrayList<>(30);
    Random random = new Random();
    int cnt = 0;
    while (true) {
        list = trimList(list, random.nextInt(100000));

        Thread.sleep(1);
        ++cnt;
        System.out.println(list + " >> " + cnt);
    }
}

启动参数修改下,添加jvm最大内存条件 -Xmx3m, 然后跑上面代码,一段时间之后居然出现stack over flow

有意思的问题来了,从逻辑上看,这个数组固定长度为20,顶多有21条数据,怎么就会内存溢出呢?

2. SubList 方法揭秘

我们看下ArrayList#sublis方法的实现逻辑,就可以发现获取子列表,居然只是重置了一下内部数组的索引

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

private class SubList extends AbstractList implements RandomAccess {
    private final AbstractList parent;
    private final int parentOffset;
    private final int offset;
    int size;
  
    SubList(AbstractList 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;
    }
    ...
}

返回的是一个SubList类型对象,这个对象和原来的List公用一个存储数据的数组,但是多了两个记录子列表起始的偏移;

然后再看下SubList的add方法,也是直接在原来的数组中新增数据,想到与原来的列表在指定位置插入数据

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

所以上面实现的代码中 list = list.subList(0, 20); 这一行,有内存泄露,貌似是只返回了一个20长度大小的列表,但是这个列表中的数组长度,可能远远不止20

为了验证上面的说法,debug下上面的测试用例

动图演示如下

3. 正确使用姿势

上面知道sublist并不会新创建一个列表,旧的数据依然还在,只是我们用不了而已,所以改动也很简单,根据sublist的结果创建一个新的数组就好了

public List trimList(List list, int add) {
    list.add(add);
    list.sort(null);
    if (list.size() > 20) {
        list = new ArrayList<>(list.subList(0, 20));
    }
    return list;
}

再次测试,代码一直在顺利的执行,看下后面的计数,都已经5w多,前面1w多久报错了

虽然上面解决了内存泄露,但是gc也很频繁了,本篇的重点主要是指出sublist的错误使用姿势,所以上面算法的优化就不详细展开了

4. 知识点扩展

看下下面的测试代码输出应该是什么

@ToString
public static class InnerC {
    private String name;
    private Integer id;

    public InnerC(String name, Integer id) {
        this.name = name;
        this.id = id;
    }
}

@Test
public void subList() {
    List list = new ArrayList<>();
    for (int i = 0; i < 20; i++) {
        list.add(i);
    }

    // case 1
    List sub = list.subList(10, 15);
    sub.add(100);
    System.out.println("list: " + list);
    System.out.println("sub: " + sub);

    // case 2
    list.set(11, 200);
    System.out.println("list: " + list);
    System.out.println("sub: " + sub);

    // case 3
    list = new ArrayList<>(sub);
    sub.set(0, 999);
    System.out.println("list: " + list);
    System.out.println("sub: " + sub);

    // case 4
    List cl = new ArrayList<>();
    cl.add(new InnerC("a", 1));
    cl.add(new InnerC("a2", 2));
    cl.add(new InnerC("a3", 3));
    cl.add(new InnerC("a4", 4));

    List cl2 = new ArrayList<>(cl.subList(1, 3));
    cl2.get(0).name = "a5";
    cl2.get(0).id = 5;
    System.out.println("list cl: " + cl);
    System.out.println("list cl2: " + cl2);
}

再看具体的答案之前,先分析一下

针对case1/2,我们知道sublist返回的列表和原列表公用一个底层数组,所以这两个列表的增删,都是相互影响的

case1 执行之后相当于在list数组的下标15这里,插入数据100

case2 执行之后,list的下标11,相当于sub的下标1,也就是说sub[1] 变成了200

对于case3/4 而言,根据sub创建了一个新的列表,这个时候修改新的列表中的值,会影响到原来的列表中的值么?

分析这个场景,就需要看一下源码了

public ArrayList(Collection c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

// 对应的核心逻辑就在 Arrays.copyOf,而这个方法主要调用的是native方法`System.arraycopy`

public static  T[] copyOf(U[] original, int newLength, Class newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

从上面的源码分析,会不会相互影响就看这个数组拷贝是怎么实现的了(深拷贝?浅拷贝?)

接下来看下实际的输出结果

list: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 100, 15, 16, 17, 18, 19]
sub: [10, 11, 12, 13, 14, 100]
list: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 200, 12, 13, 14, 100, 15, 16, 17, 18, 19]
sub: [10, 200, 12, 13, 14, 100]
list: [10, 200, 12, 13, 14, 100]
sub: [999, 200, 12, 13, 14, 100]
list cl: [BasicTest.InnerC(name=a, id=1), BasicTest.InnerC(name=a5, id=5), BasicTest.InnerC(name=a3, id=3), BasicTest.InnerC(name=a4, id=4)]
list cl2: [BasicTest.InnerC(name=a5, id=5), BasicTest.InnerC(name=a3, id=3)]

从上面可以知道,case1/2的分析没啥问题,case3、4的输出有点意思了

数组内为Integer时,两者互不影响

数组内为普通对象时,修改其中一个,会影响另外一个

关从输出结果来看 System.arraycopy 是浅拷贝,至于为什么int不影响呢,这个就和方法调用传参是基本数据类型时,在方法内部修改参数不会影响到外部一个道理了

II. 其他

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

微博地址: 小灰灰Blog

QQ: 一灰灰/3302797840

个人博客站点 一灰灰Blog: https://liuyueyi.github.io/he...

一灰灰blog

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/74653.html

相关文章

  • 寻找Java中String.split性能更好方法

    摘要:有没有更快的方法如果分隔符不是单字符而且也不需要按正则分隔的话,使用的方法还会和一样使用正则表达式。使用分隔字符串,针对不需要按正则分隔的场景提供更好的实现,分隔符支持字符串。 String.split 是Java里很常用的字符串操作,在普通业务操作里使用的话并没有什么问题,但如果需要追求高性能的分割的话,需要花一点心思找出可以提高性能的方法。 String.split方法的分割参数r...

    QiShare 评论0 收藏0
  • 了解集合世界fail-fast机制 和 CopyOnWriteArrayList 源码详解

    摘要:体现的就是适配器模式。数组对象集合世界中的机制机制集合世界中比较常见的错误检测机制,防止在对集合进行遍历过程当中,出现意料之外的修改,会通过异常暴力的反应出来。而在增强循环中,集合遍历是通过进行的。 前言 学习情况记录 时间:week 2 SMART子目标 :Java 容器 记录在学习Java容器 知识点中,关于List的重点知识点。 知识点概览: 容器中的设计模式 从Array...

    young.li 评论0 收藏0
  • 源码|jdk源码-ArrayList与Vector源码阅读

    摘要:毕业两个星期了,开始成为一名正式的码农了。将指定位置的数据移除。但是问题是,为时,并不是直接一个大小为的数组,而是使用静态变量来代替。此外,函数还做了越界检查。返回迭代器,与之有一个搭配的辅助类。 毕业两个星期了,开始成为一名正式的java码农了。一直对偏底层比较感兴趣,想着深入自己的java技能,看书、读源码、总结、造轮子实践都是付诸行动的方法。说到看源码,就应该由简入难,逐渐加深,...

    0x584a 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<