Java集合中级——Vector源码解析

Java集合中级——Vector源码解析

Vector

• Vector是什么？
• 继承结构
• 域
• 构造函数
• 转为数组
• 截断
• 扩容
• 设置大小
• 获取数组容量、实际大小和判空
• 获取迭代器——Enumeration
• 是否包含和获取索引
• *** 作集合
• • 获取元素
  • 设置元素
  • 删除元素
  • 全清元素
  • 删除范围元素
  • 添加元素
  • 添加集合
• 克隆
• 序列化
• 获取子串
• 排序
• 获取迭代器——iterator和listIterator
• • 迭代器——Itr内部类
  • 迭代器——ListItr内部类
• 调用父类的方法
• Java8新方法（不讲）
• • forEach
  • removeIf
  • replaceAll
  • spliterator()和VectorSpliterator类

Vector是什么？

Vector是基于数组实现的随机访问的同步的List结构，其public方法都是加锁的（加锁后不再需要临时变量保持原子性）

继承结构

继承了AbstractList，实现了List，并实现了三个标记接口RandomAccess、Cloneable、Serializable

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

域

序列版本号、数组缓冲、实际大小，增长容量，还有从父类继承的modCount

private static final long serialVersionUID = -2767605614048989439L;
protected Object[] elementData;
protected int elementCount;
protected int capacityIncrement;

构造函数

• Vector()创建容量为10的数组
• Vector(int)创建指定容量数组
• Vector(int, int)创建指定容量和指定增长容量的数组
• Vector(Collection)将集合转为数组，若不是Object[]类型则转换，保存其实际大小

public Vector() {
    this(10);
}
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}
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(Collection c) {
    elementData = c.toArray();
    elementCount = elementData.length;
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}

转为数组

• copyInto()将elementData从0开始拷贝elementCount个元素到anArray（anArray[elementCount]后面可能还有元素）
• toArray()调用Arrays.copyOf将elementData缩减返回

toArray(T)具体为

• 若a.length < elementCount，则将elementData缩减并转为T[]类型返回
• 若a.length = elementCount，则将elementData从0开始拷贝elementCount个元素到a，返回a（数组相等）
• 若a.length > elementCount，则将elementData从0开始拷贝elementCount个元素到a，a[size]=null，返回a（null后面可能还有元素）

public synchronized void copyInto(Object[] anArray) {
    System.arraycopy(elementData, 0, anArray, 0, elementCount);
}
public synchronized Object[] toArray() {
    return Arrays.copyOf(elementData, elementCount);
}
public synchronized  T[] toArray(T[] a) {
    if (a.length < elementCount)
        return (T[]) Arrays.copyOf(elementData, elementCount, a.getClass());
    System.arraycopy(elementData, 0, a, 0, elementCount);
    if (a.length > elementCount)
        a[elementCount] = null;
    return a;
}

截断

增加修改次数，如果实际容量小于数组容量，则按实际大小缩减

public synchronized void trimToSize() {
    modCount++;
    int oldCapacity = elementData.length;
    if (elementCount < oldCapacity) {
        elementData = Arrays.copyOf(elementData, elementCount);
    }
}

扩容

ensureCapacity()供外部扩容，判断传入的扩容大小是否大于0，若是则增加修改次数，调用ensureCapacityHelper()

ensureCapacityHelper()判断传入的扩容大小是否大于当前数组大小，大于则调用grow

grow()方法具体为

• 若增长容量大于0，则新容量为oldCapacity+capacityIncrement，否则为旧容量的两倍
• 若新容量小于传入的扩容大小，则新容量为扩容大小
• 若新容量（或minCapacity大于）大于MAX_ARRAY_SIZE，则新容量为hugeCapacity()
• 最后将elementData扩容到新容量

hugeCapacity()具体为

• 判断是否溢出（add方法会传递elementCount+1，若此时已是Integer.MAX_VALUE则会溢出）
• 若minCapacity > MAX_ARRAY_SIZE，新容量为Integer.MAX_VALUE，否则为MAX_ARRAY_SIZE

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 static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
    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);
}
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) 
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

设置大小

增加修改次数，若newSize大于实际大小，则扩容，否则置空newSize后续元素，让实际大小等于newSize

public synchronized void setSize(int newSize) {
    modCount++;
    if (newSize > elementCount) {
        ensureCapacityHelper(newSize);
    } else {
        for (int i = newSize ; i < elementCount ; i++) {
            elementData[i] = null;
        }
    }
    elementCount = newSize;
}

