jdk6标准类库源码解读 之 数据结构 （一） ArrayList<E>

最近受到一次面试的启发，开始看jdk6的标准源码，在这里记录下自己看的过程中的体会，和大家分享。

从最常用的数据结构开始 

     ArrayList<E>

• 此对象的存储采用的是标准的Object数组(elementData)进行存储，同时使用一个整形记录数组(elementData)中实际数据的长度。

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer.
     */
    private transient Object[] elementData;

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

• 对象默认初始化存储容量为10

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
	this(10);
    }

•  对象中的存储数组elementData会随着需要存储数据的增加而扩大。在调用对象的add方法时，arraylist会首先判断容量是否足够，不够时，采用newCapacity = (oldCapacity * 3)/2 + 1的策略，进行扩充。此策略只计算一次，如果扔不足够，则直接按照新的容量进行扩展。

    public boolean add(E e) {
        ensureCapacity(size + 1); // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    public void ensureCapacity(int minCapacity) {
        modCount++;
        int oldCapacity = elementData.length;
        if (minCapacity > oldCapacity) {
            Object oldData[] = elementData;
            int newCapacity = (oldCapacity * 3) / 2 + 1;
            if (newCapacity < minCapacity)
                newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }

• 对象中的存储数组elementData不会随着需要存储数据的减少而缩小。对象只会改变elementData中的数据存储位置，进行迁移，并依赖gc判断移除对象的回收。

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

        modCount++;
        E oldValue = (E) 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;
    }

 

• indexof采用的是标准的遍历算法，时间复杂度很高，效率很低。并且都是从前开始匹配。contains方法同理。

    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i] == null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

 

上面可以通过源码，更准确的看到标准类库中对象的特点，后面会继续加入其他的数据类型、和标准类库中的其他类。