jdk源码分析之List--使用中的坑

之前讲解了一篇 jdk源码分析之List--常用实现类分析与对比，讲述了常用List实现类以及使用方式和性能对比，那么此篇文章针对List使用过程中遇到的一些坑做一些总结和分析。

循环remove

有下边一段程序:

public static void main(String[] args) {

List<Integer> list = new ArrayList<>(10);

for(int i = 0; i < 10; i ++) {

list.add(i + 1);

}

System.out.println("remove之前:" + JSON.toJSONString(list));

for(int i = 0;i < list.size();i ++) {

if(list.get(i) > 2) {

list.remove(i);

}

}

System.out.println("剩余元素:" + JSON.toJSONString(list));

}

运行结果应该如何呢？

我们期望结果是剩余元素打印:1

运行程序看一下:

从运行结果中可以看到，程序并没有得到我们期望的结果，为什么？

先不做解释，看下图：

图中我们演示了循环删除元素的执行步骤，导致程序运行结果和我们预期不一致的原因，有一个很关键的点，就是for循环中i < list.size(),因为随着我们移除元素，list.size()是逐渐变小的，导致循环过程中i的左边界是递增的，右边界是递减的，出现了元素删不掉，也就是上图中的效果。

那么如果提前把list.size()存储起来再执行for循环移除元素，效果会如何呢？我们把上边的代码稍微做一下改动：

public static void main(String[] args) {

List<Integer> list = new ArrayList<>(10);

for(int i = 0; i < 10; i ++) {

list.add(i + 1);

}

System.out.println("remove之前:" + JSON.toJSONString(list));

for(int i = 0,size = list.size();i < size;i ++) {

if(list.get(i) > 2) {

list.remove(i);

}

}

System.out.println("剩余元素:" + JSON.toJSONString(list));

}

我们把list.size()提前存储到size，每次循环比较i < size即可，那么程序运行结果又如何呢？

看到了下表越界异常，为什么，继续看下图:

那么list中循环移除元素就无解了吗？不，for循环对于遍历List比较擅长性能较好，对于更新操作显得力不从心，那么专业的事情就交给专业的人去做，这时候迭代器就要大发神威了，再次修改代码如下:

public static void main(String[] args) {

List<Integer> list = new ArrayList<>(10);

for(int i = 0; i < 10; i ++) {

list.add(i + 1);

}

System.out.println("remove之前:" + JSON.toJSONString(list));

Iterator<Integer> iterator = list.iterator();

while (iterator.hasNext()) {

Integer temp = iterator.next();

if(temp.intValue() > 2) {

iterator.remove();

}

}

System.out.println("剩余元素:" + JSON.toJSONString(list));

}

运行程序：

可以看到这次我们得到了我们期望的结果，为什么呢？我们看一下list中iterator的实现原理:

1）iterator()方法

/**

* Returns an iterator over the elements in this list in proper sequence.

*

* <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.

*

* @return an iterator over the elements in this list in proper sequence

*/

public Iterator<E> iterator() {

return new Itr();

}

新建了一个Itr对象并返回

2）Itr类

/**

* An optimized version of AbstractList.Itr

*/

private class Itr implements Iterator<E> {

int cursor; // index of next element to return

int lastRet = -1; // index of last element returned; -1 if no such

int expectedModCount = modCount;

public boolean hasNext() {

return cursor != size;

}

@SuppressWarnings("unchecked")

public E next() {

checkForComodification();

int i = cursor;

if (i >= size)

throw new NoSuchElementException();

Object[] elementData = ArrayList.this.elementData;

if (i >= elementData.length)

throw new ConcurrentModificationException();

cursor = i + 1;

return (E) elementData[lastRet = i];

}

public void remove() {

if (lastRet < 0)

throw new IllegalStateException();

checkForComodification();

try {

ArrayList.this.remove(lastRet);

cursor = lastRet;

lastRet = -1;

expectedModCount = modCount;

} catch (IndexOutOfBoundsException ex) {

throw new ConcurrentModificationException();

}

}

final void checkForComodification() {

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

}

}

