黑马程序员技术交流社区

标题: 【上海校区】Java篇 - 并发容器之Vector源码分析和注意事项 [打印本页]

---

作者: 不二晨    时间: 2019-2-15 09:56
标题: 【上海校区】Java篇 - 并发容器之Vector源码分析和注意事项
今天继续来讲Java的并发容器类，这篇的主角是Vector。



1. Vector简介
数组的容量是固定的，不能动态扩展容量。在Java中提供了几个动态数组：ArrayList，Vector。两个的区别是ArrayList是非线程安全的，而Vector是线程安全的，这边说的线程安全是它自身的操作，如add，remove，clear。

另外Vector是从JDK1.0开始推出的。



2. Vector的类定义
public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
}
Vector继承了AbstractList，实现了List，所以，它是一个集合，支持相关的添加、删除、修改、遍历等功能；

Vector实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在Vector中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问；

Vector实现了Cloneable接口，即实现clone()函数，它能被克隆；

Vector实现了Serializable接口，它支持序列化。



3. Vector的变量与常量
    /**
     * Vector存放元素的容器（数组）
     */
    protected Object[] elementData;

    /**
     * Vector存放的有效元素的个数
     */
    protected int elementCount;

    /**
     * 当Vector容量不足时，扩容的容量，每次增加一倍
     */
    protected int capacityIncrement;

    /**
     * Vector数组容器的最大容量
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;



4. 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;
    }

    /**
     * 构造器参数为初始容量，扩容容量为0（自动计算，每次是当前容量翻倍）
     */
    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }

    /**
     * 构造器参数为空，初始容量为10，扩容容量为0（自动计算，每次是当前容量翻倍）
     */
    public Vector() {
        this(10);
    }

    /**
     * JDK1.2开始提供的构造器，需要传入泛型E或其子类的集合，将该集合转换成Vector
     */
    public Vector(Collection<? extends E> c) {
        // 集合直接转换成容器数组
        elementData = c.toArray();
        // 计算有效元素的个数
        elementCount = elementData.length;
        // 这边做了一个双重保护，如果toArray不是返回Object[]，则使用Arrays.copyOf复制数组
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
    }
可以看到上面通过集合转换成Vector，转换成容器数组时做了次校验。c.toArray might (incorrectly) not return Object[].

为什么会出现这种问题呢？

public class ConcurrentTest {

    public static void test() {
        // 1. 通过new ArraysList的方式传入Arrays.asList构建，这种方式可以通过
        List<String> list = new ArrayList<>(Arrays.asList("list"));
        // class java.util.ArrayList
        System.out.println(list.getClass());
        Object[] listArray = list.toArray();
        // class [Ljava.lang.Object;
        System.out.println(listArray.getClass());
        // 转换成对象数组后可以存储Object对象
        listArray[0] = new Object();

        // 2. 直接Arrays.asList构建，这种方式会报错
        List<String> asList = Arrays.asList("asList");
        // class java.util.Arrays$ArrayList
        System.out.println(asList.getClass());
        // class [Ljava.lang.String;
        Object[] asListArray = asList.toArray();
        System.out.println(asListArray.getClass());
        // ! java.lang.ArrayStoreException
        asListArray[0] = new Object();

        // 3. 直接{}构建，这种方式会报错
        String[] strings = {new String()};
        Object[] objects = strings;
        // ! java.lang.ArrayStoreException
        objects[0] = new Object();
    }

    public static void main(String[] args) {
        test();
    }
}
执行输出：

class java.util.ArrayList
Exception in thread "main" java.lang.ArrayStoreException: java.lang.Object
class [Ljava.lang.Object;
class java.util.Arrays$ArrayList
    at io.kzw.advance.csdn_blog.ConcurrentTest.test(ConcurrentTest.java:25)
class [Ljava.lang.String;
    at io.kzw.advance.csdn_blog.ConcurrentTest.main(ConcurrentTest.java:34)

Java的泛型是伪泛型，使用不当就会造成这种问题，编译期间没问题，但是执行期报错。

最主要的原因其实是list.toArray()实现方式不一样，导致返回的数组真实类型不一样：

    // java.util.Arrays$ArrayList的toArray实现
    @Override
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        int size = size();
        if (a.length < size)
            return Arrays.copyOf(this.a, size,
                    (Class<? extends T[]>) a.getClass());
        System.arraycopy(this.a, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

    // java.util.ArrayList的toArray实现
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }


5. 增删改查方法实现
(1) 添加元素

    /**
     * 同步方法，添加一个元素
     */
    public synchronized boolean add(E e) {
        // 修改数+1
        modCount++;
        // 确保数组最小容量为有效元素个数+1，小于它则扩容
        ensureCapacityHelper(elementCount + 1);
        // 存入数组，存完后有效元素个数+1
        elementData[elementCount++] = e;
        // 返回添加是否成功
        return true;
    }


   /**
    * 同步方法，在指定位置插入一个元素
    * JDK1.2之后开始提供
    */
    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);
        }
        // 确保数组最小容量为有效元素个数+1，小于它则扩容
        ensureCapacityHelper(elementCount + 1);
        // 将原来index位置的元素放到index+1处
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
        // index处的元素为传入的object
        elementData[index] = obj;
        // 有效元素个数+1
        elementCount++;
    }
