ArrayList/Vector源码分析

ArrayList

ArrayList 实现于 List、RandomAccess 接口。可以插入空数据,也支持随机访问。
类图:

ArrayList相当于动态数据,其中最重要的两个属性分别是: elementData 数组,以及 size 大小。

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;
    transient Object[] elementData; // non-private to simplify nested class access
    /**
     * The size of the ArrayList (the number of elements it contains).
     */
    private int size;

add(e)

通过add(e)方法向数组尾部添加数据

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

这个方法做了下面事情:

  1. 首先进行扩容校验
  2. 将插入的值放到尾部,并将 size + 1

add(index,e)

通过add(index,e) 在指定位置添加的话

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

这个方法也是首先扩容校验。
接着对数据进行复制,目的是把 index 位置空出来放本次插入的数据,并将后面的数据向后移动一个位置。

扩容

扩容最终调用的代码

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1); //newCapacity计算逻辑
        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);
    }

也是一个数组复制的过程。
由此可见 ArrayList 的主要消耗是数组扩容以及在指定位置添加数据。
在日常使用时最好是指定大小,尽量减少扩容。更要减少在指定位置插入数据的操作。

序列化

由于 ArrayList 是基于动态数组实现的,所以并不是所有的空间都被使用。因此使用了 transient 修饰,可以防止被自动序列化。

    transient Object[] elementData; // non-private to simplify nested class access

ArrayList 自定义了序列化与反序列化:

 /**
     * Save the state of the <tt>ArrayList</tt> instance to a stream (that
     * is, serialize it).
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

    /**
     * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
     * deserialize it).
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in capacity
        s.readInt(); // ignored

        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

jvm序列化机制:
当对象中自定义了 writeObject 和 readObject 方法时,JVM 会调用这两个自定义方法来实现序列化与反序列化。

从实现可以看出 ArrayList 只序列化了被使用的数据。

查询

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

        return elementData(index);
    }
    E elementData(int index) {
        return (E) elementData[index];
    }

直接获取数组下标的对应元素,效率很高!

Vector

Vector 也是实现于 List 接口,底层数据结构和 ArrayList 类似,也是一个动态数组存放数据。

不过是在 add() 方法的时候使用 synchronized 进行同步写数据,但是开销较大,所以 Vector 是一个同步容器并不是一个并发容器。因此Vector并不常用!

add(e)

    /**
     * Appends the specified element to the end of this Vector.
     */
    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

add(index,e)

    public void add(int index, E element) {
        insertElementAt(element, index);
    }
    /**
     * Inserts the specified object as a component in this vector at the
     * specified {@code index}.
     */
    public synchronized void insertElementAt(E obj, int index) {
        modCount++;
        if (index > elementCount) {
            throw new ArrayIndexOutOfBoundsException(index
                                                     + " > " + elementCount);
        }
        ensureCapacityHelper(elementCount + 1);
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
        elementData[index] = obj;
        elementCount++;
    }
# java 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×