0. Vector是什么
- 动态数组
- 实现List接口
- 内容改变相关的方法均为
synchronized
1. 实现的本质
- 数组
2. 主要api解析
2.1 构造函数
默认的initialCapacity为10，capacityIncrement为0
public Vector()
public Vector(int initialCapacity)
public Vector(int initialCapacity, int capacityIncrement)
public Vector(Collection<? extends E> c)
2.2 add方法
public synchronized boolean add(E e)
public void add(int index, E element)
public synchronized boolean addAll(Collection<? extends E> c)
public synchronized boolean addAll(int index, Collection<? extends E> c)
public synchronized void addElement(E obj)
第二个方法不是synchronized是因为它是调用了一个synchronized方法来实现的，这些方法的流程是相似的
- 检查容量是否足够插入数据
- 如果不够的话，扩容
- 添加新数据
/**
* Inserts the specified element at the specified position in this Vector.
* Shifts the element currently at that position (if any) and any
* subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws ArrayIndexOutOfBoundsException if the index is out of range
* ({@code index < 0 || index > size()})
* @since 1.2
*/
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}. Each component in this vector with
* an index greater or equal to the specified {@code index} is
* shifted upward to have an index one greater than the value it had
* previously.
*
* <p>The index must be a value greater than or equal to {@code 0}
* and less than or equal to the current size of the vector. (If the
* index is equal to the current size of the vector, the new element
* is appended to the Vector.)
*
* <p>This method is identical in functionality to the
* {@link #add(int, Object) add(int, E)}
* method (which is part of the {@link List} interface). Note that the
* {@code add} method reverses the order of the parameters, to more closely
* match array usage.
*
* @param obj the component to insert
* @param index where to insert the new component
* @throws ArrayIndexOutOfBoundsException if the index is out of range
* ({@code index < 0 || index > size()})
*/
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++;
}
2.3 remove方法
同样的，所有的remove方法也是synchronized修饰的
和ArrayList类似，也是将后面的元素前移，通过System.arraycopy()实现
public synchronized E remove(int index)
public boolean remove(Object o)
public synchronized boolean removeAll(Collection<?> c)
public synchronized void removeAllElements()
public synchronized boolean removeElement(Object obj)
public synchronized void removeElementAt(int index)
protected synchronized void removeRange(int fromIndex, int toIndex)
以第二个方法为例：
/**
* Removes the first occurrence of the specified element in this Vector
* If the Vector does not contain the element, it is unchanged. More
* formally, removes the element with the lowest index i such that
* {@code (o==null ? get(i)==null : o.equals(get(i)))} (if such
* an element exists).
*
* @param o element to be removed from this Vector, if present
* @return true if the Vector contained the specified element
* @since 1.2
*/
public boolean remove(Object o) {
return removeElement(o);
}
/**
* Removes the first (lowest-indexed) occurrence of the argument
* from this vector. If the object is found in this vector, each
* component in the vector with an index greater or equal to the
* object's index is shifted downward to have an index one smaller
* than the value it had previously.
*
* <p>This method is identical in functionality to the
* {@link #remove(Object)} method (which is part of the
* {@link List} interface).
*
* @param obj the component to be removed
* @return {@code true} if the argument was a component of this
* vector; {@code false} otherwise.
*/
public synchronized boolean removeElement(Object obj) {
modCount++;
//定位到需要删除的元素的索引
int i = indexOf(obj);
if (i >= 0) {
//删除指定位置元素
removeElementAt(i);
return true;
}
return false;
}
/**
* Returns the index of the first occurrence of the specified element
* in this vector, or -1 if this vector does not contain the element.
* More formally, returns the lowest index {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*
* @param o element to search for
* @return the index of the first occurrence of the specified element in
* this vector, or -1 if this vector does not contain the element
*/
public int indexOf(Object o) {
return indexOf(o, 0);
}
/**
* Returns the index of the first occurrence of the specified element in
* this vector, searching forwards from {@code index}, or returns -1 if
* the element is not found.
* More formally, returns the lowest index {@code i} such that
* <tt>(i >= index && (o==null ? get(i)==null : o.equals(get(i))))</tt>,
* or -1 if there is no such index.
*
* @param o element to search for
* @param index index to start searching from
* @return the index of the first occurrence of the element in
* this vector at position {@code index} or later in the vector;
* {@code -1} if the element is not found.
* @throws IndexOutOfBoundsException if the specified index is negative
* @see Object#equals(Object)
*/
//从i=0开始往后查找元素位置
public synchronized int indexOf(Object o, int index) {
if (o == null) {
for (int i = index ; i < elementCount ; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = index ; i < elementCount ; i++)
//这里使用equals比较
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* Deletes the component at the specified index. Each component in
* this vector with an index greater or equal to the specified
* {@code index} is shifted downward to have an index one
* smaller than the value it had previously. The size of this vector
* is decreased by {@code 1}.
*
* <p>The index must be a value greater than or equal to {@code 0}
* and less than the current size of the vector.
*
* <p>This method is identical in functionality to the {@link #remove(int)}
* method (which is part of the {@link List} interface). Note that the
* {@code remove} method returns the old value that was stored at the
* specified position.
*
* @param index the index of the object to remove
* @throws ArrayIndexOutOfBoundsException if the index is out of range
* ({@code index < 0 || index >= size()})
*/
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 */
}
2.4 get
直接数组取值
/**
* Returns the element at the specified position in this Vector.
*
* @param index index of the element to return
* @return object at the specified index
* @throws ArrayIndexOutOfBoundsException if the index is out of range
* ({@code index < 0 || index >= size()})
* @since 1.2
*/
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
2.5 扩容
如果指定了增长的大小，则按指定大小增长，否则增加为原来的2倍
/**
* This implements the unsynchronized semantics of ensureCapacity.
* Synchronized methods in this class can internally call this
* method for ensuring capacity without incurring the cost of an
* extra synchronization.
*
* @see #ensureCapacity(int)
*/
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
//如果当前数组不足以容纳新添加的数据， 则扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//如果指定了每次增加的大小，则按此大小增长，否则扩大为原来的2倍
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
3. 总结
- 初始容量为10，未指定增长系数时2倍增长
- 查找元素快，增删元素慢
-
synchronized版本的ArrayList - 某些情况下非线程安全
4. 参考
- 源码 build 1.8.0_121-b13版本