Itr是ArrayList的一个内部类有三个重要的方法:

I hasNext()判断当前元素索引是否最后一个

II next()获取当前cursor指向的外层ArrayList数组索引位置

III remove()调用外层ArrayList中的remove方法移除lastRet位置的元素

为什么Iterator能够安全的移除元素呢？首先remove基本和next()配合使用，也就是说lastRet是实时计算出来的，这也就避免了下表越界。

Arrays.asList()移除元素

先看一段代码:

public static void main(String[] args) {

String str = "1,2,3,4,5";

String[] arr = str.split(",");

List<String> list = Arrays.asList(arr);

System.out.println(JSON.toJSONString(list));

list.remove("1");

System.out.println(JSON.toJSONString(list));

}

期望打印结果：["2","3","4","5"]

运行程序:

程序报了异常，为什么？不多说，这种情况直接看源码，看Arrays.asList实现：

public static <T> List<T> asList(T... a) {

return new ArrayList<>(a);

}

直接新建了一个ArrayList并返回，貌似也没有问题，继续点进去此处ArrayList实现:

/**

* @serial include

*/

private static class ArrayList<E> extends AbstractList<E>

implements RandomAccess, java.io.Serializable

{

private static final long serialVersionUID = -2764017481108945198L;

private final E[] a;

ArrayList(E[] array) {

a = Objects.requireNonNull(array);

}

@Override

public int size() {

return a.length;

}

@Override

public E get(int index) {

return a[index];

}

@Override

public E set(int index, E element) {

E oldValue = a[index];

a[index] = element;

return oldValue;

}

@Override

public int indexOf(Object o) {

E[] a = this.a;

if (o == null) {

for (int i = 0; i < a.length; i++)

if (a[i] == null)

return i;

} else {

for (int i = 0; i < a.length; i++)

if (o.equals(a[i]))

return i;

}

return -1;

}

@Override

public boolean contains(Object o) {

return indexOf(o) != -1;

}

}

到这里应该看出了一些端倪，原来这是一个和我们开发常用的ArrayList同名的一个List实现，但是这个ArrayList是Arrays中的一个内部类，是对List接口的自定义实现，这里的实现没有看到remove方法，类声明中其继承了AbstractList，直接看AbstractList中remove的实现:

/**

* {@inheritDoc}

*

* <p>This implementation always throws an

* {@code UnsupportedOperationException}.

*

* @throws UnsupportedOperationException {@inheritDoc}

* @throws IndexOutOfBoundsException {@inheritDoc}

*/

public E remove(int index) {

throw new UnsupportedOperationException();

}

我们看到，AbstractList中的remove是个模板方法，如果想在子类对象中使用，那就必须在子类中实现，否则抛异常，到这里我们就明白为什么上边的代码运行抛异常了。

那如果把remove改成迭代器中的remove调用，会怎么样呢？把上边的代码稍作修改如下：

public static void main(String[] args) {

String str = "1,2,3,4,5";

String[] arr = str.split(",");

List<String> list = Arrays.asList(arr);

System.out.println(JSON.toJSONString(list));

Iterator<String> iterator = list.iterator();

while (iterator.hasNext()) {

String temp = iterator.next();

if(temp.equals("1")) {

iterator.remove();

}

}

System.out.println(JSON.toJSONString(list));

}

运行程序：

程序依旧报了异常，我们继续看源码实现，从上个步骤Arrays的内部类ArrayList源码中我们也没有看到iterator的实现，也就是说也会使用AbstractList

中的实现方式:

public Iterator<E> iterator() {

return new Itr();

}

继续看Itr实现:

