首页 > 代码库 > Vector与ArrayList 的理解
Vector与ArrayList 的理解
最近在看Vector与ArrayList的源码,看下他们的区别与联系。
- Vector是线程安全的集合类,ArrayList并不是线程安全的类。Vector类对集合的元素操作时都加了synchronized,保证线程安全。
- Vector与ArrayList本质上都是一个Object[] 数组,ArrayList提供了size属性,Vector提供了elementCount属性,他们的作用是记录集合内有效元素的个数。与我们平常调用的arrayList.size()和vector.size()一样返回的集合内有效元素的个数。
- Vector与ArrayList的扩容并不一样,Vector默认扩容是增长一倍的容量,Arraylist是增长50%的容量。
- Vector与ArrayList的remove,add(index,obj)方法都会导致内部数组进行数据拷贝的操作,这样在大数据量时,可能会影响效率。
- Vector与ArrayList的add(obj)方法,如果新增的有效元素个数超过数组本身的长度,都会导致数组进行扩容。
先看下他们的源码是怎么定义内部数据存储的:
1 private static final long serialVersionUID = 8683452581122892189L; 2 3 /** 4 * Default initial capacity. 5 */ 6 private static final int DEFAULT_CAPACITY = 10; 7 8 /** 9 * Shared empty array instance used for empty instances. 10 */ 11 private static final Object[] EMPTY_ELEMENTDATA =http://www.mamicode.com/ {}; 12 13 /** 14 * The array buffer into which the elements of the ArrayList are stored. 15 * The capacity of the ArrayList is the length of this array buffer. Any 16 * empty ArrayList with elementData =http://www.mamicode.com/= EMPTY_ELEMENTDATA will be expanded to>17 * DEFAULT_CAPACITY when the first element is added. 18 */ 19 private transient Object[] elementData; 20 21 /** 22 * The size of the ArrayList (the number of elements it contains). 23 * 24 * @serial 25 */ 26 private int size;
这是ArrayList的定义,他首先定义了他的初始化容量为10
private static final int DEFAULT_CAPACITY = 10
这里应该看到了数据存储是放在Object数组里的
private transient Object[] elementData
定义了数据的长度size
The size of the ArrayList (the number of elements it contains)
再看看Vector的定义:
1 /** 2 * The array buffer into which the components of the vector are 3 * stored. The capacity of the vector is the length of this array buffer, 4 * and is at least large enough to contain all the vector‘s elements. 5 * 6 * <p>Any array elements following the last element in the Vector are null. 7 * 8 * @serial 9 */ 10 protected Object[] elementData; 11 12 /** 13 * The number of valid components in this {@code Vector} object. 14 * Components {@code elementData[0]} through 15 * {@code elementData[elementCount-1]} are the actual items. 16 * 17 * @serial 18 */ 19 protected int elementCount; 20 21 /** 22 * The amount by which the capacity of the vector is automatically 23 * incremented when its size becomes greater than its capacity. If 24 * the capacity increment is less than or equal to zero, the capacity 25 * of the vector is doubled each time it needs to grow. 26 * 27 * @serial 28 */ 29 protected int capacityIncrement;
Vector定义了数组
protected Object[] elementData;
有效元素个数
protected int elementCount
Vector增长容量,默认0
protected int capacityIncrement
Vector和ArrayList在元素超过初始大小时扩容是不一样的,但是也不像网上说的Vector增长是按一倍增长,我觉得应该加默认两个字才对,Vector中的元素个数超过了初始化容量的话,默认确实会增长一倍,请看代码:
1 /** 2 * The maximum size of array to allocate. 3 * Some VMs reserve some header words in an array. 4 * Attempts to allocate larger arrays may result in 5 * OutOfMemoryError: Requested array size exceeds VM limit 6 */ 7 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 8 9 private void grow(int minCapacity) { 10 // overflow-conscious code 11 int oldCapacity = elementData.length; 12 int newCapacity = oldCapacity + ((capacityIncrement > 0) ? 13 capacityIncrement : oldCapacity); 14 if (newCapacity - minCapacity < 0) 15 newCapacity = minCapacity; 16 if (newCapacity - MAX_ARRAY_SIZE > 0) 17 newCapacity = hugeCapacity(minCapacity); 18 elementData =http://www.mamicode.com/ Arrays.copyOf(elementData, newCapacity); 19 }
代码里在判断增长容量(简称增量)参数时如果增量大于0时,是会按增量进行扩容的,否则的话才会增加一倍的容量到数组中。
而Vector在初始化加载构造函数时,开发人员是可以指定其增量的大小的,并不是必须要根据增加一倍的规则进行增加。还是看代码:
1 public Vector(int initialCapacity, int capacityIncrement) { 2 super(); 3 if (initialCapacity < 0) 4 throw new IllegalArgumentException("Illegal Capacity: "+ 5 initialCapacity); 6 this.elementData = http://www.mamicode.com/new Object[initialCapacity]; 7 this.capacityIncrement = capacityIncrement; 8 } 9 10 /** 11 * Constructs an empty vector with the specified initial capacity and 12 * with its capacity increment equal to zero. 13 * 14 * @param initialCapacity the initial capacity of the vector 15 * @throws IllegalArgumentException if the specified initial capacity 16 * is negative 17 */ 18 public Vector(int initialCapacity) { 19 this(initialCapacity, 0); 20 } 21 22 /** 23 * Constructs an empty vector so that its internal data array 24 * has size {@code 10} and its standard capacity increment is 25 * zero. 26 */ 27 public Vector() { 28 this(10); 29 }
可以看到在构造函数中已经表明,可以指定其增量的大小,如果没有指定默认0。数组的初始化大小为10。
但是ArrayList就不可以进行增量的修改指定。还是看代码:
1 /** 2 * Increases the capacity to ensure that it can hold at least the 3 * number of elements specified by the minimum capacity argument. 4 * 5 * @param minCapacity the desired minimum capacity 6 */ 7 private void grow(int minCapacity) { 8 // overflow-conscious code 9 int oldCapacity = elementData.length; 10 int newCapacity = oldCapacity + (oldCapacity >> 1); //看这里 11 if (newCapacity - minCapacity < 0) 12 newCapacity = minCapacity; 13 if (newCapacity - MAX_ARRAY_SIZE > 0) 14 newCapacity = hugeCapacity(minCapacity); 15 // minCapacity is usually close to size, so this is a win: 16 elementData =http://www.mamicode.com/ Arrays.copyOf(elementData, newCapacity); 17 }
首先在构造函数中,ArrayList就没有提供相应的设置增量的方法,而扩容方法grow中直接就对数组进行增量50%的操作了,并没有相应的参数设置或判断增量的大小。
在上边都提到了一个静态常量是private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
这个常量是数组扩容的最大长度,但是为什么-8呢我看了上边的描述,感觉应该是:
Some VMs reserve some header words in an array.
有些虚拟机会在数组头部加入一些信息,如果还是设置最大的话,可能会导致OOM
这就是Vector和ArrayList在扩容及成员变量方面的区别及联系了。
接下来我们看看他们的源码中插入、删除等方法为什么说和LinkedList相比要慢
先看代码:
1 public synchronized void insertElementAt(E obj, int index) { 2 modCount++; 3 if (index > elementCount) { 4 throw new ArrayIndexOutOfBoundsException(index 5 + " > " + elementCount); 6 } 7 ensureCapacityHelper(elementCount + 1); 8 System.arraycopy(elementData, index, elementData, index + 1, elementCount - index); 9 elementData[index] = obj; 10 elementCount++; 11 }
Vector集合在add(int index, E element)时实际上调用了insertElementAt方法,他和删除方法实际上都是对数组进行了copy,所以在大数据量时可能会导致效率降低。ArrayList也是这样的情况。
但是在增加调用add(E e)方法时,其实就是在数组中追加数据了,如果追加数据的长度大于实际数组长度的话,会进入到grow扩容方法进行扩容。
Vector和ArrayList都提供了trimToSize()方法,这个方法是对数组容量进行缩减的方法。在这个方法中,调用方法时会对数组的元素容量及数组本身长度进行判断,如果数组内实际元素的个数比数组本身的长度少的话,调用这个方法会将数组缩减到元素个数大小。在数据量大的时候可以考虑这样做,这样可以节省不必要的空间浪费。看代码:
1 public void trimToSize() { 2 modCount++; 3 if (size < elementData.length) { 4 elementData =http://www.mamicode.com/ Arrays.copyOf(elementData, size); 5 } 6 }
Vector本身提供了一个同步方法叫setSize方法,该方法可以对当前集合进行长度设置。如果设置的长度比当前元素个数要大的话会进行判断是否需要扩容,如果不是,在给定的Size值外的元素将被置为空值。
看代码:
1 public synchronized void setSize(int newSize) { 2 modCount++; 3 if (newSize > elementCount) { 4 ensureCapacityHelper(newSize); 5 } else { 6 for (int i = newSize ; i < elementCount ; i++) { 7 elementData[i] = null; 8 } 9 } 10 elementCount = newSize; 11 }
这大体上就是Vector和ArrayList的区别
ps:以上只是个人理解,如有不对请指正。
Vector与ArrayList 的理解