获取数组容量、实际大小和判空

public synchronized int capacity() {
    return elementData.length;
}
public synchronized int size() {
    return elementCount;
}
public synchronized boolean isEmpty() {
    return elementCount == 0;
}

获取迭代器——Enumeration

• hasMoreElements()判断遍历次数是否超过elementCount
• nextElement()判断遍历次数是否超过elementCount，不超过则返回数据

public Enumeration elements() {
    return new Enumeration() {
        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");
        }
    };
}

是否包含和获取索引

• contains判断下标是否大于0
• indexOf从头或指定位置遍历判断元素是否存在，若存在返回下标，不存在返回-1
• lastIndexOf从尾或指定位置遍历判断元素是否存在，若存在返回下标，不存在返回-1

public boolean contains(Object o) {
    return indexOf(o, 0) >= 0;
}
public int indexOf(Object o) {
    return indexOf(o, 0);
}
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;
}
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[i]==null)
                return i;
    } else {
        for (int i = index; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

*** 作集合 获取元素

• elementAt() == get()获取指定位置元素
• firstElement()和lastElement()获取头尾元素

E elementData(int index) {
    return (E) elementData[index];
}

public synchronized E elementAt(int index) {
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
    }
    return elementData(index);
}
public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    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);
}

设置元素

setElementAt()和set()将元素设置到指定位置（前者返回void，后者返回旧元素）

public synchronized void setElementAt(E obj, int index) {
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +elementCount);
    }
    elementData[index] = obj;
}

public synchronized E set(int index, E element) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

删除元素

removeElementAt()和remove(int)删除指定位置元素（前者返回void，后者返回旧元素），具体为

• 增加修改次数，判越界
• 获取后面元素的数量，若大于0则后面依次往前覆盖，不大于0则是最后一个
• 大小减1，最后的元素置空

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 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;
    return oldValue;
}

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

public synchronized boolean removeAll(Collection c) {
    return super.removeAll(c);
}

• removeElement() == remove(Object)增加修改次数，找到Object对应的index并调用removeElementAt()删除

全清元素

removeAllElements() == clear()，增加修改次数，遍历数组置空，大小置0

public synchronized void removeAllElements() {
    modCount++;
    for (int i = 0; i < elementCount; i++)
        elementData[i] = null;
    elementCount = 0;
}
 public void clear() {
     removeAllElements();
 }

删除范围元素

• 增加修改次数
• 获取toIndex后面元素的个数，将toIndex后面的元素覆盖到fromIndex
• 获取新数组大小
• 将新数组后面的元素置null

protected synchronized void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = elementCount - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex,numMoved);
    int newElementCount = elementCount - (toIndex-fromIndex);
    while (elementCount != newElementCount)
        elementData[--elementCount] = null;
}

添加元素

• insertElementAt() == add(int, E)在指定位置添加元素，增加修改次数，判越界，是否扩容，index后面的元素依次往后移空出index，给index位置赋值，大小加1
• addElement()和add(E)默认添加到末尾（前者返回void，后者返回boolean），增加修改次数，判断是否扩容，大小加1并末尾赋值

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++;
}
public void add(int index, E element) {
    insertElementAt(element, index);
}

public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

添加集合

addAll(Collection)将集合转为数组a

• 增加修改记录，判断是否扩容
• 将集合转为数组a，从0开始赋值a.length个元素到elementData[elementCount]后面
• size+a.length，集合不为空则添加成功

public synchronized boolean addAll(Collection 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 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)
        System.arraycopy(elementData, index, elementData, index + numNew,numMoved);
    System.arraycopy(a, 0, elementData, index, numNew);
    elementCount += numNew;
    return numNew != 0;
}

addAll(int, Collection)将集合转为数组a添加到指定位置

• 增加修改记录，判断是否溢出、是否扩容
• 获取index后面元素的个数numMoved，若其大于0（不大于0刚好是最后一个）则后面移动numMoved个位置，空出a.length个位置
• 将数组a填充到index位置
• size+a.length，集合不为空则则添加成功

克隆

浅拷贝，只拷贝数组地址，不拷贝元素

public synchronized Object clone() {
    try {
        Vector v = (Vector) super.clone();
        v.elementData = Arrays.copyOf(elementData, elementCount);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}

序列化

怎么没有反序列化

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
    final java.io.ObjectOutputStream.PutField fields = s.putFields();
    final Object[] data;
    synchronized (this) {
        fields.put("capacityIncrement", capacityIncrement);
        fields.put("elementCount", elementCount);
        data = elementData.clone();
    }
    fields.put("elementData", data);
    s.writeFields();
}