private class Itr implements Iterator<E> {

/**

* Index of element to be returned by subsequent call to next.

*/

int cursor = 0;

/**

* Index of element returned by most recent call to next or

* previous. Reset to -1 if this element is deleted by a call

* to remove.

*/

int lastRet = -1;

/**

* The modCount value that the iterator believes that the backing

* List should have. If this expectation is violated, the iterator

* has detected concurrent modification.

*/

int expectedModCount = modCount;

public boolean hasNext() {

return cursor != size();

}

public E next() {

checkForComodification();

try {

int i = cursor;

E next = get(i);

lastRet = i;

cursor = i + 1;

return next;

} catch (IndexOutOfBoundsException e) {

checkForComodification();

throw new NoSuchElementException();

}

}

public void remove() {

if (lastRet < 0)

throw new IllegalStateException();

checkForComodification();

try {

AbstractList.this.remove(lastRet);

if (lastRet < cursor)

cursor--;

lastRet = -1;

expectedModCount = modCount;

} catch (IndexOutOfBoundsException e) {

throw new ConcurrentModificationException();

}

}

final void checkForComodification() {

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

}

}

我们看到Itr是AbstractList中的内部类，重点看一下remove方法，里边最终调用这段逻辑:

AbstractList.this.remove(lastRet);

其实是调用AbstractList自己实现的remove方法，回过头来看一下:

public E remove(int index) {

throw new UnsupportedOperationException();

}

最终调用了和上一步中同样的逻辑，所以出现了和之前同样的异常。对于这种由数组转成List的数据如果想使用remove移除元素最好转换成标准的ArrayList实现或者自己写逻辑实现。

subList子列表问题

同样，先看一段代码:

public static void main(String[] args) {

int size = 5;

List<Integer> list = new ArrayList<>(5);

for(int i = 0;i < size; i++) {

list.add(i + 1);

}

List<Integer> subList = list.subList(1,list.size());

System.out.println("before父list:" + JSON.toJSONString(list));

System.out.println("before子list:" + JSON.toJSONString(subList));

subList.add(10);

subList.remove(Integer.valueOf(3));

System.out.println("after父list:" + JSON.toJSONString(list));

System.out.println("after子list:" + JSON.toJSONString(subList));

}

这段代码的含义是我先从之前的List构建出一个子list然后对子list进行更新操作，看看对原List有没有影响，正常情况下，我们业务逻辑中是期望子list操作不影响原list的，运行程序:

运行结果表明我们对子list操作确实影响到了原来的list，为什么呢？翻开源码看实现:

public List<E> subList(int fromIndex, int toIndex) {

subListRangeCheck(fromIndex, toIndex, size);

return new SubList(this, 0, fromIndex, toIndex);

}

新建了一个SubList实例并返回，进到SubList中重点看add和remove方法:

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;

}

public void add(int index, E e) {

rangeCheckForAdd(index);

checkForComodification();

parent.add(parentOffset + index, e);

this.modCount = parent.modCount;

this.size++;

}

public E remove(int index) {

rangeCheck(index);

checkForComodification();

E result = parent.remove(parentOffset + index);

this.modCount = parent.modCount;

this.size--;

return result;

}

}

从SubList源码中可以看出，创建SubList时将外层ArrayList对象传了进来，也就是说调用了subList得到和子列表其实是和ArrayList实例指向相同的数据，当然add和remove操作也是基于相同的数据，这也就导致了对于子列表的更新操作直接影响原列表。

还有一点值得注意，就是ArrayList调用subList方法的时候，其实是典型的浅复制，换了个壳，包的数据没有变。

既然知道了原理，对于从原列表分割出字列表，并且需要基于字列表操作但是不能影响原列表的操作，我们也有相应的实现方案：

1)重写subList方法，将浅复制改成深复制

2）逻辑层面不调用subList方法，自己新建对象和列表，将需要操作的数据填充到新对象并添加到新列表

总结

这一篇主要介绍了我们工作中最常用的List使用过程中遇到的一些坑以及其解决方案，希望给大家在日常开发中带来帮助！