Java教程

ArrayList源码分析

本文主要是介绍ArrayList源码分析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1、ArrayList继承和实现结构
ArrayList继承抽象的list类AbstractList,实现了List接口,Serializable接口。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

2、ArrayList的底层实现结构是什么?默认的初始化容量是多少?
答:ArrayList底层采用数组进行实现,并且在不指定初始化容量的时候,默认的初始化容量为:10。

private static final int DEFAULT_CAPACITY = 10;  //默认的初始化容量设置为10
transient Object[] elementData;   //底层采用对象数组进行元素的存储

3、底层的构造器
(1)空参构造器,底层的数组变量elementData 默认初始化为一个空数组,只有当我们第一次向list中添加数据的时候,才会将elementData 重新赋值为一个长度为10的数组,这个过程还是比较复杂的,具体可以看下面的讲解(ArrayList第一次添加元素时所经历的一系列操作)。

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  
        //这里将elementData 数组初始化为一个空数组,并不是直接就初始化为一个长度为10 的数组,这个过程是在第一次添加元素的时候才进行的
    }

(2)带参构造器,将参数传入的一个集合类型变量c转换成数组,添加到list底层的数组中。

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

4、ArrayList第一次添加元素时所经历的一系列操作。
(1)在我们调用无参构造器创建list对象的时候,底层会将elementData 数组初始化为一个空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA(private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};);
(2)当我们第一次调用add()方法往list中添加元素的时候(list.add("tmj");),进入到add()方法体;

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 进行数组的容量保证,如果第一次添加,此时的elementData还是空数组
        //就需要将elementData赋值为一个长度为默认10的数组对象,如果不是第一次添加,就需要进行数组容量判断,检查当前的elementData数组是否还有剩余的位置存放,
        //如果容量不够,需要进行扩容,再将扩容的数组赋值为elementData变量,就完成数组的扩容
        elementData[size++] = e;  //容量保证完成后,就将元素放到记录的index索引处,这里就是size对应的索引。
        return true;
    }

(3)ensureCapacityInternal()方法调用;

private void ensureCapacityInternal(int minCapacity) {  //当第一次调用add方法时,minCapacity为1,就代表这个底层数组最小的容量为minCapacity,因为必须将元素放下
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  //第一次add时,会进入这个代码块
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);  //第一次进来的时候minCapacity=1,所以和默认的容量10相比,最终得到minCapacity选取两者较大这 = 10
        }

        ensureExplicitCapacity(minCapacity);  //这个方法用于对判断数组是否需要进行扩容
    }

(4)ensureExplicitCapacity()方法调用

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

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)  //如果我们需要的最小容量小于了当前数组的容量(第一次add时,当前数组容量为0),就调用grow()进行数组的扩容
            grow(minCapacity);
    }

(5)grow()方法调用

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;  //原先数组的容量
        int newCapacity = oldCapacity + (oldCapacity >> 1);  //进行扩容后数组的新容量,newCapacity = oldCapacity + oldCapacity /2;
        //这里就是关键点,可以看出,每次进行数组扩容的时候,都是将新的数组扩容为原先数组容量的1.5倍。这里的右移就代表除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);  //完成数组中元素的转移
    }

5、常用方法介绍
(1)toArray():将一个list对象转换成对应的数组对象
(2)get(int index):返回指定索引位置上的元素

public E get(int index) {
        rangeCheck(index);  //索引范围检查

        return elementData(index);
    }

(3)set(int index, E element):将某个索引位置上的元素设置为新的元素,并返回原先元素的值。

public E set(int index, E element) {
        rangeCheck(index);  //索引检查

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

(4)add(E e):添加一个元素到list中
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

(5)add(int index, E element):在指定的索引位置上添加元素,这个操作会导致该index后续的其他元素依次后移,腾出一个空间给新的元素。

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

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

(6)remove(int index):删除指定索引位置上的元素,这个操作会导致index后面的元素依次往前面移动,并且size–,list中元素个数减1。

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; // clear to let GC do its work

        return oldValue;
    }

(7)remove(Object o):从list中移除查找到的第一个特定的对象o,如果有多个相同的对象,只会移除第一个,返回是否移除对象,如果list中没有该对象,返回false,否则返回true。如果需要移除多个,可以自己写一个循环进行迭代删除。

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

(8)clear():清空这个list中的元素,实际上就是将底层的数组每个位置上的值都设置为null并将size设置为0,这样可以帮助GC进行垃圾回收。

public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

(9)removeRange(int fromIndex, int toIndex):移除list中某个index1到另外一个index2之间的所有元素。

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

        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }

                    
这篇关于ArrayList源码分析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!