获取子串

详情请看Collections

public synchronized List subList(int fromIndex, int toIndex) {
    return Collections.synchronizedList(super.subList(fromIndex, toIndex),this);
}

排序

public synchronized void sort(Comparator c) {
    final int expectedModCount = modCount;
    Arrays.sort((E[]) elementData, 0, elementCount, c);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

获取迭代器——iterator和listIterator

• iterator()返回从实现Iterator的迭代器Itr
• listIterator()返回实现ListIterator且位置为0的迭代器ListItr
• listIterator(int)返回指定位置的迭代器ListItr

public synchronized Iterator iterator() {
    return new Itr();
}

public synchronized ListIterator listIterator() {
    return new ListItr(0);
}

public synchronized ListIterator listIterator(int index) {
    if (index < 0 || index > elementCount)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}

迭代器——Itr内部类

• 域limit存储elementCount，避免在迭代过程中并发修改导致elementCount被改变（andoird代码）
• hasNext()判断游标是否小于limit
• forEachRemaining()不讲

next()可连续调用，调用前可不用hasNext()，具体为

• 加锁，判断集合是否已被并发修改
• 再判断游标是否已到元素末尾（避免连续调用next）
• 根据游标取出元素（用i保持原子性，避免cursor被修改）
• 将游标加1，记录越过的元素位置

private class Itr implements Iterator {

    protected int limit = Vector.this.elementCount;
    int cursor;  
    int lastRet = -1; 
    int expectedModCount = modCount;
    public boolean hasNext() {
        return cursor < limit;
    }
    public E next() {
        synchronized (Vector.this) {
            checkForComodification();
            int i = cursor;
            if (i >= limit)
                throw new NoSuchElementException();
            cursor = i + 1;
            return elementData(lastRet = i);
        }
    }
    
    public void forEachRemaining(Consumer action) {
        Objects.requireNonNull(action);
        synchronized (Vector.this) {
            final int size = limit;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final E[] elementData = (E[]) Vector.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                action.accept(elementData[i++]);
            }
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }
    }
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
    
    public void remove() {
        if (lastRet == -1)
            throw new IllegalStateException();
        synchronized (Vector.this) {
            checkForComodification();
            Vector.this.remove(lastRet);
            expectedModCount = modCount;
            limit--;
        }
        cursor = lastRet;
        lastRet = -1;
    }
}

remove()具体为

• 先判断是否调用了next()
• 加锁，再判断是否已被并发修改
• 调用外部类的remove()移除上一个越过的元素
• 同步修改次数，大小减1
• 删除后数组移动，游标回退到所移动元素的左边
• lastRet = -1避免连续调用remove()

迭代器——ListItr内部类

ListItr 继承了 Itr（向后遍历） 且实现了 ListIterator（向前遍历）

• 构造函数获取指定位置的迭代器（从头开始则为0）
• hasPrevious()判断当前是否到了位置0
• nextIndex()和previousIndex()返回当前游标和上一个游标

previous()具体为

• 加锁，判断集合是否已被并发修改
• 再判断是否到元素开头（避免连续调用previous）
• 根据游标取出元素（用i保持原子性，避免cursor被修改）
• 将游标减1，记录越过的元素位置

final class ListItr extends Itr implements ListIterator {
    ListItr(int index) {
        super();
        cursor = index;
    }
    public boolean hasPrevious() {
        return cursor != 0;
    }
    public int nextIndex() {
        return cursor;
    }
    public int previousIndex() {
        return cursor - 1;
    }
    public E previous() {
        synchronized (Vector.this) {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            cursor = i;
            return elementData(lastRet = i);
        }
    }
    public void set(E e) {
        if (lastRet == -1)
            throw new IllegalStateException();
        synchronized (Vector.this) {
            checkForComodification();
            Vector.this.set(lastRet, e);
        }
    }
    public void add(E e) {
        int i = cursor;
        synchronized (Vector.this) {
            checkForComodification();
            Vector.this.add(i, e);
            expectedModCount = modCount;
            limit++;
        }
        cursor = i + 1;
        lastRet = -1;
    }
}

set()具体为

• 先判断是否调用了next()或previous()
• 加锁，判断是否已被并发修改
• 调用外部类的set覆盖上一个越过的元素（未lastRet = -1，说明可重复set进行覆盖）

add()具体为

• 先判断是否已被并发修改
• 用外部类的add()在游标处添加元素（用i保持原子性，避免add时cursor被修改）
• 记录修改次数，大小加1
• 游标+1，lastRet = -1避免调用set()、remove()，但可连续调用add()，游标加1

————————————————————————————————

调用父类的方法

以下调用了AbstractCollection的方法

public synchronized boolean containsAll(Collection c) {
    return super.containsAll(c);
}
public synchronized boolean retainAll(Collection c) {
    return super.retainAll(c);
}
public synchronized boolean equals(Object o) {
    return super.equals(o);
}
public synchronized int hashCode() {
    return super.hashCode();
}
public synchronized String toString() {
    return super.toString();
}

Java8新方法（不讲） forEach

public synchronized void forEach(Consumer action) {
    Objects.requireNonNull(action);
    final int expectedModCount = modCount;
    @SuppressWarnings("unchecked")
    final E[] elementData = (E[]) this.elementData;
    final int elementCount = this.elementCount;
    for (int i=0; modCount == expectedModCount && i < elementCount; i++) {
        action.accept(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

removeIf

public synchronized boolean removeIf(Predicate filter) {
    Objects.requireNonNull(filter);
    int removeCount = 0;
    final int size = elementCount;
    final BitSet removeSet = new BitSet(size);
    final int expectedModCount = modCount;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        final E element = (E) elementData[i];
        if (filter.test(element)) {
            removeSet.set(i);
            removeCount++;
        }
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    final boolean anyToRemove = removeCount > 0;
    if (anyToRemove) {
        final int newSize = size - removeCount;
        for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
            i = removeSet.nextClearBit(i);
            elementData[j] = elementData[i];
        }
        for (int k=newSize; k < size; k++) {
            elementData[k] = null;  
        }
        elementCount = newSize;
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }
    return anyToRemove;
}

replaceAll

public synchronized void replaceAll(UnaryOperator operator) {
    Objects.requireNonNull(operator);
    final int expectedModCount = modCount;
    final int size = elementCount;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        elementData[i] = operator.apply((E) elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

spliterator()和VectorSpliterator类

public Spliterator spliterator() {
    return new VectorSpliterator<>(this, null, 0, -1, 0);
}

static final class VectorSpliterator implements Spliterator {
    private final Vector list;
    private Object[] array;
    private int index; // current index, modified on advance/split
    private int fence; // -1 until used; then one past last index
    private int expectedModCount; // initialized when fence set
    
    VectorSpliterator(Vector list, Object[] array, int origin, int fence,
                      int expectedModCount) {
        this.list = list;
        this.array = array;
        this.index = origin;
        this.fence = fence;
        this.expectedModCount = expectedModCount;
    }
    private int getFence() { // initialize on first use
        int hi;
        if ((hi = fence) < 0) {
            synchronized(list) {
                array = list.elementData;
                expectedModCount = list.modCount;
                hi = fence = list.elementCount;
            }
        }
        return hi;
    }
    public Spliterator trySplit() {
        int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
        return (lo >= mid) ? null :
            new VectorSpliterator(list, array, lo, index = mid,
                                     expectedModCount);
    }
    @SuppressWarnings("unchecked")
    public boolean tryAdvance(Consumer action) {
        int i;
        if (action == null)
            throw new NullPointerException();
        if (getFence() > (i = index)) {
            index = i + 1;
            action.accept((E)array[i]);
            if (list.modCount != expectedModCount)
                throw new ConcurrentModificationException();
            return true;
        }
        return false;
    }
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer action) {
        int i, hi; // hoist accesses and checks from loop
        Vector lst; Object[] a;
        if (action == null)
            throw new NullPointerException();
        if ((lst = list) != null) {
            if ((hi = fence) < 0) {
                synchronized(lst) {
                    expectedModCount = lst.modCount;
                    a = array = lst.elementData;
                    hi = fence = lst.elementCount;
                }
            }
            else
                a = array;
            if (a != null && (i = index) >= 0 && (index = hi) <= a.length) {
                while (i < hi)
                    action.accept((E) a[i++]);
                if (lst.modCount == expectedModCount)
                    return;
            }
        }
        throw new ConcurrentModificationException();
    }
    public long estimateSize() {
        return (long) (getFence() - index);
    }
    public int characteristics() {
        return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
    }
}