可以看到，因为Vecor是数组实现，所以插入速度一般，因为涉及到数组移动。



(2) 移除元素

    /**
     * 同步方法，移除指定位置的元素，并返回移除元素
     * JDK1.2开始提供
     */
    public synchronized E remove(int index) {
        // 修改数+1
        modCount++;
        // 如果要移除的位置大于等于有效元素个数，抛出异常
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        // 获取指定位置的元素，转成E的类型
        E oldValue = elementData(index);
        // 移动数组
        int numMoved = elementCount - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 数组移动完毕后，将最后一个有效位置的元素置为null，gc时将回收该元素
        elementData[--elementCount] = null;
        // 返回移除的元素
        return oldValue;
    }

    /**
     * 同步方法，移除某个具体元素
     */
    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;
    }

    /**
     * 同步方法，移除指定位置的元素，原理和remove(int index)一样
     */
    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;
    }

    /**
     * 清空元素
     */
    public void clear() {
        removeAllElements();
    }

    /**
     * 同步方法，清空元素
     */
    public synchronized void removeAllElements() {
        // 修改数+1
        modCount++;
        // 将有效元素置为null，让gc时能回收
        for (int i = 0; i < elementCount; i++)
            elementData = null;
        // 有效元素置为0
        elementCount = 0;
    }
所以从删除的方法来看，删除速度也一般，因为涉及到数组的移动。

如果不需要使用Vector中的元素，可以调用clear()方法，这样就能让这些无用的元素在GC时回收。



(3) 获取元素

    /**
     * 同步方法，获取指定位置的元素
     */
    public synchronized E get(int index) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        // 通过索引从数组中找到该元素并返回
        return elementData(index);
    }

    /**
     * 获取某元素的位置
     */
    public int indexOf(Object o) {
        return indexOf(o, 0);
    }

    /**
     * 同步方法，获取某元素的位置
     */
    public synchronized int indexOf(Object o, int index) {
        // Vector可以存储null值
        if (o == null) {
            // 从有效元素中查找第一个null值
            for (int i = index ; i < elementCount ; i++)
                if (elementData==null)
                    return i;
        } else {
            // 从有效元素中查找第一个该对象
            for (int i = index ; i < elementCount ; i++)
                if (o.equals(elementData))
                    return i;
        }
        // 没有找到返回-1
        return -1;
    }

    /**
     * 同步方法，获取某元素在数组中最后出现的位置
     */
    public synchronized int lastIndexOf(Object o) {
        return lastIndexOf(o, elementCount-1);
    }

    /**
     * 同步方法，从指定位置向前遍历数组查找元素
     */
    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==null)
                    return i;
        } else {
            for (int i = index; i >= 0; i--)
                if (o.equals(elementData))
                    return i;
        }
        return -1;
    }

    /**
     * 同步方法，获取指定索引的元素值
     */
    public synchronized E elementAt(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }
        // 从数组中找到该索引的值
        return elementData(index);
    }

    /**
     * 同步方法，返回数组中第一个有效元素的值
     */
    public synchronized E firstElement() {
        if (elementCount == 0) {
            throw new NoSuchElementException();
        }
        return elementData(0);
    }

    /**
     * 同步方法，返回数组中最后一个有效元素的值
     */
    public synchronized E lastElement() {
        if (elementCount == 0) {
            throw new NoSuchElementException();
        }
        return elementData(elementCount - 1);
    }
查找元素的速度快，因为是数组实现，直接通过下标就可以定位到元素。



(4) 修改元素

   /**
    * 同步方法，修改指定位置的元素，并返回旧元素
    */
   public synchronized E set(int index, E element) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        // 先拿到旧元素
        E oldValue = elementData(index);
        // 数组指定位置重新赋值
        elementData[index] = element;
        // 返回旧元素
        return oldValue;
    }
修改元素的速度也快，因为是数组实现，定位元素快。



6. 关于扩容
    /**
     * (加锁)
     * 收缩容器数组大小
     */
    public synchronized void trimToSize() {
        // 修改次数+1
        modCount++;
        // 当前数组的容量
        int oldCapacity = elementData.length;
        // 如果实际存放的有效元素容量小于数组容量，则收缩
        if (elementCount < oldCapacity) {
            // 使用Arrays.copyOf复制数组
            elementData = Arrays.copyOf(elementData, elementCount);
        }
    }

    /**
     * (加锁)
     * 确保数组大小满足最小容量
     */
    public synchronized void ensureCapacity(int minCapacity) {
        // 先判断最小容量是否为正数
        if (minCapacity > 0) {
            modCount++;
            ensureCapacityHelper(minCapacity);
        }
    }

    private void ensureCapacityHelper(int minCapacity) {
        // 如果最小容量比数组大小大，则需要扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    /**
     * 扩容实现
     */
    private void grow(int minCapacity) {
        // 旧容量
        int oldCapacity = elementData.length;
        // 新容量 = 容量增量如果大于0则为旧容量+容量增量，否则为旧容量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);
    }

    private static int hugeCapacity(int minCapacity) {
        // 如果minCapacity < 0，其实是大于Integer.MAX_VALUE，会变成负数。这时抛出oom
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        // 最大为Integer.MAX_VALUE
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
扩容方式为，如果往里添加或插入一个元素，会至少扩容到比这个元素大1的大小。

扩容规则是：设置了扩容增量，新大小为旧容量大小 + 扩容增量，否则为旧容量大小的2倍。最大不能超过Integer.MAX_VALUE，否则会抛出OutOfMemoryError。





7. 源码分析总结
(1) Vector内部采用数组实现，增加，删除慢，查找快。

(2) Vector内部具有自动收缩功能(trim)。

(3) Vector的扩容方案：如果没有设置增量，则是2倍扩容，设置了增量则为旧容量 + 增量。所以如果能预估到元素的大小变化，可以在构造时传入初始容量和增量。

(4) Vector的对外方法几乎都是同步的，这能保证Vector本身的操作是同步的，但是一段代码中，它之外的方法如果需要同步还需单独处理。并且这样的同步方式和Hashtable一样，效果不高，任何一个操作都是锁整张表。





8. 使用注意事项
    public static void main(String[] args) {
        Vector<Integer> vector = new Vector<>();
        while (true) {
            for (int i = 0; i < 10; i++) {
                vector.add(i);
                System.out.println("add" + i);
            }
            Thread printThread = new Thread() {
                @Override
                public void run() {
                    try {
                        for (int i = 0; i < vector.size(); i++) {
                            System.out.println(vector.get(i));
                            Thread.sleep(1000);
                        }
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                }
            };
            Thread removeThread = new Thread() {
                @Override
                public void run() {
                    try {
                        for (int i = 0; i < vector.size(); i++) {
                            vector.remove(i);
                            System.out.println("remove" + i);
                            Thread.sleep(1000);
                        }
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                }
            };
            printThread.start();
            removeThread.start();
            while (Thread.activeCount() > 10) ;
        }
    }
执行一段时间后，出现数组下标越界异常。

不要以为使用了同步集合就万事大吉，同步集合只能保证本身的操作是同步的，但是它所属的代码块不是同步的话，多线程情况下也会出问题。

改成这样就没问题了：

    public static void main(String[] args) {
        Vector<Integer> vector = new Vector<>();
        while (true) {
            for (int i = 0; i < 10; i++) {
                vector.add(i);
                System.out.println("add" + i);
            }
            Thread printThread = new Thread() {
                @Override
                public void run() {
                    try {
                        // vector内部用的也是用的它本身的对象作为锁，这边使用synchronized (vector)直接重入，避免获取锁的开销
                        synchronized (vector) {
                            for (int i = 0; i < vector.size(); i++) {
                                System.out.println(vector.get(i));
                                Thread.sleep(1000);
                            }
                        }
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                }
            };
            Thread removeThread = new Thread() {
                @Override
                public void run() {
                    try {
                        synchronized (vector) {
                            for (int i = 0; i < vector.size(); i++) {
                                vector.remove(i);
                                System.out.println("remove" + i);
                                Thread.sleep(1000);
                            }
                        }
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                }
            };
            printThread.start();
            removeThread.start();
            while (Thread.activeCount() > 10) ;
        }
    }
总之，Vector已经不推荐使用它了。想在多线程下使用集合，除了Vector，还有Collections.synchronizedList(List<T> list)，但是其同步效果和Vector差不多，也是锁住整章表。除此之外还有CopyOnWriteArrayList，这是以空间换时间的设计，每一个写的操作都会重新生成一个数组。如果想适应复杂场景和提升同步效率，建议还是自己用锁来实现比较好。
---------------------
【转载，仅作分享，侵删】
作者：况众文
原文：https://blog.csdn.net/u014294681/article/details/85323638
版权声明：本文为博主原创文章，转载请附上博文链接！

---

作者: 不二晨    时间: 2019-2-20 09:38
今天也要加油鸭

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2