Java集合源码分析之Vector

时间：2022-10-31 17:56:01

1. Vector简介

Java集合源码分析之Vector

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

Vector实现了可扩展的对象数组List
Vector实现了RandomAcess接口，支持索引，支持根据索引快速查找元素。RandomAccess
Vector实现了Cloneable接口，可以被克隆Cloneable
Vector实现了java.io.Serializable，支持序列化java.io.Serializable

2. 成员变量

//底层实现是数组，用于保存元素
protected Object[] elementData;
//底层数组的元素个数
protected int elementCount;
//数组增量
protected int capacityIncrement;
//序列化ID
private static final long serialVersionUID = -2767605614048989439L;
//集合最大容量为Integer最大值减8，减8的目的是：
//1.有的虚拟机需要空间保存集合的头信息
//2.防止请求的数组溢出虚拟机限制 
//最大为2的31次方-1
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

Vector类的底层实现是数组，用elementData数组保存元素，

3. 构造方法

public Vector(int initialCapacity, int capacityIncrement) {
    super();
    //增容为负数抛出异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    //创建一个数组容量为传入的值，赋值给elementData
    this.elementData = new Object[initialCapacity];
    //将增量赋值给集合
    this.capacityIncrement = capacityIncrement;
}

这个构造方法，指定了集合的初始容量，以及当要发生溢出时，集合自动增容时增加的容量大小。

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

仅指定集合初始容量构造方法。

public Vector() {
    this(10);
}

空参构造方法，集合初始容量为10。

public Vector(Collection<? extends E> c) {
    //将传入集合转换为数组赋给elementData
    elementData = c.toArray();
    //获取数组的长度赋给elementCount
    elementCount = elementData.length;
    //传入的集合时数组，调用Arraycpoy方法复制
    // defend against c.toArray (incorrectly) not returning Object[]
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}

构造方法参数为一个集合，将集合复制到Vector集合，

4. 查找方法

