我們有這么一個場景，給你一個列表蠢琳，可以動態(tài)的新增，但是最終要求列表升序镜豹，要求長度小于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. 測試驗(yàn)證
上面的代碼先不考慮性能的優(yōu)化方面泰讽，有沒有問題？
寫了個簡單的測試case，我們來看下會出現(xiàn)什么情況
@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);
}
}
啟動參數(shù)修改下已卸，添加jvm最大內(nèi)存條件 -Xmx3m佛玄， 然后跑上面代碼，一段時間之后居然出現(xiàn)stack over flow
有意思的問題來了累澡，從邏輯上看梦抢，這個數(shù)組固定長度為20，頂多有21條數(shù)據(jù)愧哟，怎么就會內(nèi)存溢出呢奥吩？
2. SubList 方法揭秘
我們看下ArrayList#sublis方法的實(shí)現(xiàn)邏輯，就可以發(fā)現(xiàn)獲取子列表蕊梧，居然只是重置了一下內(nèi)部數(shù)組的索引
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公用一個存儲數(shù)據(jù)的數(shù)組，但是多了兩個記錄子列表起始的偏移;
然后再看下SubList的add方法肥矢，也是直接在原來的數(shù)組中新增數(shù)據(jù)绩脆，想到與原來的列表在指定位置插入數(shù)據(jù)
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
所以上面實(shí)現(xiàn)的代碼中 list = list.subList(0, 20); 這一行，有內(nèi)存泄露橄抹，貌似是只返回了一個20長度大小的列表，但是這個列表中的數(shù)組長度惕味，可能遠(yuǎn)遠(yuǎn)不止20
為了驗(yàn)證上面的說法楼誓，debug下上面的測試用例
動圖演示如下
3. 正確使用姿勢
上面知道sublist并不會新創(chuàng)建一個列表，舊的數(shù)據(jù)依然還在名挥，只是我們用不了而已疟羹，所以改動也很簡單，根據(jù)sublist的結(jié)果創(chuàng)建一個新的數(shù)組就好了
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;
}
再次測試禀倔，代碼一直在順利的執(zhí)行榄融，看下后面的計(jì)數(shù)，都已經(jīng)5w多救湖，前面1w多久報錯了
雖然上面解決了內(nèi)存泄露愧杯，但是gc也很頻繁了，本篇的重點(diǎn)主要是指出sublist的錯誤使用姿勢鞋既，所以上面算法的優(yōu)化就不詳細(xì)展開了
4. 知識點(diǎn)擴(kuò)展
看下下面的測試代碼輸出應(yīng)該是什么
@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返回的列表和原列表公用一個底層數(shù)組邑闺，所以這兩個列表的增刪跌前，都是相互影響的
- case1 執(zhí)行之后相當(dāng)于在list數(shù)組的下標(biāo)15這里，插入數(shù)據(jù)100
- case2 執(zhí)行之后陡舅，list的下標(biāo)11抵乓，相當(dāng)于sub的下標(biāo)1，也就是說sub[1] 變成了200
對于case3/4 而言，根據(jù)sub創(chuàng)建了一個新的列表灾炭，這個時候修改新的列表中的值茎芋，會影響到原來的列表中的值么？
分析這個場景咆贬，就需要看一下源碼了
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;
}
}
// 對應(yīng)的核心邏輯就在 Arrays.copyOf败徊，而這個方法主要調(diào)用的是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;
}
從上面的源碼分析，會不會相互影響就看這個數(shù)組拷貝是怎么實(shí)現(xiàn)的了（深拷貝掏缎？淺拷貝皱蹦？）
接下來看下實(shí)際的輸出結(jié)果
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的輸出有點(diǎn)意思了
- 數(shù)組內(nèi)為Integer時，兩者互不影響
- 數(shù)組內(nèi)為普通對象時酌儒，修改其中一個辜妓，會影響另外一個
關(guān)從輸出結(jié)果來看 System.arraycopy 是淺拷貝，至于為什么int不影響呢忌怎，這個就和方法調(diào)用傳參是基本數(shù)據(jù)類型時籍滴，在方法內(nèi)部修改參數(shù)不會影響到外部一個道理了
II. 其他
盡信書則不如，已上內(nèi)容榴啸，純屬一家之言孽惰，因個人能力有限，難免有疏漏和錯誤之處鸥印，如發(fā)現(xiàn)bug或者有更好的建議勋功，歡迎批評指正，不吝感激
- 微博地址: 小灰灰Blog
- QQ： 一灰灰/3302797840
- 個人博客站點(diǎn) 一灰灰Blog： https://liuyueyi.github.io/hexblog
一灰灰blog
