java ArrayList与Vector源码学习

Vector和ArrayList非常相似，两者都是用来表示可变数组，内部元素的存储都是通过数组来实现，可以随机的访问某个元素。

两者的主要区别是Vector的方法带有synchronized标志，各方法的访问是同步的，因此，Vector能够支持多线程，但是相应地效率比较低；ArrayList的方法没有synchronized标志，不是线程安全的。还有个比较小的差异是Vector在容量不够时，选择 size * 2扩容；ArrayList选择 size * 3/2 + 1扩容。

 

下面先来看下ArrayList的源码：

 

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

 RandomAccess： 这个是标记接口，没有需要实现的方法，声明ArrayList可以随机访问

Cloneable：ArrayList支持拷贝

Serializable： ArrayList支持序列化

 

ArrayList定义了如下的数组对象：

 

/**
     * 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;

 ArrayList使用elementData数组来缓存元素，使用transient关键字说明该数组对象不会被默认序列化，，开始很困惑，既然声明了ArrayList是可序列化的，为什么数组对象又声明为不能被序列化的？

 

 

 /**
     * Save the state of the <tt>ArrayList</tt> instance to a stream (that
     * is, serialize it).
     *
     * @serialData The length of the array backing the <tt>ArrayList</tt>
     *             instance is emitted (int), followed by all of its elements
     *             (each an <tt>Object</tt>) in the proper order.
     */
    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 array length
        s.writeInt(elementData.length);

	// 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 {
	// Read in size, and any hidden stuff
	s.defaultReadObject();

        // Read in array length and allocate array
        int arrayLength = s.readInt();
        Object[] a = elementData = new Object[arrayLength];

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

 因为ArrayList自定义了writeObject和readObject的方法，在writeObject中循环elementData数组序列化ArrayList中的元素。 可是为啥要这么折腾呢？

 

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

 在创建ArrayList对象的时候，如果没有指定大小，默认ArrayList的size为10；在添加元素的时候，如果当前空间不足，会按照上面的ensureCapacity的方法来扩容，扩容后的大小是原先的1.5倍。因此elementData数组很可能没有放满，会有很多无效的null元素，默认的序列化会把无效的null元素也序列化，影响效率。

 

 

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

	return (E) elementData[index];
    }

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

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

 上面是ArrayList的常见的方法，可以看到，实质上就是做些数组的操作。

 

 

下面先来看下Vector的源码：

 

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

 Vector的声明跟ArrayList一样，也是实现了List<E>, RandomAccess, Cloneable, java.io.Serializable这几个接口。

 

 

private void ensureCapacityHelper(int minCapacity) {
	int oldCapacity = elementData.length;
	if (minCapacity > oldCapacity) {
	    Object[] oldData = elementData;
	    int newCapacity = (capacityIncrement > 0) ?
		(oldCapacity + capacityIncrement) : (oldCapacity * 2);
    	    if (newCapacity < minCapacity) {
		newCapacity = minCapacity;
	    }
            elementData = Arrays.copyOf(elementData, newCapacity);
	}
    }

 上面是Vector的扩容方法，当空间不足时，会分配 size * 2的空间。

 

 

public synchronized E elementAt(int index) {
	if (index >= elementCount) {
	    throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
	}

        return (E)elementData[index];
    }

 public synchronized void addElement(E obj) {
	modCount++;
	ensureCapacityHelper(elementCount + 1);
	elementData[elementCount++] = obj;
    }

public synchronized void removeElementAt(int index) {
	modCount++;
	if (index >= elementCount) {
	    throw new ArrayIndexOutOfBoundsException(index + " >= " +
						     elementCount);
	}
	else if (index < 0) {
	    throw new ArrayIndexOutOfBoundsException(index);
	}
	int j = elementCount - index - 1;
	if (j > 0) {
	    System.arraycopy(elementData, index + 1, elementData, index, j);
	}
	elementCount--;
	elementData[elementCount] = null; /* to let gc do its work */
    }

 上面是Vector的常见的方法，跟ArrayList的主要区别是在方法上加了synchronized关键字。

 

 

 

评论

3 楼 pi88dian88 2014-01-22  

string2020 写道

楼主能不能谈谈 Hashtable，ConcurrentHashMap
这两个的区别，这两个都是hash表，都是同步的。

有什么区别

， 谢谢来踩，也只是简单的介绍下
http://pi88dian88.iteye.com/blog/2008160

2 楼 kidneyball 2014-01-09  

string2020 写道

楼主能不能谈谈 Hashtable，ConcurrentHashMap
这两个的区别，这两个都是hash表，都是同步的。

有什么区别

Hashtable的任何操作都会把整个表锁住，是阻塞的。好处是总能获取最实时的更新，比如说线程A调用putAll写入大量数据，期间线程B调用get，线程B就会被阻塞，直到线程A完成putAll，因此线程B肯定能获取到线程A写入的完整数据。坏处是所有调用都要排队，效率较低。

ConcurrentHashMap是设计为非阻塞的。在更新时会局部锁住某部分数据，但不会把整个表都锁住。同步读取操作则是完全非阻塞的。好处是在保证合理的同步前提下，效率很高。坏处是严格来说读取操作不能保证反映最近的更新。例如线程A调用putAll写入大量数据，期间线程B调用get，则只能get到目前为止已经顺利插入的部分数据。此外，使用默认构造器创建的ConcurrentHashMap比较占内存，如果程序需要创建巨量ConcurrentHashMap，应该在构造时指定concurrencyLevel （详情参考 http://ria101.wordpress.com/2011/12/12/concurrenthashmap-avoid-a-common-misuse/ ）。

1 楼 string2020 2014-01-08  

楼主能不能谈谈 Hashtable，ConcurrentHashMap
这两个的区别，这两个都是hash表，都是同步的。

有什么区别