Java集合之Vector详解

简介

Vector的内部实现类似于ArrayList,Vector也是基于一个容量能够动态增长的数组来实现的,该类是JDK1.0版本添加的类,它的很多实现方法都加入了同步语句,因此是线程安全的(但Vector其实也只是相对安全,有些时候还是要加入同步语句来保证线程的安全,我们后面会有例子来说明这一点)。

Vector类声明如下:

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

Vector继承于AbstractList,实现了List、RandomAccess、Cloneable、 Serializable等接口。

ArrayList实现了List接口,可以对它进行队列操作;实现了RandmoAccess接口,即提供了随机访问功能;实现了Cloneable接口,能被克隆;实现了Serializable接口,因此它支持序列化,能够通过序列化传输。

Vector源码详解

Vector内部通过一个Object数组来存储数据:

protected Object[] elementData;

Vector使用elementCount变量来表示实际存储的元素个数:

protected int elementCount;

Vector有四个构造方法:

// 创建一个空的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;
}

// 创建一个空的Vector,并且指定了Vector的初始容量
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

// 创建一个空的Vector,并且指定了Vector的初始容量为10
public Vector() {
    this(10);
}

// 根据其他集合来创建一个非空的Vector
public Vector(Collection 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);
}

我们下面主要来看一看Vector的add和remove方法。

add方法

Vector有两个重载的Add方法:

// 在数组elementData尾部添加一个元素
public synchronized boolean add(E e)
// 在数组elementData指定位置index处添加元素
public void add(int index, E element)
add(E e)方法

add(E e)方法源码如下:

// 在数组elementData尾部添加一个元素
public synchronized boolean add(E e) {
    modCount++;
    // 容量大小判断
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

该方法首先要判断elementData数组的容量是否能够容纳新的元素,若不能,则需要进行扩容操作,然后将元素e放置在数组的size位置。ensureCapacityHelper(int)方法源码如下:

private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    // 增加元素后,ArrayList中要存储的元素个数为minCapacity
    // 若此时minCapacity > elementData原始的容量,则要按照minCapacity进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

扩容的最终操作是通过grow(int)方法来实现的:

private void grow(int minCapacity) {
    // overflow-conscious code
    // 获取elementData的原始容量
    int oldCapacity = elementData.length;
    // 计算新的容量
    // 如果在构造方法中设置了capacityIncrement > 0,那么新数组长度就是原数组长度 + capacityIncrement
    // 否则,新数组长度就是原数组长度 * 2
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                        capacityIncrement : oldCapacity);
    // 若进行扩容后,capacity仍然比实际需要的小,则新容量更改为实际需要的大小,即minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新数组的长度比虚拟机能够提供给数组的最大存储空间大,则将新数组长度更改为最大正数:Integer.MAX_VALUE
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 按照新的容量newCapacity创建一个新数组,然后再将原数组中的内容copy到新数组中
    elementData = Arrays.copyOf(elementData, newCapacity);
}

和ArrayList的扩容步骤很相似,这里不再介绍。

add(int index, E element)方法

add(int index, E element)方法源码如下:

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

该方式其实是调用了insertElementAt方法:

public synchronized void insertElementAt(E obj, int index) {
    // fail-fast机制
    modCount++;
    // 判断index下标的合法性
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                                                    + " > " + elementCount);
    }
    // 判断容量大小
    ensureCapacityHelper(elementCount + 1);
    // 数组拷贝,将index到末尾的元素拷贝到index + 1到末尾的位置,将index的位置留出来
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    elementData[index] = obj;
    elementCount++;
}

remove方法

remove方法在Vector中同样有两种实现方式:

// 根据元素删除
public boolean remove(Object o)
// 根据index下标删除元素
public synchronized E remove(int index)

我们先看remove(Object o)方法。

remove(Object o)方法

remove(Object o)方法源码如下:

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

其内部通过removeElement方法来删除元素:

public synchronized boolean removeElement(Object obj) {
    // fail-fast机制
    modCount++;
    // 查找元素obj在数组中的下标
    int i = indexOf(obj);
    // 若下标 >= 0
    if (i >= 0) {
        // 调用removeElementAt(int)方法删除元素
        removeElementAt(i);
        return true;
    }
    return false;
}

