Felix's Blog
Series

Vector

felix.shao2025-02-16

Vector

简述

核心内容
  • 数据结构。
  • 初始化）。
  • 添加元素。
  • 移除元素。
  • 查找。
  • 扩容（含自动扩容）。
Vector 简介

 Vector JDK1.0 开始支持的。
 Vector 和 Arraylist 类型，但是是线程安全的，这里着重关注下不同的点，相似的功能参考Arraylist 源码分析。

详述

Vector 类图

 略，同 ArrayList。

数据结构和核心方法
public class Vector<E> ...{

    /** 保存 Vector 数据的数组，和 ArrayList 对比，没有 transient */
    protected Object[] elementData;

    /** Vector 中实际数据的数量，ArrayList 的属性为 size */
    private int elementCount;

    /** 扩容因子（容量增长系数），ArrayList 无该字段 */
    protected int capacityIncrement;

    public boolean add(E e)...

    public boolean addAll(Collection<? extends E> c)...

    public E set(int index, E element)...

    public E get(int index)...

    public E remove(int index)...

    public void trimToSize()...

}

 数据结构同 ArrayList，内容不再冗余说明。

TIP

 Vector 中 elementData 为什么没有被 transient 修饰?
 估摸是历史原因，Vector 的 JDK1.0 版本的，ArrayList 是 JDK1.2 版本的，因此 ArrayList 对此做了点优化。

初始化

 Vector 提供了四种方式的构造器。

/** Vector 带容量大小的构造函数。*/
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                            initialCapacity);
    //新建一个数组，数组容量是 initialCapacity                                        
    this.elementData = new Object[initialCapacity];
    //设置增长容量增长系数
    this.capacityIncrement = capacityIncrement;
}

public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

public Vector() {
    this(10);
}

/** Vector 带容量大小的构造函数 */
public Vector(Collection<? extends E> c) {
    elementData = c.toArray();
    elementCount = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}

TIP

 Vector 中默认的初始化容量是 10，通过跟踪调试源码发现，public Vector()... 默认已经分配好了 10 长度的空间。

添加元素-add

TIP

  • 对比 ArrayList,大部分方法上加了 synchronized 关键字处理。
  • 其他的一些细节，看注释描述。
/** 添加一个元素，直接添加到数组末尾 */
public synchronized boolean add(E e) {
    modCount++; // 多了这个，是因为有的方法没有加 synchronized
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

/** 在指定索引添加一个元素 */
public void add(int index, E element) {
    insertElementAt(element, 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++;
}
添加元素-addAll
/** 在末尾索引处开始添加集合的所有元素 */
public synchronized boolean addAll(Collection<? extends E> c) {
    modCount++;
    Object[] a = c.toArray();
    int numNew = a.length;
    // 在这里会做方法扩容处理
    ensureCapacityHelper(elementCount + numNew);
    // 添加元素
    System.arraycopy(a, 0, elementData, elementCount, numNew);
    elementCount += numNew;
    return numNew != 0;
}

/** 在指定索引处开始添加集合的所有元素 */
public synchronized boolean addAll(int index, Collection<? extends E> c) {
    modCount++;
    if (index < 0 || index > elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityHelper(elementCount + numNew);

    int numMoved = elementCount - index;
    if (numMoved > 0)
        // index 的元素移动从 c.size 长度
        System.arraycopy(elementData, index, elementData, index + numNew,
                            numMoved);
    // 复制要添加的元素
    System.arraycopy(a, 0, elementData, index, numNew);
    elementCount += numNew;
    return numNew != 0;
}
移除元素-remove
/** 移除指定索引上的元素
 *  删除操作是 add() 操作的逆过程，需要将删除点之后的元素向前移动一个位置。需要注意的是为了让 GC 起作用，必须显式的为最后一个位置赋 null 值
 */
public synchronized E remove(int index) {
    modCount++;
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);

    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
    elementData[--elementCount] = null; // Let gc do its work

    return oldValue;
}

/** 移除指定的元素 */
public boolean remove(Object o) {
    return removeElement(o);
}

public synchronized boolean removeElement(Object obj) {
    modCount++;
    int i = indexOf(obj);
    if (i >= 0) {
        removeElementAt(i);
        return true;
    }
    return false;
}

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 */
}
查找元素-get
/** 查找元素 */
public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index];
}
扩容(含自动扩容)

 扩容和 ArrayList 不同，代码如下：

/** 扩容方法入口 */
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;
    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);
}
其他方法-trimToSize
/** 将底层数组的容量调整为当前列表保存的实际元素的大小 */
public synchronized void trimToSize() {
    modCount++;
    int oldCapacity = elementData.length;
    if (elementCount < oldCapacity) {
        elementData = Arrays.copyOf(elementData, elementCount);
    }
}
其他方法-indexOf、lastIndexOf
/** 获取元素的第一次出现的 index */
public int indexOf(Object o) {
    return indexOf(o, 0);
}

/** 获取元素从 index 索引开始，第一次出现的索引，ArrayList 没有该方法 */
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++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

/** 获取元素的最后一次出现的 index */
public synchronized int lastIndexOf(Object o) {
    return lastIndexOf(o, elementCount-1);
}

/** 获取元素从 index 索引结尾，最后一次出现的索引，ArrayList 没有该方法 */
public synchronized int lastIndexOf(Object o, int index) {
    if (index >= elementCount)
        throw new IndexOutOfBoundsException(index + " >= "+ elementCount);

    if (o == null) {
        for (int i = index; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = index; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}
其他方法-toArray
public synchronized Object[] toArray() {
    return Arrays.copyOf(elementData, elementCount);
}

总结

TIP

  • 除线程安全外，其他基本同 ArrayList。
  • Vector 的方法里面保留了 modCount++ 等 fail-fast 机制的内容。

附录一、参考文献

Last Updated 2/18/2025, 2:43:17 PM
ON THIS PAGE