java基础 - 05 Vector

Vector

学过C++的同学都知道，Vector也在C++中存在，他可以说是两种编程语言中都存在的数据结构，但是值得我们注意的是，Vector在java中和在C++中是存在差别的，在Java中，Vector是一个数组。并且他是动态的，可以自动调整大小且容纳新的元素，他实现了List接口，提供了许多方便的方法来操作元素，诸如添加，修改，删除，等等，Vector在Java中还保持着线程安全的特点·，也就是说，多个线程可以同时访问和修改Vector的内容。

如果你看过Vector源码的情况下，你应该知道Vector为啥可以保证线程安全，涉及到增删改查的操作，在Vector中均使用了synchronized 来修饰，synchronized给他加锁了，那能不安全嘛！

如下图所示：

Vector的使用情况

如果你是在开发岗位的开发者，你应该会发现，我们的Vector在C++中使用频繁，但是在Java中我们用起来就很少了，这是为什么呢？

原因在于，我们的Vector在实现线程的时候，会带来额外的性能开销，在单线程的环境下，我们作为Java开发者更加喜欢ArrayList，在单线程的情况下，ArrayList查询会比Vector更加高效。此外，Java提供了更加先进的并发集合类，例如ConcurrentLinkedQueue以及上篇我们介绍的CopyOnWriteArrayList，他们在多线程的环境下比Vector更加具有性能优势。

至于为啥Java中的ArrayList会比Vector更加高效，这是由于Vector在实现线程安全的过程中，会带来额外的性能开销，但是因为ArrayList并不具备线程安全的特性，所以其在单线程的情况下其性能更高。

1. 修改元素

对于修改元素，两者的效率是相同的，都是O(1)。

2. 删除元素

对于删除元素，Vector和ArrayList的效率都是O(n)，其中n是元素的数量。但是，如果删除的元素在列表的末尾，ArrayList的效率会更高，因为它不需要移动其他元素。

3. 添加元素

对于添加元素，Vector和ArrayList的效率都是O(1)，但是如果添加元素导致容量不足，Vector会自动增加容量，这会带来额外的性能开销。

4. 查询元素

对于查询元素，两者的效率都是O(1)。

但如果是在单线程的情况下，建议还是使用ArrayList，具体原因，我们可以通过一个案例进行分析：

 public static void main(String[] args) {
        Vector<String> vector1 = new Vector<>();
        vector1.add("apple");
        vector1.add("banana");

        for (String line : vector1) {
            System.out.println(line);
        }

        // 使用ArrayList进行操作
        ArrayList<Integer> arrayList = new ArrayList<>();

        // 添加元素
        long startTime = System.nanoTime();
        for (int i = 0; i < 1000000; i++) {
            arrayList.add(i);
        }
        long endTime = System.nanoTime();
        long arrayListAddTime = endTime - startTime;
        System.out.println("ArrayList 添加元素耗时: " + arrayListAddTime + " 纳秒");

        // 修改元素
        startTime = System.nanoTime();
        arrayList.set(500000, 999);
        endTime = System.nanoTime();
        long arrayListSetTime = endTime - startTime;
        System.out.println("ArrayList 修改元素耗时: " + arrayListSetTime + " 纳秒");

        // 删除元素
        startTime = System.nanoTime();
        arrayList.remove(500000);
        endTime = System.nanoTime();
        long arrayListRemoveTime = endTime - startTime;
        System.out.println("ArrayList 删除元素耗时: " + arrayListRemoveTime + " 纳秒");

        // 查询元素
        startTime = System.nanoTime();
        int element = arrayList.get(500000);
        endTime = System.nanoTime();
        long arrayListGetTime = endTime - startTime;
        System.out.println("ArrayList 查询元素耗时: " + arrayListGetTime + " 纳秒");


        // 使用Vector进行操作
        Vector<Integer> vector = new Vector<>();

        // 添加元素
        startTime = System.nanoTime();
        for (int i = 0; i < 1000000; i++) {
            vector.add(i);
        }
        endTime = System.nanoTime();
        long vectorAddTime = endTime - startTime;
        System.out.println("Vector 添加元素耗时: " + vectorAddTime + " 纳秒");

        // 修改元素
        startTime = System.nanoTime();
        vector.set(500000, 999);
        endTime = System.nanoTime();
        long vectorSetTime = endTime - startTime;
        System.out.println("Vector 修改元素耗时: " + vectorSetTime + " 纳秒");

        // 删除元素
        startTime = System.nanoTime();
        vector.remove(500000);
        endTime = System.nanoTime();
        long vectorRemoveTime = endTime - startTime;
        System.out.println("Vector 删除元素耗时: " + vectorRemoveTime + " 纳秒");

        // 查询元素
        startTime = System.nanoTime();
        element = vector.get(500000);
        endTime = System.nanoTime();
        long vectorGetTime = endTime - startTime;
        System.out.println("Vector 查询元素耗时: " + vectorGetTime + " 纳秒");
    }

