当前位置： 移动技术网 > IT编程>开发语言>Java > 老哥你真的知道ArrayList#sublist的正确用法么

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

2019年05月26日  | 移动技术网IT编程  | 我要评论

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

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

public list<integer> trimlist(list<integer> 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<integer> 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

sof

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

2. sublist 方法揭秘

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

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;
    }
    ...
}

返回的是一个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下上面的测试用例

debug

动图演示如下

gif

3. 正确使用姿势

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

public list<integer> trimlist(list<integer> list, int add) {
    list.add(add);
    list.sort(null);
    if (list.size() > 20) {
        list = new arraylist<>(list.sublist(0, 20));
    }
    return list;
}

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

show

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

sof

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<integer> list = new arraylist<>();
    for (int i = 0; i < 20; i++) {
        list.add(i);
    }

    // case 1
    list<integer> 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<innerc> 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<innerc> 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<? extends e> 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,u> t[] copyof(u[] original, int newlength, class<? extends t[]> 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)]

out

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

  • 数组内为integer时，两者互不影响
  • 数组内为普通对象时，修改其中一个，会影响另外一个

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

ii. 其他

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

一灰灰blog

qrcode

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网