Java源码解读——ArrayList（二）

看了下ArrayList的源码，记录下自己的解读心得与体会。

 

ArrayList的自动变长机制

都知道ArrayList不像数组那样是定长的，然而ArrayList也使用了数组来保存数据，所以么，自然很关心是怎么实现变长的。

 

ArrayList通过ensureCapacityInternal(int minCapacity)方法实现自身容量的增加，在add()和addAll()方法里面都调用了改方法。

    private void ensureCapacityInternal(int minCapacity) {
        modCount++;
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

 方法名的英文大致意思是“确保内部容量”，这里要说明，size表示的是现有的元素个数，并非ArrayList的容量，容量应该是数组elementData的长度。参数minCapacity是需要检查的最小容量，即方法的功能就是确保elementData的长度不小于minCapacity，如果不够，则调用grow增加容量。容量的增长也算结构性变动，所以modCount需要加1。

 

grow代码：

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) 
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

 先对容量扩大1.5倍，这里oldCapacity >> 1是二进制操作右移，相当于除以2，如果不知道这个面壁去吧（刚看到时候也没反应过来这个是什么操作，毕竟平时java中很少用到左移、右移这种运算，没事谢个测试用例测试下计算效果就知道是干什么的了）。接再来把新的临时容量（还没正式改变容量，应该叫预期容量）和实际需要的最小容量比较，如果还不满足，则把临时容量改成需要的最小容量值。在判断容量是否超过MAX_ARRAY_SIZE的值，MAX_ARRAY_SIZE值为Integer.MAX_VALUE - 8，比int的最大值小8，不知道为什设计，可能方便判断吧。如果已经超过，调用hugeCapacity方法检查容量的int值是不是已经溢出。一般很少用到int最大值的情况，那么多数据也不会用ArrayList来做容器了，估计这辈子没机会见到hugeCapacity运行一次了。最后确定了新的容量，就使用Arrays.copyOf方法来生成新的数组，copyOf也已经完成了将就的数据拷贝到新数组的工作。

当然有增就有减，trimToSize()就是用来将elementData的长度变成size。

    public void trimToSize() {
        modCount++;
        int oldCapacity = elementData.length;
        if (size < oldCapacity) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }

 这样可以解决平凡新增、删除元素后elementData过大的问题。

 

从上面的操作来看，ArrayList的容量增长的开始还是有的，就算那些数字的计算忽略不计，Arrays.copyOf的操作的消耗也不会小。所以在初始化ArrayList的时候尽量预算下大致的容量需求，降低平凡调整容量的开销。

 

序列化

ArrayList实现了Serializable接口，所以ArrayList可以进行序列化。但是elementData的定义

private transient Object[] elementData;

 transient修饰符让elementData无法自动序列化，这样的原因是，数组内存储的的元素其实只是一个引用，单单序列化一个引用没有任何意义，反序列化后这些引用都无法在指向原来的对象。ArrayList使用writeObject()实现手工序列化数组内的元素。

    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        int expectedModCount = modCount;
        s.defaultWriteObject();

        s.writeInt(elementData.length);

        for (int i=0; i<size; i++)
            s.writeObject(elementData[i]);

        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

 

迭代器实现

一般ArrayList需要遍历时，可以调用他的iterator()方法返回一个迭代器，然后用迭代器进行遍历。

    public Iterator<E> iterator() {
        return new Itr();
    }

 iterator()方法放回了一个Itr类实例，这个Itr类是ArrayList的一个内部类，实现了Iterator接口。

        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

上面是Itr类的三个成员变量。 cursor类似一个游标，指向迭代器下一个值的位置。lastRet是迭代器最后一次取出的元素的位置。expectedModCount的值为Itr初始化时候ArrayList的modCount的值，前面将过modCount用于记录ArrayList内发生结构性改变的次数，而Itr每次进行next或remove的时候都会去检查expectedModCount值是否还和现在的modCount值一直，从而保证了迭代器和ArrayList内数据的一致性。实现代码如下：

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

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

 Itr作为ArrayList的内部类，可以访问所有ArrayList的成员。理解了这一点，itr类的实现就容易理解了。

 

还有一个listIterator的迭代器，实现方式类似。

 

 

java的集合在平时开发中很常用，能够了解它们的内部实现，对开发带来很大的便利，也减少了不必要的BUG。

 

评论

4 楼 15201493793 2016-05-11  

大神arraylist完了，linkedList呢，set,map 啥的呢？继续啊

3 楼 unbachone 2015-10-24  

ensureCapacityInternal不是“确保内部容量”的意思，是为了区别于ensureCapacity方法，jdk1.6时是用ensureCapacity方法来确保容量的，1.7有了一些改进，而ensureCapacity变成了只供外部调用，而ArrayList类内部确保容量就使用了ensureCapacityInternal方法，所以在方法后面加了Internal。

2 楼 jssyjam 2015-09-22  

/**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
     //这边减去8的意思是一些vms会在数组头加一些信息，如果不预留空间可能会发生内存溢出的错误

1 楼 jiangyeqt 2014-12-29  

transient修饰符让elementData无法自动序列化，这样的原因是，数组内存储的的元素其实只是一个引用，单单序列化一个引用没有任何意义，反序列化后这些引用都无法在指向原来的对象。ArrayList使用writeObject()实现手工序列化数组内的元素。
-----------------------------------------------------------------
这一段不敢苟同，亲自敲一敲就知道了。
集合中存储javaBean，序列化的是什么，是引用吗？其实是有状态的javaBean对象吧。反序列话回来会生成一个状态完全相同的javaBean实例。不知道我说的是否有纰漏，请指教。