Java集合源码分析-ArrayList

作者: 宛丘之上兮 | 来源:发表于2018-11-12 17:18 被阅读0次

ArrayList类图

先看下ArrayList类图，比较直观。

ArrayList类图

ArrayList构造函数

先看ArrayList的成员变量：

    private static final long serialVersionUID = 8683452581122892189L;
    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = new Object[0];
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];
    transient Object[] elementData;
    private int size;
    private static final int MAX_ARRAY_SIZE = 2147483639;

初始容量DEFAULT_CAPACITY是10，当容量不足以容纳全部元素时，会自动扩张容量，新的容量 = 1.5*初始容量，对大容量MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8即2³¹-1-8=2147483639，为啥最大容量要定义这个数字呢？可以看下这个知乎上的解释，意思是说是否减8没那么重要(只是为了避免一些机器内存溢出)。

ArrayList一共有三个构造器，无参构造器a，参数为int型有参构造器b，参数为Collection型的有参构造器c。

    public ArrayList() {//a构造器
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    public ArrayList(int var1) {//b构造器
        if (var1 > 0) {
            this.elementData = new Object[var1];
        } else {
            if (var1 != 0) {
                throw new IllegalArgumentException("Illegal Capacity: " + var1);
            }
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

    public ArrayList(Collection<? extends E> var1) {//c构造器
        this.elementData = var1.toArray();
        if ((this.size = this.elementData.length) != 0) {
            if (this.elementData.getClass() != Object[].class) {
                this.elementData = Arrays.copyOf(this.elementData, this.size, Object[].class);
            }
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

通过上面的源码可以看出，a构造器直接将DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值给elementData；b构造器和c构造器很相似，如果参数int为0或者参数Collection长度为0，会将EMPTY_ELEMENTDATA赋值给elementData。DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA都是长度为0的数组，我感觉其实用一个数组变量就应该够用了，为啥还要分开成两个数组呢？

ArrayList核心操作

ArrayList核心操作包括：

trimToSize()(遍历操作也放在这部分讲解)
rangeCheck(var1:int)
get(pos:int):E
set(pos:int, val:E)
add(val:E):boolean
add(pos:int, val:E)
remove(val:int)
remove(val:Object):boolean
size():int
isEmpty(pos:int):boolean
indexOf(val:Object):int

size()

    public int size() {
        return this.size;
    }

返回的是元素的个数size，而不是elementData数组的长度。因为ArrayList容量增长后的容量是原来的1.5倍，所以elementData数组的长度一般都会大于size，如果手动调用或者系统调用了方法trimToSize，那么elementData数组会通过数组的拷贝方式被赋值为一个容量更小且容量等于size的数组并保存原有的数据(具体介绍在方法trimToSize分析中)，这时候elementData数组的长度才会等于size。

isEmpty(pos:int):boolean

    public boolean isEmpty() {
        return this.size == 0;
    }

源码不解释......

indexOf(val:Object):int

    public int indexOf(Object var1) {
        int var2;
        if (var1 == null) {
            for(var2 = 0; var2 < this.size; ++var2) {
                if (this.elementData[var2] == null) {
                    return var2;
                }
            }
        } else {
            for(var2 = 0; var2 < this.size; ++var2) {
                if (var1.equals(this.elementData[var2])) {
                    return var2;
                }
            }
        }
        return -1;
    }

源码非常清晰简单，上面代码的第11行(简书文章代码怎么显示代码的行数呀？)是对元素的内容进行的比较而不是引用。
这里顺便提一下contains(Object var1):boolean这个函数：

    public boolean contains(Object var1) {
        return this.indexOf(var1) >= 0;
    }

trimToSize()

源码中只提供了这个方法，但是没有被调用，估计是内存紧张的时候被系统调用的。源码：

    public void trimToSize() {
        ++this.modCount;
        if (this.size < this.elementData.length) {
            this.elementData = this.size == 0 ? EMPTY_ELEMENTDATA : Arrays.copyOf(this.elementData, this.size);
        }
    }

代码的第二行为啥要对modCount自加呢？顾名思义，modCount就是值更改的次数，增加、删除、修改ArrayList结构的操作都算是更改，所有都要对modCount这个变量自增1。ArrayList的遍历是不安全的，在使用Iterator遍历(下标遍历不存在这个问题)开始的时候用变量expectedModCount保存modCount原来的值，如果遍历时改变了集合的结构(增删等操作，这时modCount会和预期的值expectedModCount不一样)而抛出ConcurrentModificationException异常，具体流程如下(ArrayList的迭代器Itr的源码)：

    private class Itr implements Iterator<E> {
        int cursor;
        int lastRet = -1;
        int expectedModCount;
        Itr() {
            this.expectedModCount = ArrayList.this.modCount;
        }
    //......后面的操作省略
    //首先看到Itr保存了一个expectedModCount变量
    public E next() {
        this.checkForComodification();
    //......后面的操作省略
    }
    final void checkForComodification() {
        if (ArrayList.this.modCount != this.expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }
}

可以看到，在方法checkForComodification中可能会抛出异常。

顺便提一下ArrayList的三种遍历方式：

    public void arrayListTraversal(List<Integer> lists){
        /* 第一种遍历方式 ===-随机访问遍历*/
        System.out.print("for循环的遍历方式：");
        for (int i = 0; i < lists.size(); i++) {
            System.out.print(lists.get(i));
        }
        System.out.println();
        
        /* 第二种遍历方式 =-=-强制for循环遍历，这种方式和第三种方式关系有点暧昧*/
        System.out.print("foreach的遍历方式：");
        for (Integer list : lists) {
            System.out.print(list);
        }
        System.out.println();
        
        /* 第三种遍历方式-=-=迭代器遍历*/
        System.out.print("Iterator的遍历方式：");
        for (Iterator<Integer> list = lists.iterator(); list.hasNext();) {
            System.out.print(list.next());
        }
    }

其实通过反编译可以看到，第二种便利方式(foreach)底层是使用了Iterator迭代器进行的遍历，所以在遍历的时候进行增删等操作也会和第三种遍历一样抛出ConcurrentModificationException异常，而第一种遍历方式不存在这个问题而且遍历效率最高，举个例子：

ArrayList<Integer> list = new ArrayList();
list.add(1);
list.add(2);
list.add(3);
for (int i = 0; i < list.size; i++) {
    int av = list.get(i);
    if (av == 2) {
        list.add(666);
    }
    System.out.println("av: " + av);
}
System.out.println("list: " + list);

上面代码的执行结果是：

ArrayList<Integer> list = new ArrayList();
list.add(1);
list.add(2);
list.add(3);
for (int av : list) {
    if (av == 2) {
        list.add(666);
    }
    System.out.println("av: " + av);
}
System.out.println("list: " + list);

上面代码的执行结果是：

讲完了遍历，回到开始，继续分析trimToSize方法。如果elementData数组包含空闲位置，第三行代码满足，如果容量不为0，那么会调用Arrays.copyOf(this.elementData, this.size)，这行代码干嘛呢？看下Arrays.java的源码：

    public static <T> T[] copyOf(T[] var0, int var1) {
        return (Object[])copyOf(var0, var1, var0.getClass());
    }

    public static <T, U> T[] copyOf(U[] var0, int var1, Class<? extends T[]> var2) {
        Object[] var3 = var2 == Object[].class ? (Object[])(new Object[var1]) : (Object[])((Object[])Array.newInstance(var2.getComponentType(), var1));
        System.arraycopy(var0, 0, var3, 0, Math.min(var0.length, var1));
        return var3;
    }

可以看到最终会调用System.arraycopy这个方法，返回一个新的数组赋值给elementData，而这个新的数组是将原来数组的闲置位置删除后的。

rangeCheck(var1:int)

    private void rangeCheck(int var1) {
        if (var1 >= this.size) {
            throw new IndexOutOfBoundsException(this.outOfBoundsMsg(var1));
        }
    }

get(pos:int):E

    public E get(int var1) {
        this.rangeCheck(var1);
        return this.elementData(var1);
    }

set(pos:int, val:E)

    public E set(int var1, E var2) {
        this.rangeCheck(var1);
        Object var3 = this.elementData(var1);
        this.elementData[var1] = var2;
        return var3;
    }

add(val:E):boolean

前面几个方法很简单，只贴了源码都没有解释一句，因为不需要解释，而add这个方法就有点复杂了(其实代码只有很简单的五行)：

    public boolean add(E var1) {
        this.ensureCapacityInternal(this.size + 1);
        this.elementData[this.size++] = var1;
        return true;
    }

首先是调用了ensureCapacityInternal(var1:int)这个方法来保证容量并且判断是否需要扩充容量。

    private void ensureCapacityInternal(int var1) {
        if (this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            var1 = Math.max(10, var1);
        }
        this.ensureExplicitCapacity(var1);
    }

    private void ensureExplicitCapacity(int var1) {
        ++this.modCount;
        if (var1 - this.elementData.length > 0) {
            this.grow(var1);
        }
    }

因为add操作更改了ArrayList的结构，所以第二行对modCount加1，第三行表示如果add后新的容量比原来容量大，就调用grow(var:int)进行扩容，看下grow(var:int)的源码：

    private void grow(int var1) {
        int var2 = this.elementData.length;
        int var3 = var2 + (var2 >> 1);
        if (var3 - var1 < 0) {
            var3 = var1;
        }
        if (var3 - 2147483639 > 0) {
            var3 = hugeCapacity(var1);
        }
        this.elementData = Arrays.copyOf(this.elementData, var3);
    }

第三行很关键，表示新的容量是原来的1.5倍，第八行的hugeCapacity是一种容错机制，如果超出了最大容量，那么容量就是最大容量+8：

    private static int hugeCapacity(int var0) {
        if (var0 < 0) {
            throw new OutOfMemoryError();
        } else {
            return var0 > 2147483639 ? 2147483647 : 2147483639;
        }
    }

add(pos:int, val:E)

    public void add(int var1, E var2) {
        this.rangeCheckForAdd(var1);
        this.ensureCapacityInternal(this.size + 1);
        System.arraycopy(this.elementData, var1, this.elementData, var1 + 1, this.size - var1);
        this.elementData[var1] = var2;
        ++this.size;
    }

源码也很简单，扩容操作与add(val:E):boolean一模一样，特别的地方在第四行进行了数组的拷贝操作。

remove(val:int)

    public E remove(int var1) {
        this.rangeCheck(var1);
        ++this.modCount;
        Object var2 = this.elementData(var1);
        int var3 = this.size - var1 - 1;
        if (var3 > 0) {
            System.arraycopy(this.elementData, var1 + 1, this.elementData, var1, var3);
        }
        this.elementData[--this.size] = null;
        return var2;
    }

关键点还是第七行的System.arraycopy数组拷贝操作。

remove(val:Object):boolean

    public boolean remove(Object var1) {
        int var2;
        if (var1 == null) {
            for(var2 = 0; var2 < this.size; ++var2) {
                if (this.elementData[var2] == null) {
                    this.fastRemove(var2);
                    return true;
                }
            }
        } else {
            for(var2 = 0; var2 < this.size; ++var2) {
                if (var1.equals(this.elementData[var2])) {
                    this.fastRemove(var2);
                    return true;
                }
            }
        }
        return false;
    }

    private void fastRemove(int var1) {
        ++this.modCount;
        int var2 = this.size - var1 - 1;
        if (var2 > 0) {
            System.arraycopy(this.elementData, var1 + 1, this.elementData, var1, var2);
        }
        this.elementData[--this.size] = null;
    }

Java集合源码分析-ArrayList

ArrayList类图

ArrayList构造函数

ArrayList核心操作

size()

isEmpty(pos:int):boolean

indexOf(val:Object):int

trimToSize()

rangeCheck(var1:int)

get(pos:int):E

set(pos:int, val:E)

add(val:E):boolean

add(pos:int, val:E)

remove(val:int)

remove(val:Object):boolean

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

程序员

架构算法设计模式和编程理论