×

ArrayList实现源码分析与Vector的区别

我的笔记 我的笔记 发表于2019-08-31 15:53:24 浏览2914 评论0

抢沙发发表评论


本文将以以下几个问题来探讨ArrayList的源码实现

  1. ArrayList成员属性、构造方法。

  2. ArrayList的大小是如何自动增加的?

  3. add/set方法。

  4. remove方法。

  5. Iterator和ListIterator接口。

  6. 子集操作。

  7. 如何复制某个ArrayList到另一个ArrayList中去?写出你的代码?

1、ArrayList成员属性、构造方法

private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] EMPTY_ELEMENTDATA = {};

    transient Object[] elementData;

    private int size;

从这段定义中可以看出,ArrayList维护了两个数组DEFAULT_CAPACITY和elementData。DEFAULT_CAPACITY是一个空数组,当创建一个空的ArrayList的时候就会使用DEFAULT_CAPACITY,这个时候elementData==DEFAULT_CAPACITY,当在容器中添加一个元素以后,则会使用elementData来存储数据。

这里值得讨论的是DEFAULT_CAPACITY常量,他代表的含义是一个默认数组大小,当我们创建的容器没用指定容量大小时,就会默认使用这个常量作为数组大小。因此当我们创建一个ArrayList实例的时候,最好考虑一下业务场景,如果我们将频繁的存储大量的元素,那么最好在创建的时候指定一个合理的size。所谓动态扩容,就是当数组中存储的元素达到容量上限以后,ArrayList会创建一个新的数组,新数组的大小为当前数组大小的1.5倍。随后将数组元素拷贝到新数组,如果这个动作频繁执行的话,会增大性能开销。

public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

    public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;
    }

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

这三个方法都是ArrayList的构造方法,从前两个方法中可以看出初始化ArrayList的时候是如何指定容器初始大小的,这里也无需多言了。那么我们再看看,当容量达到上限的时候,是如何动态扩充数组大小的呢。

2、ArrayList的大小是如何自动增加的?

public boolean add(E e) {
    // 每次添加元素之前先动态调整数组大小,避免溢出
    ensureCapacityInternal(size + 1);
    // 为什么ArrayList的元素都是顺序存放的?这就是原因,每次都会把最新添加的元素放到数组末尾。
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    // 如果当前容器为空,那么就先初始化数组,数组大小不能小于DEFAULT_CAPACITY
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // 容器会在什么时候扩容? 就是他了! 如果当前元素数量达到了容器的上限,那么就扩充数组
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // oldCapacity为当前容器大小
    int oldCapacity = elementData.length;
    // oldCapacity >> 1和oldCapacity / 2是等效的,因此newCapacity为原来的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 因为第一次容器有可能为空,elementData.length==0,newCapacity会小于minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 当然newCapacity也不能大于MAX_ARRAY_SIZE,因为数组能分配的最大空间就是Integer.MAX_VALUE
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 当确定好数组大小后,就可以进行数组拷贝,Arrays.copyOf的底层是一个native方法,后续有机会会讲到他的实现。
    elementData = Arrays.copyOf(elementData, newCapacity);
}

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

add/set方法

1.add方法:

public boolean add(E e) {
    // 检查扩容
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);
    //将index后面的元素后移一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);

    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

这里给出了四种add方法,add(E e)添加到数组末尾,add(int index, E element)添加到指定位置。添加元素的时候,首先都要检查扩容,而add(int index, E element)方法中多一步操作,就是将指定位置以后的所有元素向后移动一位,留出当前位置用来存放添加的元素。后面两种addAll方法原理和前两种一样,无非他是添加一个集合元素的区别。

2.set方法:

public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

set和add的区别就是,add是添加一个元素,而set是替换元素,size不变。

remove方法:

1.remove单个元素:

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 直接进行数组拷贝操作,把index后的所有元素向前移动一位。
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // 把元素设空,等待垃圾回收

    return oldValue;
}

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

// 之所以叫做快速删除,是因为他被设置为一个私有方法,只能在内部调用,删除元素的时候,省去了数组越界的判断。也不返回被删除的元素,直接进行数组拷贝操作。
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;
}

2.删除集合元素
removeAll和remove方法思想也是类似的,但是这里有个细节我认为作者处理的非常妙,有必要拿出来品味一下。那么妙在哪里呢?原来这里有两个方法removeAll和retainAll他们正好是互斥的两个操作,但是底层都调用了同一个方法来实现,请看!

// 删除包含集合C的元素
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

