内容简介:我们有这么一个场景,给你一个列表,可以动态的新增,但是最终要求列表升序,要求长度小于20,可以怎么做?这个还不简单,几行代码就可以了<!-- more -->
我们有这么一个场景,给你一个列表,可以动态的新增,但是最终要求列表升序,要求长度小于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; }
<!-- more -->
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
有意思的问题来了,从逻辑上看,这个数组固定长度为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下上面的测试用例
动图演示如下
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多久报错了
虽然上面解决了内存泄露,但是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<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)]
从上面可以知道,case1/2的分析没啥问题,case3、4的输出有点意思了
- 数组内为Integer时,两者互不影响
- 数组内为普通对象时,修改其中一个,会影响另外一个
关从输出结果来看 System.arraycopy
是浅拷贝,至于为什么int不影响呢,这个就和方法调用传参是基本数据类型时,在方法内部修改参数不会影响到外部一个道理了
II. 其他
尽信书则不如,已上内容,纯属一家之言,因个人能力有限,难免有疏漏和错误之处,如发现bug或者有更好的建议,欢迎批评指正,不吝感激
- 微博地址:小灰灰Blog
- QQ: 一灰灰/3302797840
- 个人博客站点 一灰灰Blog : https://liuyueyi.github.io/he...
一灰灰blog
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Namo Webeditor5.5一看就懂.
吳聲毅 / 金禾資訊 / 20040214 / NT$ 169
一看就懂系列書全以初學者的角度切入,全書以STEP BY STEP方式撰寫,並以豐富的圖片搭配教學,在最後更加上日常生活實例運用講解,一路學來一氣呵成。為了增進學習的效率更採用高級紙品全彩印刷,這麼好的書,您還在等什麼,一看就懂系列書保證是您最佳入門學習好伙伴。 本書特色: 1、一看就懂:Step by Step操作詳盡說明、讓您一看就懂 2、精選範例:精彩實務範例生動活......一起来看看 《Namo Webeditor5.5一看就懂.》 这本书的介绍吧!