Java 集合源码探究之Vector 底层实现、扩容、线程安全

Vector

类图

得到的信息

• 实现 Cloneable 接口， 可以拷贝
• 实现RandomAccess接口， 可以随机访问
• 实现Serialzable 接口， 可以序列化
• 实现List 以及继承AbstractList类

类信息

public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { protected Object[] elementData; protected int elementCount; protected int capacityIncrement;} 

• 底层使用对象数组来实现存储
• 存储元素数量、当前的容量
• 访问修饰符为 protected
• capacityIncrement
  • 向量容量自动增加的量，当其大小大于其容量时递增。如果容量增量小于或等于零，向量的每一次增长都是原来的两倍。

	类内部	本包	子类	外部类
public
protected
default
private

构造函数

 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() { this(10); } public Vector(int initialCapacity) { this(initialCapacity, 0); } 

添加元素

• 修改 修改的次数
• 进行判断
• 添加元素

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

扩容时候

ensureCapacityHelper(elementCount + 1);

• minCapacity 当前元素数量+ 1 的值， 用来判断添加这个元素是否需要扩容
• 如果需要扩容就调用 grow(minCapacity); 方法来扩容

 private void ensureCapacityHelper(int minCapacity) { // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } 

grow(minCapacity);

• minCapacity 当前元素数量+ 1 的值， 用来判断添加这个元素是否需要扩容
• MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
• 指定扩容大小
  • 按照扩容大小扩容
• 没指定扩容大小
  • 扩容原有大小
• 如果扩容后的大小还不满足当前要存放的数量
  • 就直接扩容到当前要存放的数量
• 要扩容的大下已经比 Integer.MAX_VALUE - 8; 还要大的时候
  • 使用 hugeCapacity(minCapacity);
• 最后得到扩容的大小之后 使用 Arrays.copyOf(elementData, newCapacity); 来扩容
  • 最后还是使用的这个底层方法来实现复制元素达到扩容目的
  • System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));

 private void grow(int minCapacity) { // overflow-conscious code 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); } 

hugeCapacity

• minCapacity 当前元素数量+ 1 的值， 用来判断添加这个元素是否需要扩容
• MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

minCapacity 的大小如果比 MAX_ARRAY_SIZE还要大的话， 就直接扩容为 Integer.MAX_VALUE 的最大值！

 private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } 

扩容总结

• 扩容大小
  • 如果指定扩容大小， 就使用这个大小来扩容元素
  • 如果没指定大小， 就按照原有大小的2 倍来扩容
  • 如果扩容后还不满足当前要存放的数量， 就直接扩容到当前容量
• 扩容大小和 int 最大值 - 8 比较
  • 根据比较结果， 判断是否扩容为int的最大值

不扩容时候

• ensureCapacityHelper(elementCount + 1); 是个无返回值的函数， 不扩容就直接跳过了
• 直接在数组中添加该元素
  • elementCount 会自增

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

设置大小

如果当前的新大小 已经超过了当前元素的数量就是用扩容！否则的话就会把当前新位置之后的元素全部置为 空，然后更新元素的数量。

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

elements

elements()

会增加一种vector的数据访问的方法， 使用elements类。它在内部定义了一个 计数器 count ， 每次调用nextElement 就相当于从 0 开始逐个返回 vector里面的元素， 并且使用 count 和 elementCount 对比来判断vector中是否还含有元素。

 public Enumeration<E> elements() { return new Enumeration<E>() { int count = 0; public boolean hasMoreElements() { return count < elementCount; } public E () { synchronized (Vector.this) { if (count < elementCount) { return elementData(count++); } } throw new NoSuchElementException("Vector Enumeration"); } }; } /**
**这个接口是有两个方法
1、得到下一个元素
2、是否还有元素
**/ public interface Enumeration<E> { boolean hasMoreElements(); E nextElement(); } 

指定位置添加元素

• 先判断 这个位置是否超过元素的数量
  • 抛出异常
• 判断是否需要扩容
• 拷贝数组
• 在指定的位置添加元素

 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++; } 

删除元素

• 得到这个位置的元素
• 得到需要移动元素的个数
  • int numMoved = elementCount - index - 1;
  • elementCount = 5
  • index = 3
  • numMoved = 1只需要移动最后一个元素即可
• 开始数组的复制
• 把尾部位置制空
• 返回这个位置的元素

 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; // Let gc do its work return oldValue; } E elementData(int index) { return (E) elementData[index]; } 

判断是否为空

 public synchronized boolean isEmpty() { return elementCount == 0; } 

得到元素的索引

得到首次出现的位置

通过遍历逐一比较的方式来获得元素的索引。

• o 要判断元素的值

• index 从什么位置开是判断

• 如果要比较元素的值为 null的话

  • 使用 == 来判断是否相等

• 如果要比较元素的值不为 null 的话

  • 使用 equals 来判断是否相等

 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, 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; } 

总结

• 底层的实现和arraylist很类似
  • 使用数组
• 初始化的时候可以指定扩容大小
  • 按照扩容大小扩容
  • 扩容2 倍
• 方法被 synchronized修饰
  • 是线程安全的集合类
• 判断相等的时候使用 equals

本文地址：https://blog.csdn.net/qq_41291945/article/details/108868449