我们先来看indexOf(Object)方法:

public int indexOf(Object o) {
    return indexOf(o, 0);
}
public synchronized int indexOf(Object o, int index) {
    // 若要查找的元素为null
    if (o == null) {
        for (int i = index ; i < elementCount ; i++)
            if (elementData[i]==null)
                return i;
    } 
    // 若要查找的元素不为null
    else {
        for (int i = index ; i < elementCount ; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

Vector查找元素时,是分为元素为null和不为null两种方式来判断的,这也说明Vector允许添加null元素;同时,如果这个元素在Vector中存在多个,则只会找出从index开始,最先出现的那个。

找到元素对应的下标,若下标 >= 0,则说明元素在数组中存在,然后通过removeElementAt(int)方法来删除元素,removeElementAt(int)方法源码如下:

public synchronized void removeElementAt(int index) {
    modCount++;
    // index下标合法性检验
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                    elementCount);
    }
    else if (index < 0) {
        throw new ArrayIndexOutOfBoundsException(index);
    }
    // 要移动的元素个数
    int j = elementCount - index - 1;
    if (j > 0) {
        // 将index之后的元素向前移动一位
        System.arraycopy(elementData, index + 1, elementData, index, j);
    }
    elementCount--;
    elementData[elementCount] = null; /* to let gc do its work */
}
remove(int index)方法

remove(int index)方法源码如下:

public synchronized E remove(int index) {
    modCount++;
    // index下标合法性检验
    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;
}

Vector的相对线程安全

我们前面说过Vector是相对线程安全的,为什么这么说呢?

我们看下面一段代码:

public class VectorTest {
	static class MyThread extends Thread {
		private CountDownLatch countDownLatch;
		private Vector vector;
		private String element;
		
		public MyThread(CountDownLatch countDownLatch, Vector vector, String element) {
			this.countDownLatch = countDownLatch;
			this.vector = vector;
			this.element = element;
		}
		
		@Override
		public void run() {
			super.run();
			
			try {
				if (!vector.contains(element)) {
					// 注意这里
					Thread.sleep(1000);
					vector.add(element);
				}
			} catch (InterruptedException e) {
				e.printStackTrace();
			} finally {
				countDownLatch.countDown();
			}
		}
	}

	public static void main(String[] args) throws InterruptedException {
		CountDownLatch countDownLatch = new CountDownLatch(2);
		Vector vector = new Vector<>();
		
		MyThread myThread1 = new MyThread(countDownLatch, vector, "abc");
		MyThread myThread2 = new MyThread(countDownLatch, vector, "abc");
		
		myThread1.start();
		myThread2.start();
		
		countDownLatch.await();
		
		int vectorSize = vector.size();
		System.out.println("vector size: " + vectorSize);
		for (int i = 0; i < vectorSize; i++) {
			System.out.println("index " + i + ": " + vector.get(i));
		}
	}
}

运行结果(不唯一):

vector size: 2
index 0: abc
index 1: abc

注意注释处的一段代码,该段代码是判断元素element是否存在,不存在的话,则将其添加到vector之中,如果线程1和线程2同时运行该段代码,设想一下如下情景:

线程1通过vector.contains(element)同步方法来判断元素是否存在,此时,该方法返回false,即表明线程1可以将element元素插入Vector中;但是运行完该方法之后,线程1开始sleep,那这时,线程2开始运行vector.contains(element)同步方法,该方法仍然返回了false,即线程2可以将element元素插入Vector中,然后线程2开始sleep,最终结果,就是线程1和线程2都将元素“abc”添加到了vector之中,这就是我们为什么说Vector是相对线程安全的了。

要解决该问题,需要我们在自己的业务代码代码中进行同步控制,比如将那一段代码修改为如下:

synchronized (vector) {
    if (!vector.contains(element)) {
        Thread.sleep(1000);
        vector.add(element);
    }
}

则程序运行结果为:

vector size: 1
index 0: abc

可以看到,这才是我们预期的结果。

相关博客

Java集合之ArrayList详解

你可能感兴趣的