4.1 copyInto()复制集合到指定的数组中去
Public synchronized void copyInto(Object[] anArray) {
    //调用arraycopy方法复制集合到指定数组
    System.arraycopy(elementData, 0, anArray, 0, elementCount);
}
4.2 capacity()集合容量
public synchronized int capacity() {
    //返回数组长度
    return elementData.length;
}
4.3 size()集合长度
public synchronized int size() {
    //返回数组元素个数
    return elementCount;
}
4.4 isEmpty()集合是否为空
public synchronized boolean isEmpty() {
    //返回数组元素个数
    return elementCount == 0;
}
4.5 elements()枚举所有元素
public Enumeration<E> elements() {
    return new Enumeration<E>() {
        int count = 0;
        //是否还有元素
        public boolean hasMoreElements() {
            return count < elementCount;
        }
        //下个元素
        public E nextElement() {
            synchronized (Vector.this) {
                if (count < elementCount) {
                    return elementData(count++);
                }
            }
            throw new NoSuchElementException("Vector Enumeration");
        }
    };
}
4.6 contains()是否包含某个元素
public boolean contains(Object o) {
    //使用indexOf()方法 返回的是这个索引是否大于等于0 indexOf()没有找到元素会返回-1
    return indexOf(o, 0) >= 0;
}
4.7 indexOf()查找元素索引
public int indexOf(Object o) {
    //调用重载方法，从0索引开始查找元素
    return indexOf(o, 0);
}
public synchronized int indexOf(Object o, int index) {
    //如果查找元素为空
    if (o == null) {
        //for循环从指定index出开始查找为null的元素用==判断
        for (int i = index ; i < elementCount ; i++)
            if (elementData[i]==null)
                return i;
    } else {
        //for循环从指定index出开始查找equals()方法判断
        for (int i = index ; i < elementCount ; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    //没有找到返回-1
    return -1;
}
4.8 lastIndexOf()查找某个元素出现最后索引
public synchronized int lastIndexOf(Object o) {
    //调用lastIndexOf重载方法从elementCount-1位置处向前查找
    return lastIndexOf(o, elementCount-1);
}
public synchronized int lastIndexOf(Object o, int index) {
    //指定索引超出数组长度抛出异常
    if (index >= elementCount)
        throw new IndexOutOfBoundsException(index + " >= "+ elementCount);
    //如果查找元素为null
    if (o == null) {
        //for循环倒着遍历用==判断
        for (int i = index; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        //用equals()方法判断从后向前遍历
        for (int i = index; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    //没有找到返回-1
    return -1;
}
4.9 elementAt()返回指定位置元素
public synchronized E elementAt(int index) {
    //指定位置超出集合容量抛出异常
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
    }
    //elementData()方法实际就是数组查找return elementData[index]
    return elementData(index);
}
4.10 firstElement()返回第一个元素
public synchronized E firstElement() {
    //集合长度为0时抛出异常
    if (elementCount == 0) {
        throw new NoSuchElementException();
    }
    //返回数组elementData[0]
    return elementData(0);
}
4.11 get()获取指定位置的元素
public synchronized E get(int index) {
    //指定位置大于元素个数抛出异常
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    //返回数组指定位置的元素
    return elementData(index);
}
4.12 containsAll()是否包含集合
public synchronized boolean containsAll(Collection<?> c) {
    //父类的containsAll()方法对传入的集合经行遍历每个元素用contains()方法判断
    return super.containsAll(c);
}

5. 增删方法及相关方法

5.1 trimToSize()减少集合容量
public synchronized void trimToSize() {
    //对集合作出修改集合版本自加
    modCount++;
    //获取数组原长度
    int oldCapacity = elementData.length;
    //如果元素个数小于集合长度复制数组到长度为元素个数的数组中
    if (elementCount < oldCapacity) {
        elementData = Arrays.copyOf(elementData, elementCount);
    }
}
5.2 ensureCapacity()确认数组容量
public synchronized void ensureCapacity(int minCapacity) {
    if (minCapacity > 0) {
        //如果传入的最小容量大于零集合会修改所以版本号自加
        modCount++;
        //如果最小容量大于目前集合的数组的长度数组扩容到这个最小容量
        if (minCapacity > elementData.length)
            //grow()方法增容
            grow(minCapacity);
    }
}

传入的集合最小容量比数组实际的长度大，那么集合扩容到传入的最小容量。

5.3 grow()数组扩容
private Object[] grow(int minCapacity) {
    //调用数组工具类的copyOf()方法复制数组到新的指定的容量
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}
private Object[] grow() {
        //无参的增容方法容量加一
        return grow(elementCount + 1);
    }
5.4 newCapacity()新容量
private int newCapacity(int minCapacity) {
    //数组容量
    int oldCapacity = elementData.length;
    //capacityIncrement增容量大于0那么新容量就是旧容量加增容容量否则就为新容量为2倍旧容量
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    //增容后的容量比传入的最小容量小
    if (newCapacity - minCapacity <= 0) {
        //传入的最小容量小于零抛出异常
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //返回传入的最小容量
        return minCapacity;
    }
    //增容后的容量小于数组最大容量的话返回新的容量
    //否则返回hugeCapacity()判断容量的最大值
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}
private static int hugeCapacity(int minCapacity) {
    //传入的最小容量小于零抛出异常
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    //如果传入的容量大于数组最大容量返回Integer最大值否则返回数组最大容量
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}

当请求的数组容量大于MAX_ARRAY_SIZE时会得到Integer.MAX_VALUE也就是没有减去8的
Integer的最大值。可见数组最大容量是可以取到Integer.MAX_VALUE的，但是会不安全。

5.5 setSize()设定集合大小
public synchronized void setSize(int newSize) {
    //对集合作出修改集合版本自加
    modCount++;
    //如果指定的大小大于数组的长度，数组扩容到指定的长度
    if (newSize > elementData.length)
        grow(newSize);
    final Object[] es = elementData;
    //从指定容量位置开始到数组尾的元素都置为null
    for (int to = elementCount, i = newSize; i < to; i++)
        es[i] = null;
    elementCount = newSize;
}
5.6 setElementAt()修改指定位置元素
public synchronized void setElementAt(E obj, int index) {
    //如果指定位置超出集合抛出异常
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                 elementCount);
    }
    //数组指定位置修改为传入的obj
    elementData[index] = obj;
}
5.7 removeElementAt()移除指定位置元素
public synchronized void removeElementAt(int index) {
    //如果指定位置超出集合抛出异常
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                 elementCount);
    }
    //指定位置小于0抛出异常
    else if (index < 0) {
        throw new ArrayIndexOutOfBoundsException(index);
    }
    int j = elementCount - index - 1;
    //调用arraycopy方法复制index后的元素到前一个位置删除index处元素
    if (j > 0) {
        System.arraycopy(elementData, index + 1, elementData, index, j);
    }
    //对集合作出修改集合版本自加
    modCount++;
    //集合中元素个数减一
    elementCount--;
    //原最后一个元素置为null
    elementData[elementCount] = null; /* to let gc do its work */
}
5.8 insertElementAt()指定位置插入元素
public synchronized void insertElementAt(E obj, int index) {
    //指定位置超出集合抛出异常
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                                                 + " > " + elementCount);
    }
    //对集合作出修改集合版本自加
    modCount++;
    final int s = elementCount;
    Object[] elementData = this.elementData;
    //判断元素个数和数组长度是否相等如果相等数组增容
    if (s == elementData.length)
        elementData = grow();
    //调用arraycopy()方法复制元素空处指定的index处
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    //指定index处赋值obj
    elementData[index] = obj;
    //集合长度加1
    elementCount = s + 1;
}
5.9 addElement()向集合尾添加一个元素
public synchronized void addElement(E obj) {
    //对集合作出修改集合版本自加
    modCount++;
    //调用add方法再数组elementcount处添加传入元素obj
    add(obj, elementData, elementCount);
}
5.10 removeElement()删除指定元素
public synchronized boolean removeElement(Object obj) {
    //对集合作出修改集合版本自加
    modCount++;
    //找到元素所在的索引位置如果不存在为-1
    int i = indexOf(obj);
    //找到元素
    if (i >= 0) {
        //调用removeElementAt()方法删除指定索引位置的元素
        removeElementAt(i);
        return true;
    }
    return false;
}
5.11 移除所有元素removeAllElements()
public synchronized void removeAllElements() {
    final Object[] es = elementData;
    //遍历数组数组每个位置都置为null，并且元素个数置为0
    for (int to = elementCount, i = elementCount = 0; i < to; i++)
        es[i] = null;
    //对集合作出修改集合版本自加
    modCount++;
}
5.12 clear()移除所有元素
public void clear() {
    removeAllElements();
}
5.13 set()修改指定位置元素为指定的元素
public synchronized E set(int index, E element) {
    //指定索引超出元素个数范围抛出越界异常
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    //取得位置原元素
    E oldValue = elementData(index);
    //数组指定位置赋为指定元素
    elementData[index] = element;
    //返回原元素
    return oldValue;
}
5.14 add()在集合尾添加元素
public synchronized boolean add(E e) {
    //对集合作出修改集合版本自加
    modCount++;
    //调用add()重载方法
    add(e, elementData, elementCount);
    //修改成功返回true
    return true;
}
private void add(E e, Object[] elementData, int s) {
    //指定位置为数组尾数组增容
    if (s == elementData.length)
        elementData = grow();
    //数组指定位置赋值指定元素
    elementData[s] = e;
    //集合元素个数加1
    elementCount = s + 1;
}
5.15 remove()删除指定元素
public boolean remove(Object o) {
    //调用removeElement()方法删除指定元素
    return removeElement(o);
}
5.16 add()在指定位置添加元素
public void add(int index, E element) {
    //调用insertElementAt()方法在指定位置插入元素
    insertElementAt(element, index);
}
5.17 删除指定索引位置元素remove()
public synchronized E remove(int index) {
    //对集合作出修改集合版本自加
    modCount++;
    //如果指定索引超出集合元素个数抛出越界异常
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    //取得指定位置原元素
    E oldValue = elementData(index);
    //要复制移动的元素个数
    int numMoved = elementCount - index - 1;
    //复制元素个数大于0调用arraycopy()方法复制元素
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //数组原最后位置置为null并且元素个数自减
    elementData[--elementCount] = null; // Let gc do its work
    //返回原元素
    return oldValue;
}
5.18 addAll()添加指定集合中所有元素
    public boolean addAll(Collection<? extends E> c) {
        //传入集合转换数组
        Object[] a = c.toArray();
        //对集合作出修改集合版本自加
        modCount++;
        //传入数组的长度
        int numNew = a.length;
        //传入集合长度为0返回false
        if (numNew == 0)
            return false;
        synchronized (this) {
            Object[] elementData = this.elementData;
            final int s = elementCount;
            //如果要添加的集合的长度大于数组剩余长度 数组需要增容
            if (numNew > elementData.length - s)
                //数组增容传入集合的长度
                elementData = grow(s + numNew);
            //arraycopy()方法复制
            System.arraycopy(a, 0, elementData, s, numNew);
            //元素个数增加
            elementCount = s + numNew;
            return true;
        }
    }
