Java容器源码学习--ArrayList源码分析

ArrayList实现了List接口，它的底层数据结构是数组，因此获取容器中任意元素值的时间复杂度为O(1)，新增或删除元素的时间复杂度为O(N)。每一个ArrayList实例都有一个capacity变量，capacity是ArrayList用于存储元素的容器大小，当有新元素添加到容器时，capacity会自动扩容，当新增元素时，容器会计算需要扩容的大小，减少了内存重新分配的次数。需要注意的时，ArrayList是非线程安全的容器，在多线程环境下容易出现线程安全问题。

源码

成员变量

private static final int DEFAULT_CAPACITY = 10; // 默认的容量是10

private static final Object[] EMPTY_ELEMENTDATA = {}; //初始化容量为0时的空数组

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //初始化没有指定容量

transient Object[] elementData; //存储元素的数组

private int size; //容器中元素的数量

构造方法

public ArrayList(int initialCapacity) {

       //如果初始化指定容量 > 0，直接创建一个数组

        if (initialCapacity > 0) {

            this.elementData = new Object[initialCapacity];

        } else if (initialCapacity == 0) {

            this.elementData = EMPTY_ELEMENTDATA;

        } else {

            throw new IllegalArgumentException("Illegal Capacity: "+

                                               initialCapacity);

        }

    }

    /**

     * Constructs an empty list with an initial capacity of ten.

     */

    public ArrayList() {

        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //默认的数组容量大小是10

    }

添加元素



public boolean add(E e) {

        modCount++;

        add(e, elementData, size);

        return true;

    }

private void add(E e, Object[] elementData, int s) {

        //容器元素数量等于数组的长度触发扩容条件

        if (s == elementData.length)

          //调用grow方法进行扩容

            elementData = grow();

        elementData[s] = e;

        size = s + 1;

    }

//扩容逻辑，先计算出需要扩容的大小，再把原数组元素拷贝到扩容后的数组

private Object[] grow(int minCapacity) {

        int oldCapacity = elementData.length;

        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

            int newCapacity = ArraysSupport.newLength(oldCapacity,

                    minCapacity - oldCapacity, /* minimum growth */

                    oldCapacity >> 1           /* preferred growth */);

            return elementData = Arrays.copyOf(elementData, newCapacity);

        } else {

            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];

        }

    }

    private Object[] grow() {

        return grow(size + 1);

    }

//计算扩容后的数组长度

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {

        // preconditions not checked because of inlining

        // assert oldLength >= 0

        // assert minGrowth > 0

        int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow

        if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {

            return prefLength;

        } else {

            // put code cold in a separate method

            return hugeLength(oldLength, minGrowth);

        }

    }

通过源码可知，添加元素前，先判断当前容器大小与数组长度，决定是否要扩容，否则直接添加到容器中。扩容需要计算出扩容后新数组的长度，新数组长度是原数组的1.5倍大小。

在指定位置添加元素

public void add(int index, E element) {

//先判断插入位置是否合法

        rangeCheckForAdd(index);

//记录容器被修改的次数

        modCount++;

        final int s;

        Object[] elementData;

//扩容条件

        if ((s = size) == (elementData = this.elementData).length)

            elementData = grow();

//将后面的元素后移，腾出位置

        System.arraycopy(elementData, index,

                         elementData, index + 1,

                         s - index);

        elementData[index] = element;

        size = s + 1;

    }

巴特西

Java容器源码学习--ArrayList源码分析

源码

成员变量

构造方法

添加元素

在指定位置添加元素

最新文章

热门文章