007Java集合003详解Vector、Stack

注意:本文基于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 }

 

上一篇:【003】Python 注释


下一篇:java全栈系列之JavaSE--IDEA开发工具的安装以及基础使用003