5.19 removeAll()移除指定集合中的元素
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return bulkRemove(e -> c.contains(e));
}
5.20 retainAll()移除除了指定集合元素之外的元素
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return bulkRemove(e -> !c.contains(e));
}
5.21 addAll()在指定位置开始添加指定集合中的元素
public synchronized boolean addAll(int index, Collection<? extends E> c) {
    //指定索引位置小于0或者大于集合个数抛出越界异常
    if (index < 0 || index > elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    //指定集合转换为数组
    Object[] a = c.toArray();
    //对集合作出修改集合版本自加
    modCount++;
    //指定集合长度
    int numNew = a.length;
    //指定集合长度为0返回false
    if (numNew == 0)
        return false;
    Object[] elementData = this.elementData;
    final int s = elementCount;
    //原集合的数组剩余长度不够
    if (numNew > elementData.length - s)
        //数组扩容指定的集合长度
        elementData = grow(s + numNew);
    //复制数组个数
    int numMoved = s - index;
    if (numMoved > 0)
        //arraycopy()方法复制数组
        System.arraycopy(elementData, index,
                         elementData, index + numNew,
                         numMoved);
    System.arraycopy(a, 0, elementData, index, numNew);
    elementCount = s + numNew;
    return true;
}

6 总结

  1. Vector是线程安全的，许多方法都加入了synchronized同步语句，
  2. Vector底层是通过可变数组实现的和ArrayList类似，
  3. Vector可以设置扩容量capacityIncrement，
  4. Vector的无参构造函数默认初始数组容量为10，容量不够且没有设置扩容容量时会两倍扩容，最大容量为Integer.MAX_VALUE - 8，
  5. Vector支持枚举迭代方式Enumeration。
标签：

相关文章