一次效果可能不是很明显，我们多试试几次，在得结论，在单线程情况下。我们的ArrayList还是要比Vector的效率更高，当然这个还得你自己慢慢对比，对测试几次，在得出结论。知道注意的是，实际情况下的性能会收到多种因素的影响，比如硬件，JVM实现等情况。

Vector的常见方法

Vector的具体方法如图所示，我们不一一进行讲解了，我们就围绕简单的几个进行讲解，也是我们在实际开发中用的较多的几个方法。

结合源码进行分析：

成员变量

构造方法

/**
 *使用指定的初始容量和容量增量构造一个空的向量。
 */
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal    Capacity: "+initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

/**
 * 使用指定的初始容量和等于零的容量增量构造一个空向量。
 */
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

/**
 *构造一个空向量，使其内部数据数组的大小为 10，其标准容量增量为零。
 */
public Vector() {
    this(10);
}

/**
 * 构造一个包含指定 collection 中的元素的向量且按迭代器返回元素的顺序排列。
 */
public Vector(Collection<? extends E> c) {
    elementData = c.toArray();
    elementCount = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    //c.toArray有可能返回的不是Object[]类型，
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
        //Arrays.copyOf(elementData, elementCount, Object[].class);这个方法就是用来创建1个Object[]数组，这样数组中就可以存放任意对象了。
}

boolean add(E e): 将指定元素添加到此向量的末尾。

public synchronized boolean add(E e) {
    //修改次数+1
    modCount++;
    //扩容
    ensureCapacityHelper(elementCount + 1);
    //元素放到向量末尾
    elementData[elementCount++] = e;
    return true;
}

//保证容量足够
private void ensureCapacityHelper(int minCapacity) {
    //获取现有数组大小
    int oldCapacity = elementData.length;
    //若要求的最小容量大于现有容量，进行扩容
    if (minCapacity > oldCapacity) {
        Object[] oldData = elementData;
        //若设置了增量则为现有容量大小+增量，否则现有容量*2
        int newCapacity = (capacityIncrement > 0) ?
        (oldCapacity + capacityIncrement) : (oldCapacity * 2);
        //若计算后的扩容容量都不满足最小容量要求，本次扩容到最小容量
        if (newCapacity < minCapacity) {
            newCapacity = minCapacity;
         }
         //进行扩容并数组复制
         elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

对源码进行相关分析可知，synchronized保证新增同步，扩容方案为：先计算预期扩容大小（容量增量>0，则预期为：现有容量+容量增量，否则为：现有容量*2），计算后与要求的最小容量比较，取最大值。
之所以有计算预期扩容大小，是因为每次add时，扩容为现有容量+要新增的元素个数，如果每次都扩容到刚刚好放所有新元素，则每次都需要扩容，进行数组复制，性能会比较差。

void add(int index, E element): 在此向量的指定位置插入指定的元素。

public void add(int index, E element) {
    insertElementAt(element, index);
}

public synchronized void insertElementAt(E obj, int index) {
    //修改次数+1
    modCount++;
    //数组越界检查
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                             + " > " + elementCount);
    }
    //扩容
    ensureCapacityHelper(elementCount + 1);
    //向量扩容并复制
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    //设置指定索引元素为新元素
    elementData[index] = obj;
    //容量元素数+1
    elementCount++;
}