// 除了包含集合C的元素外,一律被删除。也就是说,最后只剩下c中的元素。
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

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++)
            // 我认为这里有两点值得我们学习
            // 第一,作者巧妙的提取了逻辑上的最大公约数,仅通过一行逻辑判断就实现了两个互斥的效果。
            // 第二,作者的所用操作都集中于elementData一个数组上,避免了资源的浪费。
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // 理论上r==size 只有当出现异常情况的时候,才会出现r!=size,一旦出现了异常,
        // 那么务必要将之前被修改过的数组再还原回来。
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // 被删除部分数组后,剩余的所有元素被移到了0-w之间的位置,w位置以后的元素都被置空回收。
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

Iterator和ListIterator接口

1.Itr
Itr实现的是Iterator接口,拥有对元素向后遍历的能力.

int cursor;       // 指向下一个返回的元素
int lastRet = -1; // 指向在遍历过程中,最后返回的那个元素。 如果没有为-1。

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;
    // 返回当前元素,并把lastRet指向当前这个元素
    return (E) elementData[lastRet = i];
}

// 此处有坑,调用此方法前,必须调用next方法,从lastRet可以看出,如果当前没有调用next,那么lastRet==-1
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();
    }
}

2.ListItr
ListItr不但继承了Itr类,也实现了ListIterator接口,因此他拥有双向遍历的能力。这里着重介绍一下向前遍历的原理。

public boolean hasPrevious() {
    return cursor != 0;
}

public int previousIndex() {
    // 通过cursor-1,将指针向前移位。
    return cursor - 1;
}

public E previous() {
    checkForComodification();
    int i = cursor - 1;
    if (i < 0)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i;
    return (E) elementData[lastRet = i];
}

子集操作

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

这里指的子集,就是指定list的起始位置和结束位置,获取这段范围内的集合元素。那么这有什么作用呢?当单独获取了这段子集以后,就可以独立的对待他,他的起始元素将从0开始。那么这是怎么实现的呢?原来他是通过维护一个SubList内部类,每次读取元素的时候,配合一个offset偏移量,精确的找到elementData数组中对应位置的元素了。由于代码量过多,我这里就象征性的展示其中的一个get方法。

public E get(int index) {
    rangeCheck(index);
    checkForComodification();
    // 子集中的位置+偏移量==实际数组中的位置
    return ArrayList.this.elementData(offset + index);
}

如何复制某个ArrayList到另一个ArrayList中去?写出你的代码?

1.clone

 public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

2.之前介绍过的构造方法。

public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

两者本质都是调用Arrays.copyOf,而Arrays.copyOf是调用System.arrayscopy

   public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }

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

总结:

以数组实现。节约空间,但数组有容量限制。超出限制时会增加50%容量,用System.arraycopy()复制到新的数组,因此最好能给出数组大小的与估值。默认第一次插入元素是创建大小为10的数组。
按数组下标访问元素-get(i)/set(i,e)的性能很高,这是数组的基本优势。直接在数组末尾加入元素-add(e)的性能也很高,但如果按下标插入,删除元素–add(i,e),remove(i),remove(e)则要用System.arraycopy()来移动受影响的元素,性能就变差了,这是基本劣势。

与Vector的区别

1、ArrayList是非线程安全,而Vector是线程安全的,在源码的表示上Vector加上了关键字synchronized。

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

// ArrayList的add方法
public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

2、 ArrayList和Vector都具有动态扩容的特性,唯一的区别是,ArrayList扩容后是原来的1.5倍。Vector中有一个capacityIncrement变量,每次扩容都在原来大小基础上增加capacityIncrement。如果capacityIncrement==0,那么就在原大小基础上再扩充一倍。
3、 Vector中有一个方法setSize(int newSize),而ArrayList并没有,我觉得这个方法有点鸡肋。setSize允许用户主动设置容器大小,如果newSize小于当前size,那么elementData数组中只会保留newSize个元素,多出来的会设为null。如果newSize大于当前size,那么就扩容到newSize大小,数组中多出来的部分设为null,以后添加元素的时候,之前多出来的部分就会以null的形式存在,直接试验一下吧。

Vector<Integer> v2 = new Vector<Integer>();
    v2.add(1);
    v2.setSize(3);
    v2.add(3);
    System.out.println(v2.size());

    setSize之前:
    [1]
    setSize之后:
    [1, null, null]
    当我再次添加一个元素后:
    [1, null, null, 3]
    所以我觉得这个方法并没有太大实用意义。而且会是用户困惑,出现一些不必要的错误。
原文链接:https://blog.csdn.net/qq_33850908/article/details/79481787

因为Vector是同步的,所以性能上肯定不如ArrayList,所以在不需要考虑多线程的环境下,建议使用ArrayList。

我的笔记博客版权我的笔记博客版权