关于ArrayList (一)
关于ArrayList (一)
Tunie2014 发表于5年前
关于ArrayList (一)
  • 发表于 5年前
  • 阅读 310
  • 收藏 1
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

之前对ArrayList的分析太简单了,所以,我决定重新看一遍源码,分析下其内部是如何实现集合具备的功能。

ArrayList

1.定义:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
首先,ArrayList就是继续的AbstractList抽象类,这是种适配器模式的应用。接着它又实现 了List接口,按理说AbstractList也实现了List接口,ArrayList应该没有必要再去实现List接口了,究竟是什么原因呢?我也不清楚,存疑。


其次,ArrayList还实现了RandomAccess,Cloneable,Serializable接口,这些接口有什么用呢?去看下API就知道了。

2.重要方法实现

集合操作无外乎增删改查,先看看“增”的实现。

增:

public boolean add(E e) 
    public void add(int index, E element)
    public boolean addAll(int index, Collection<? extends E> c) 
    public boolean addAll(Collection<? extends E> c)
Arraylist提供了四个“增”,它的内部是依靠数组来实现了,不过,重点在于它的长度可变这个特性。我们知道,数组一旦申明new出来之后,长度是不可变的,所以,看看它是如何实现长度可变的是很有意思的。我们很快就会发现增方法中都调用了这个方法,源码如下:


ensureCapacityInternal(size + 1);  // Increments modCount!!

如有必要,增加此ArrayList实例的容量,以确保它至少能够容纳最小容量参数所指定的元素数。

private void ensureCapacityInternal(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
很好,重点在grow方法的实现,它才是最终实现长度可变这功能的元凶。


private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;//当前数组长度
        int newCapacity = oldCapacity + (oldCapacity >> 1);//当前数组长度的3/2
        if (newCapacity - minCapacity < 0)//若最小容量大于新容量
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

minCapacity通常是最接近实际的集合元素的大小的,所以,取这个值是最划得来的。

很显然,当ArrayList每增加一次元素,元素可以是一个或多个,它都会对自身的容量长度进行最优处理,这个就是它的长度可变的精髓。

删:   

public void clear()
    public E remove(int index)
    public boolean remove(Object o)
    public boolean removeAll(Collection<?> c)
    protected void removeRange(int fromIndex, int toIndex)
    private boolean batchRemove(Collection<?> c, boolean complement) 
    private void fastRemove(int index)
ArrayList对外 提供了四个有关“删”的接口,内部还有三个“删”的功能实现。我们一个一个来,先看clear的实现,源码如下:


public void clear() {
        modCount++;
        // Let gc do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

有必要去了解下modCount变量的作用:已从结构上修改 此列表的次数。从结构上修改是指更改列表的大小,或者打乱列表,从而使正在进行的迭代产生错误的结果。好了,文档说的很清楚。

clear方法的实现非常简单明了,利用了数组的特性,通过设置数组各元素的值为null,然后交给gc(垃圾回收)处理。接下来分析下remove(int index)方法。

public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // Let gc do its work

        return oldValue;
    }
首先,看下rangeCheck方法内部如何实现的,从字面上可以理解为范围检测,源码如下:

private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
就一句代码,意思一目了然。

其次,我发现这里有一个elementData方法,和变量elementData一样,呵呵,

E elementData(int index) {
        return (E) elementData[index];
    }
进行了一次类型强制转换。

最后,我严重的发现自己对arraycopy缺少认识,去补充下基础知识先。

public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);
是个native方法,功能是从指定源数组中复制一个数组,复制从指定的位置开始,到目标数组的指定位置结束。从src引用的源数组到dest引用的目标数组,数组组件的一个子序列被复制下来。被复制的组件的编号等于length参数。源数组中位置在srcPos到srcPos+length-1之间的组件被分别复制到目标数组中的destPos到destPos+length-1位置。原来是这样子呀。看下remove(Object o)方法:

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

这代码看起来没什么挑战,去看下fastRemove方法如何实现的,这个是重点。

private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // Let gc do its work
    }
跟remove(int index)实现基本一致。调用了arraycopy方法。轮到removeAll了,源码必不可少。


public boolean removeAll(Collection<?> c) {
        return batchRemove(c, false);
    }
重点在batchRemove方法是如何实现的,看看去
 private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

removeAll肯定是删除与集合c的交集部分,这样就不难理解try语句块中for循环实现的目的了。很显然,经过for循环后,elementData数组中的所有不在c集合中的元素都被安置在0至w段,剩下的步骤只要清空掉w至size-1之间的元素的可以了。然后,我们看下finally块是如何实现剩余步骤的。看第一个if语句,这种情况的出现只有在c.contains方法抛出异常的时候才会处理,直接看第二个if语句,很显然,w不可能会大于size的,正如前面我说的,这里只是进行了下善后的工作,清空w至size-1间的所有元素。接着看下removeRange方法:

protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        // Let gc do its work
        int newSize = size - (toIndex-fromIndex);
        while (size != newSize)
            elementData[--size] = null;
    }
方法的意思是删除指定范围间的元素,唉,这算法,我从来就没有这样想过,太厉害了!






共有 人打赏支持
粉丝 3
博文 95
码字总数 46373
×
Tunie2014
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: