注意:本文基于JDK1.8进行记录。
1 Vector
1.1 简介
不常用的集合,和ArrayList类似,允许任何符合规则的元素插入,包括null和重复元素。
底层是数组结构,提供了索引机制,查找效率高,增删效率低。
线程安全,使用了synchronized关键字。
1.2 扩容机制
扩容机制和ArrayList类似,初始容量默认为10,负载因子是1,表示当插入元素后个数超出原有长度时会进行扩增,扩容增量是默认为原容量,所以扩增后容量为2倍,可使用方法手动扩容和缩减。
最好指定初始容量值和增量,避免过多的进行扩容操作而浪费时间和效率。
1.3 方法说明
1.3.1 构造方法
1 // 空参构造器,返回默认容量为10的集合。 2 public Vector(); 3 // 指定长度的构造器,默认增量为0。 4 public Vector(int initialCapacity); 5 // 指定长度和增量的构造器,默认增量为0。 6 public Vector(int initialCapacity, int capacityIncrement); 7 // 传入了一个集合的构造器,如果集合长度为0,返回容量为0的集合。 8 public Vector(Collection<? extends E> c);
1.3.2 常用方法
1 // 获取指定下标的元素。 2 public synchronized E get(int index); 3 // 设置指定下标的指定元素,并返回旧元素。 4 public synchronized E set(int index, E element); 5 // 添加元素,并返回是否成功。 6 public synchronized boolean add(E e); 7 // 在指定位置添加指定元素。 8 public void add(int index, E element); 9 // 删除指定位置的元素,并返回删除的元素。 10 public synchronized E remove(int index); 11 // 删除元素,并返回是否成功。 12 public boolean remove(Object o);
1.4 源码分析
1.4.1 属性
1 // 数组。 2 protected Object[] elementData; 3 // 元素个数。 4 protected int elementCount; 5 // 扩容增量 6 protected int capacityIncrement;
1.4.2 构造方法
1 // 空参构造器,返回默认容量为10的集合。 2 public Vector() { 3 this(10); 4 } 5 // 指定长度的构造器,默认增量为0。 6 public Vector(int initialCapacity) { 7 this(initialCapacity, 0); 8 } 9 // 指定长度和增量的构造器,默认增量为0。 10 public Vector(int initialCapacity, int capacityIncrement) { 11 super(); 12 if (initialCapacity < 0) 13 throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity); 14 this.elementData = new Object[initialCapacity]; 15 this.capacityIncrement = capacityIncrement; 16 } 17 // 传入了一个集合的构造器,如果集合长度为0,返回容量为0的集合。 18 public Vector(Collection<? extends E> c) { 19 elementData = c.toArray(); 20 elementCount = elementData.length; 21 // Object[]数组里的类型不一定都是Object类型的,有可能是Object的子类,所以要判断一下。 22 if (elementData.getClass() != Object[].class) 23 elementData = Arrays.copyOf(elementData, elementCount, Object[].class); 24 }
1.4.3 常用方法
1 // 获取指定下标的元素。 2 public synchronized E get(int index) { 3 // 检查指定下标是否越界。 4 if (index >= elementCount) 5 throw new ArrayIndexOutOfBoundsException(index); 6 // 返回指定下标的元素。 7 return elementData(index); 8 } 9 // 设置指定下标的指定元素,并返回旧元素。 10 public synchronized E set(int index, E element) { 11 // 检查指定下标是否越界。 12 if (index >= elementCount) 13 throw new ArrayIndexOutOfBoundsException(index); 14 // 设置指定元素并返回旧元素。 15 E oldValue = elementData(index); 16 elementData[index] = element; 17 return oldValue; 18 } 19 // 添加元素,并返回是否成功。 20 public synchronized boolean add(E e) { 21 // 操作数自增。 22 modCount++; 23 // 扩容。 24 ensureCapacityHelper(elementCount + 1); 25 // 元素个数增加并设置指定元素。 26 elementData[elementCount++] = e; 27 // 返回成功。 28 return true; 29 } 30 // 在指定位置添加指定元素。 31 public void add(int index, E element) { 32 insertElementAt(element, index); 33 } 34 // 删除指定位置的元素,并返回删除的元素。 35 public synchronized E remove(int index) { 36 // 操作数自增。 37 modCount++; 38 // 检查指定下标是否越界。 39 if (index >= elementCount) 40 throw new ArrayIndexOutOfBoundsException(index); 41 // 获取指定下标的元素。 42 E oldValue = elementData(index); 43 // 需要移动的元素个数。 44 int numMoved = elementCount - index - 1; 45 if (numMoved > 0) 46 System.arraycopy(elementData, index+1, elementData, index, numMoved); 47 // 将最后一个元素设置为null并减少容量大小。 48 elementData[--elementCount] = null; 49 // 返回指定下标的元素。 50 return oldValue; 51 } 52 // 删除元素,并返回是否成功。 53 public boolean remove(Object o) { 54 return removeElement(o); 55 }
1.4.4 扩容方法
1 // 对集合进行扩容。 2 public synchronized void ensureCapacity(int minCapacity) { 3 // 如果指定容量大于扩充值,则进行扩容。 4 if (minCapacity > 0) { 5 // 操作数自增。 6 modCount++; 7 ensureCapacityHelper(minCapacity); 8 } 9 } 10 // 对集合进行扩容。 11 private void ensureCapacityHelper(int minCapacity) { 12 // 如果最小值大于数组长度,则进行扩容。 13 if (minCapacity - elementData.length > 0) 14 grow(minCapacity); 15 } 16 // 数组作为一个对象,需要一定的内存存储对象头信息,对象头信息最大占用内存不可超过8字节。 17 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 18 // 扩容计算。 19 private void grow(int minCapacity) { 20 // 获取原容量大小。 21 int oldCapacity = elementData.length; 22 // 如果增量大于0,则使用增量,否则使用原容量作为增量,最后加上原容量作为新容量。 23 int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); 24 // 如果扩容后小于最小值,则设置容量为最小值。 25 if (newCapacity - minCapacity < 0) 26 newCapacity = minCapacity; 27 // 如果扩容后大于最大值,则进一步设置容量。 28 if (newCapacity - MAX_ARRAY_SIZE > 0) 29 newCapacity = hugeCapacity(minCapacity); 30 // 复制数组。 31 elementData = Arrays.copyOf(elementData, newCapacity); 32 } 33 // 扩容后容量过大的处理方法。 34 private static int hugeCapacity(int minCapacity) { 35 // 如果最小值小于零,则表示溢出,抛出内存溢出异常。 36 if (minCapacity < 0) 37 throw new OutOfMemoryError(); 38 // 如果扩容后的值大于最大值,则使用Integer的最大值,否则就使用最大值。 39 return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; 40 }
2 Stack
2.1 简介
不常用的集合,继承自Vector,允许任何符合规则的元素插入,包括null和重复元素。
同Vector类似,底层是数组结构,但通过对Vector的扩展,将数组结构倒置形成堆栈结构,使用典型的后进先出操作方式。
线程安全,使用了synchronized关键字。
2.2 扩容机制
同Vector。
2.3 方法说明
2.3.1 构造方法
1 public Stack();
2.3.2 常用方法
1 // 判断是否为空。 2 public boolean empty(); 3 // 入栈,添加到栈顶。 4 public E push(E item); 5 // 出栈,查看并删除栈顶元素。 6 public synchronized E pop(); 7 // 查看栈顶元素。 8 public synchronized E peek(); 9 // 查找元素,返回栈中首次出现下标。 10 public synchronized int search(Object o);
2.4 源码分析
2.4.1 构造方法
1 public Stack() { 2 }
2.4.2 常用方法
1 // 判断是否为空。 2 public boolean empty() { 3 // 通过Vector的size()方法判断。 4 return size() == 0; 5 } 6 // 入栈,添加到栈顶。 7 public E push(E item) { 8 // 实际添加到数组尾部。 9 addElement(item); 10 return item; 11 } 12 // 出栈,查看并删除栈顶元素。 13 public synchronized E pop() { 14 E obj; 15 int len = size(); 16 // 实际查看数组尾部元素。 17 obj = peek(); 18 // 实际删除数组尾部元素。 19 removeElementAt(len - 1); 20 return obj; 21 } 22 // 查看栈顶元素。 23 public synchronized E peek() { 24 int len = size(); 25 if (len == 0) 26 throw new EmptyStackException(); 27 // 实际查看数组尾部元素。 28 return elementAt(len - 1); 29 } 30 // 查找元素,返回栈中首次出现下标。 31 public synchronized int search(Object o) { 32 // 实际查看元素在数组最后出现位置。 33 int i = lastIndexOf(o); 34 if (i >= 0) { 35 // 转换为栈中位置。 36 return size() - i; 37 } 38 return -1; 39 }