boolean addAll(Collection c) :将指定 Collection 中的所有元素添加到此向量的末尾，按照指定 collection 的迭代器所返回的顺序添加这些元素。

public synchronized boolean addAll(Collection<? extends E> c) {
    //修改次数+1
    modCount++;
    //获取collection数组
    Object[] a = c.toArray();
    int numNew = a.length;
    //扩容
    ensureCapacityHelper(elementCount + numNew);
    //元素数组复制，扩容，并将添加到向量末尾
    System.arraycopy(a, 0, elementData, elementCount, numNew);
    //更新元素数
    elementCount += numNew;
    //返回是否新增了元素
    return numNew != 0;
}

E get(int index):返回向量中指定位置的元素

public synchronized E get(int index) {
    //数组边界检查
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    return (E)elementData[index];
}

E set(int index, E element):用指定的元素替换此向量中指定位置处的元素。

public synchronized E set(int index, E element) {
    //数组边界检查
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    //获取对应索引原有元素值
    Object oldValue = elementData[index];
    //设置新的元素值
    elementData[index] = element;
    //返回原有元素值
    return (E)oldValue;
}

boolean remove(Object o):引用块内容移除此向量中指定元素的第一个匹配项，如果向量不包含该元素，则元素保持不变。

public boolean remove(Object o) {
   return removeElement(o);
}

public synchronized boolean removeElement(Object obj) {
    //修改次数+1
    modCount++;
    int i = indexOf(obj);
    if (i >= 0) {
        removeElementAt(i);
        return true;
    }
    return false;
}
/**
 *返回此向量中第一次出现的指定元素的索引，如果此向量不包含该元素，则返回 -1。
 */
public int indexOf(Object o) {
    return indexOf(o, 0);
}
/**
 *返回此向量中第一次出现的指定元素的索引，从 index 处正向搜索，如果未找到该元素，则返回 -1。
 */
public synchronized int indexOf(Object o, int index) {
    if (o == null) {
  
    //元素为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;
}

这里有个判断为空，之所以判断元素是否为空，主要是为了NULL与“==”进行匹配，否则使用equals,主要目标是避免Null也使用看equals会出现的空指针异常。

E remove(int index): 移除此向量中指定位置的元素。

public synchronized E remove(int index) {
    //修改次数+1
    modCount++;
    //数组边界检查
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    //获取原有数值    
    Object oldValue = elementData[index];
    //计算要移动的元素数
    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        //复制元素，并将元素整体前移一位，从索引index+1开始
        //此时倒数第二个元素和末尾元素相同
        System.arraycopy(elementData, index+1, elementData, index,
                 numMoved);
    //设置末尾为空，等待垃圾回收              
    elementData[--elementCount] = null; // Let gc do its work
    //返回被移除的元素
    return (E)oldValue;
}

boolean removeAll(Collection c):从此向量中移除包含在指定 Collection 中的所有元素。

public synchronized boolean removeAll(Collection<?> c) {
        //调用的父类(AbstractList)的父类(AbstractCollection)
        return super.removeAll(c);
}

/**
 * 移除此 collection 中那些也包含在指定 collection 中的所有元素（可选操作）。
 */
public boolean removeAll(Collection<?> c) {
    boolean modified = false;
    Iterator<?> e = iterator();
    while (e.hasNext()) {
        if (c.contains(e.next())) {
        e.remove();
        modified = true;
        }
    }
    return modified;
}