Java集合（三）CopyOnWriteArrayList、Vector、Stack
本系列文章：
Java集合（一）集合框架概述
Java集合（二）List、ArrayList、LinkedList
Java集合（三）CopyOnWriteArrayList、Vector、Stack
Java集合（四）Map、HashMap
Java集合（五）LinkedHashMap、TreeMap
Java集合（六）Hashtable、ConcurrentHashMap
Java集合（七）Set、HashSet、LinkedHashSet、TreeSet
Java集合（八）BlockingQueue、ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue、DelayQueue
【CopyOnWriteArrayList】
一、CopyOnWriteArrayList介绍
在很多应用场景中，读操作可能会远远大于写操作。由于读操作根本不会修改原有的数据，因此对于每次读取都进行加锁其实是一种资源浪费。我们可以允许多个线程同时访问List 的内部数据，毕竟读取操作是安全的。CopyOnWriteArrayList恰恰符合这种要求。
CopyOnWriteArrayList位于JUC包下，可以说是读写分离、以空间换时间版的ArrayList。其继承关系和ArrayList也是一致的：
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
CopyOnWriteArrayList是一个线程安全、并且在读操作时无锁的ArrayList，其底层实现也是数组。不止读操作时无锁，写入也不会阻塞读取操作。只有写入和写入之间需要进行同步等待。
CopyOnWriteArrayList 类的所有可变操作（add、set等）都是通过创建底层数组的新副本来实现的。当List需要被修改的时候，并不修改原有内容，而是对原有数据进行一次复制，副本用来写，原来的数据用来读。写完之后，再将修改完的副本替换原来的数据，这样就可以保证写操作不会影响读操作。
1.1 CopyOnWriteArrayList的特点*
- 1、线程安全
CopyOnWriteArrayList所有写操作，都是通过对底层数组进行一次新的复制来实现，是线程安全的。 - 2、适合读操作大于写操作的场景
CopyOnWriteArrayList适合使用在读操作远远大于写操作的场景里，比如缓存。CopyOnWriteArrayList不存在扩容的概念，每次写操作都要复制一个副本，在副本的基础上修改后改变原来的引用。CopyOnWriteArrayList中写操作需要大面积复制数组，所以性能差。 - 3、内存消耗较大
CopyOnWriteArrayList虽然读多写少的场景，不过要慎用 ，因为当CopyOnWriteArrayList存放的数据比较多时，每次add/set都要重新复制数组，这个代价实在太高。 - 4、数据一致性
CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。写和读分别作用在新老不同容器上，在写操作执行过程中，读不会阻塞但读取到的却是老容器的数据。 - 5、读写分离，效率高
采用读写分离方式，读的效率非常高。CopyOnWriteArrayList的迭代器是基于创建时的数据快照的，故数组的增删改不会影响到迭代器。 - 6、支持随机读
由于CopyOnWriteArrayList底层实现数组，数据存在连续的内存上，因此支持随机读。
1.2 CopyOnWriteArrayList的使用
- 1、构造方法
可以构建空对象，也可以根据数组、集合等对象来构建对象。
//构造一个空数组
public CopyOnWriteArrayList()
//将指定集合中的元素copy到数组中
public CopyOnWriteArrayList(Collection<? extends E> c)
//将指定数组中的元素copy到数组中
public CopyOnWriteArrayList(E[] toCopyIn)
- 2、添加元素
添加元素的方式和ArrayList类似，默认添加元素在数组尾部，也可以在指定位置添加。
//将指定的元素列表的结束
public boolean add(E e)
//在列表中指定的位置上插入指定的元素
public void add(int index, E element)
//追加指定集合的所有元素到这个列表的末尾
public boolean addAll(Collection<? extends E> c)
//将指定集合中的所有元素插入到该列表中，从指定位置开始
public boolean addAll(int index, Collection<? extends E> c)
- 3、判断是否包含某个元素
public boolean contains(Object o)
- 4、获取制定位置的元素
public E get(int index)
- 5、返回指定元素的索引
//返回此列表中指定元素的第一个出现的索引
public int indexOf(Object o)
//从指定位置搜索，返回此列表中的第一个出现的指定元素的索引
public int indexOf(E e, int index)
- 6、删除元素
//根据下标删除元素
public E remove(int index)
//删除列表中首次出现的元素
public boolean remove(Object o)
- 7、清空
public void clear()
二、从源码理解CopyOnWriteArrayList
看CopyOnWriteArrayList源码，可以从两点来把握：
- 1、动态数组
CopyOnWriteArrayList内部有个volatile数组。在添加、修改、删除数据时，都会新建一个数组，并将原数组中的元素拷贝到新数组中，然后在新数组中更新，最后再将“volatile数组”引用指向新数组。
CopyOnWriteArrayList就是通过这种方式实现的动态数组；不过正由于它在添加、修改、删除数据时，都会新建数组，所以涉及到修改数据的操作，CopyOnWriteArrayList效率很低；但只是进行遍历查找的话，效率比较高（与ArrayList相似）。 - 2、线程安全
线程安全是通过volatile和互斥锁来实现的。
CopyOnWriteArrayList的底层实现是volatile数组。volatile可以保证不同线程对共享变量操作的可见性，因此一个线程读取volatile数组时，总能看到其它线程对该volatile数组最后的写入数据，这样就保证了读取到的数据总是最新的。
CopyOnWriteArrayList通过互斥锁来保护数据。在添加、修改、删除数据时，会先获取互斥锁，修改完毕后，先将volatile数组引用指向新数组，然后再释放互斥锁。这样，就达到了保护数据的目的。
CopyOnWriteArrayList主要的成员变量：
//锁
final transient ReentrantLock lock = new ReentrantLock();
//数组
private transient volatile Object[] array;
CopyOnWriteArrayList在实现线程安全时，用了一把锁。
2.1 创建对象
//创建空的CopyOnWriteArrayList对象
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
//创建含有指定Collection的元素的CopyOnWriteArrayList
public CopyOnWriteArrayList(Collection<? extends E> c) {
Object[] elements;
if (c.getClass() == CopyOnWriteArrayList.class)
elements = ((CopyOnWriteArrayList<?>)c).getArray();
else {
elements = c.toArray();
if (elements.getClass() != Object[].class)
elements = Arrays.copyOf(elements, elements.length, Object[].class);
}
setArray(elements);
}
//创建含有指定数组的元素的CopyOnWriteArrayList
public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
final void setArray(Object[] a) {
array = a;
}
2.2 添加元素
add() 方法在添加集合的时候加了锁，保证了同步，避免了多线程写的时候会copy出多个副本出来。也就是说同时最多只有一个线程可以获取到这把锁，来创建新数组。
总体而言，添加元素的逻辑是：加锁；创建一个新的数组；将现有数组的元素拷贝过去；在新的数组中增加元素；将引用指向新的数组；释放锁。
- 1、在数组末尾追加元素
public boolean add(E e) {
//获取该对象的锁
final ReentrantLock lock = this.lock;
//加锁,每次只有一个线程可进入临界区
lock.lock();
try {
//获取原始"volatile数组"中的数据和数据长度
Object[] elements = getArray();
int len = elements.length;
//新建一个数组newElements，并将原始数据拷贝到newElements中
//newElements数组的长度="原始数组的长度"+1
Object[] newElements = Arrays.copyOf(elements, len + 1);
//将"新增加的元素"保存到newElements中
newElements[len] = e;
//将"volatile数组"引用指向newElements数组，这样旧数组就被GC回收了
setArray(newElements);
return true;
} finally {
//释放锁
lock.unlock();
}
}
- 2、在数组指定位置添加元素
public void add(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
if (index > len || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+len);
Object[] newElements;
int numMoved = len - index;
//如果要插入的位置是最后一位，直接将旧数组复制到新数组中，新数组长度为旧数组长度+1
if (numMoved == 0)
newElements = Arrays.copyOf(elements, len + 1);
//如果要插入的位置不是最后一位，新数组长度为旧数组长度+1，然后将要插入位置前后的数据都复制到新数组中
else {
newElements = new Object[len + 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index, newElements, index + 1,
numMoved);
}
newElements[index] = element;
setArray(newElements);
} finally {
lock.unlock();
}
}
可以看出，添加1个元素时，新数组的长度是在原有数组长度len的基础上+1。同理，往CopyOnWriteArrayList里添加一个元素数量为n的集合时，新数组的长度是len+n。
2.3 删除元素
删除元素的逻辑和添加元素的相似：加锁；创建一个新的数组；将现有数组的元素拷贝过去；在新的数组中删除元素；将引用指向新的数组；释放锁。
//删除索引index处的元素
public E remove(int index) {
final ReentrantLock lock = this.lock;
//加锁
lock.lock();
try {
//获取原始"volatile数组"中的数据和数据长度
Object[] elements = getArray();
int len = elements.length;
//获取elements数组中的第index个数据
E oldValue = get(elements, index);
int numMoved = len - index - 1;
//如果被删除的是最后一个元素，则直接通过Arrays.copyOf()进行处理，而不需要新建数组
if (numMoved == 0)
setArray(Arrays.copyOf(elements, len - 1));
//否则，新建数组，然后将"volatile数组中被删除元素之外的其它元素"拷贝到新数组中
//最后，将"volatile数组"引用指向newElements数组，这样旧数组就被GC回收了。
else {
Object[] newElements = new Object[len - 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
setArray(newElements);
}
//将删除的元素返回
return oldValue;
} finally {
//释放锁
lock.unlock();
}
}
和添加元素同理，删除1个元素时，新数组的长度是在原有数组长度len的基础上-1。同理，往CopyOnWriteArrayList里添加一个元素数量为n的集合时，新数组的长度是len-n。
2.4 获取元素
获取元素是读操作，不修改元素。由于读写分离，因此读数据不需要加锁。
public E get(int index) {
return get(getArray(), index);
}
private E get(Object[] a, int index) {
return (E) a[index];
}
2.5 遍历元素
即迭代器的实现，CopyOnWriteArrayList中有好几种迭代器，以Iterator为例看下即可。
//获取迭代器
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
static final class COWIterator<E> implements ListIterator<E> {
//array的快照版本
private final Object[] snapshot;
//数组下标
private int cursor;
//省略...
public boolean hasNext() {
return cursor < snapshot.length;
}
public boolean hasPrevious() {
return cursor > 0;
}
@SuppressWarnings("unchecked")
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}
@SuppressWarnings("unchecked")
public E previous() {
if (! hasPrevious())
throw new NoSuchElementException();
return (E) snapshot[--cursor];
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor-1;
}
public void remove() {
throw new UnsupportedOperationException();
}
public void set(E e) {
throw new UnsupportedOperationException();
}
public void add(E e) {
throw new UnsupportedOperationException();
}
//省略...
}
从上面的迭代器代码，我们能看出CopyOnWriteArrayList遍历的两个特点：
- 1、支持向前/向后2个方向遍历
COWIterator中有next()、previous()这样获取后一个元素、前一个元素的方法，所以遍历是可以向前、也可以向后的。CopyOnWriteArrayList的底层实现是数组，可以向前向后遍历也正常。 - 2、读时不能修改数组中的元素
COWIterator中的remove、set、add方法都是直接抛出了UnsupportedOperationException，因此在迭代CopyOnWriteArrayList元素时，不能修改元素。
CopyOnWriteArrayList是读写分离的，原数组用来读，新数组用来写。迭代时不能修改，也保证了数据的安全。
三、相关问题
3.1 CopyOnWriteArrayList的迭代器支持fast-fail吗*
不支持。因为写时复制的存在，CopyOnWriteArrayList在使用迭代器迭代的时候，实际上迭代的是原数组，而不是更新的数组，所以中间如果发生新增、删除元素是在新数组上发生的，所以不影响旧数组的迭代，但是正因为元素的迭代发生在旧数组上，所以迭代时更新的数据是获取不到最新的。
【Vector】
一、Vector介绍
public class Vector<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
Vector与ArrayList很相似，也是基于数组来实现，与ArrayList相比，Vector是线程安全的（在每个方法上几乎都增加了synchronized关键字来实现线程间的同步，也正因为如此，Vector的效率会比较低）。可以简单地将Vector理解为线程安全版的ArrayList。
1.1 Vector的特点*
- 1、底层实现与ArrayList相似
Vector底层也是数组，所以也支持随机访问。 - 2、线程安全
Vector与ArrayList最大的不同就在于其是线程安全的，元素修改的方法都是用synchronized关键字修饰的。 - 3、扩容时容量与ArrayList不同
ArrayList不可以设置扩展的容量，默认1.5倍。
Vector可以设置扩展的容量，如果没有设置，默认2倍。 - 4、初始容量与ArrayList不同
ArrayList的无参构造方法中初始容量为0（自动扩容时才扩容为10），而Vector的无参构造方法中初始容量为10。可以简单地理解为这两个容器的初始容量都是10。
1.2 Vector的使用
- 1、构造方法
在构造Vector对象时，可以指定初始容量initialCapacity和每次的增量capacityIncrement。当capacityIncrement小于等于0时，数组成倍扩容；当capacityIncrement大于0时，数组扩容时就增加相对的数值。
//构造一个空Vector，其内部数据数组的大小为10 ，标准容量增量为0
public Vector()
//构造具有指定初始容量，并且其容量增量等于0的空Vector
public Vector(int initialCapacity)
//构造具有指定的初始容量和容量增量的空Vector
public Vector(int initialCapacity, int capacityIncrement)
- 2、添加元素
添加的元素的方式和ArrayList类似，不过每个方法上多了synchronized ，保证线程安全。
//将指定的元素追加到此Vector的末尾
public synchronized boolean add(E e)
//在此Vector中的指定位置插入指定的元素
public void add(int index, E element)
//将指定的元素添加到此向量的末尾
public synchronized void addElement(E obj)
//在指定的index位置插入指定元素
public synchronized void insertElementAt(E obj, int index)
- 3、返回此Vector的当前元素个数
public synchronized int capacity()
- 4、清空Vector
public void clear()
- 5、判断是否包含某元素
public boolean contains(Object o)
- 6、获取元素
//返回指定位置的元素
public synchronized E elementAt(int index)
//返回此Vector的第一个元素
public synchronized E firstElement()
//返回此Vector中指定位置的元素
public synchronized E get(int index)
//获取Vector中的最后一个元素
public synchronized E lastElement()
- 7、比较两个Vector是否相等
public synchronized boolean equals(Object o)
- 8、支持for each循环
public synchronized void forEach(Consumer<? super E> action)
- 9、检索元素位置
//返回此Vector中指定元素的第一次出现的索引，如果此向量不包含元素，则返回-1
public int indexOf(Object o)
//返回此Vector中指定元素的第一次出现的索引，从 index向前检索，如果未找到
//该元素，则返回-1
public synchronized int indexOf(Object o, int index)
//返回此Vector中指定元素的最后一次出现的索引，如果此向量不包含元素，则返回-1
public synchronized int lastIndexOf(Object o)
//返回此Vector中指定元素的最后一次出现的索引，从 index开始 ，如果未找到
//元素，则返回-1
public synchronized int lastIndexOf(Object o, int index)
- 10、Vector是否为空
public synchronized boolean isEmpty()
- 11、返回一个迭代器
public synchronized Iterator< E > iterator()
- 12、删除元素
//删除此Vector中指定位置的元素
public synchronized E remove(int index)
//删除此Vector中第一个出现的指定元素，如果Vector不包含该元素，则不会更改
public boolean remove(Object o)
//删除指定索引处的元素
public synchronized void removeElementAt(int index)
- 13、替换元素
//用指定的元素替换此Vector中指定位置的元素
public synchronized E set(int index, E element)
//用指定的元素替换此Vector中指定位置的元素
public synchronized void setElementAt(E obj, int index)
- 14、返回此Vector中的元素数
public synchronized int size()
二、从源码理解Vector
几个变量：
//存放元素的数组
protected Object[] elementData;
//Vector的实际元素数量
protected int elementCount;
//需要扩容时的增量， 如果capacityIncrement小于或等于0，vector的容量
//需要增长时将会成倍增长
protected int capacityIncrement;
2.1 创建Vector对象
在构造方法中，其实要做的就是确定初始容量和增长因子。初始容量默认为10，每次扩容默认增长一倍
- 1、指定Vector的初始容量和增长容量的构造方法
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
- 2、只指定Vector的初始容量、默认扩容时容量增长一倍的构造方法
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
- 3、默认容量为10、扩容时容量增长一倍的构造方法
public Vector() {
this(10);
}
如调用Vector()方法，此时会生成一个容量为10的Vector：
2.2 自动扩容*
此处以调用addElement方法向Vector中添加元素为例：
public synchronized void addElement(E obj) {
//modCount用于fail-fast机制
modCount++;
//判断在增加一个新的元素后，原数组是否需要扩容
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
private void ensureCapacityHelper(int minCapacity) {
//判断minCapacity是否大于当前容量，如果大于，就调用grow进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//判断capacityIncrement变量是否为0，如果不为0，每次就增加相应的容量；
//为0的话就扩容一倍
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 final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
此处的扩容实现过程与ArrayList大致相似，不同的地方在于判断capacityIncrement变量是否为0，如果不为0，每次就增加相应地的容量；为0的话就扩容一倍。而ArrayList是1.5倍扩容。
2.3 添加元素
添加元素的大致逻辑为：先确定要不要扩容，需要的话就扩容，然后再添加元素。
- 1、添加元素到数组尾部
public synchronized boolean add(E e) {
modCount++;
//先检验是否需要扩容
ensureCapacityHelper(elementCount + 1);
//将元素追加至数组末尾
elementData[elementCount++] = e;
return true;
}
这个方法的实现，除了加了一个synchronized关键字，别的和ArrayList一模一样，图示：
如果此时再调用add方法先后添加2、3两个元素后，Vector会变成：
- 2、添加元素到数组的指定位置
public void add(int index, E element) {
insertElementAt(element, index);
}
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++;
}
假设调用add(1,4)方法，就会在下标索引为1的位置添加元素4。这个过程分为以下几步：
- 3、在数组尾部添加元素
public synchronized void addElement(E obj) {
modCount++;
//检验是否需要扩容
ensureCapacityHelper(elementCount + 1);
//将元素追加至数组末尾
elementData[elementCount++] = obj;
}
- 4、将指定集合的元素添加到数组尾部
public synchronized boolean addAll(Collection<? extends E> c) {
modCount++;
//将集合转换为数组
Object[] a = c.toArray();
int numNew = a.length;
//检验是否需要扩容
ensureCapacityHelper(elementCount + numNew);
//接着将元素拷贝到Vector中
System.arraycopy(a, 0, elementData, elementCount, numNew);
elementCount += numNew;
return numNew != 0;
}
- 5、将指定集合的元素添加到数组的指定位置
public synchronized boolean addAll(int index, Collection<? extends E> c) {
modCount++;
//检验位置参数是否合法
if (index < 0 || index > elementCount)
throw new ArrayIndexOutOfBoundsException(index);
//将集合元素插入指定数组中
Object[] a = c.toArray();
int numNew = a.length;
//判断是否需要扩容
ensureCapacityHelper(elementCount + numNew);
//判断要插入的位置是否小于元素数量，如果小于，则需要将Vector中从插入元素位置后面的元素向后移动
int numMoved = elementCount - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//将集合转化成的数组中的元素全部插入到Vector对应的数组中
System.arraycopy(a, 0, elementData, index, numNew);
elementCount += numNew;
return numNew != 0;
}
addAll(Collection<? extends E> c)和addAll(int index, Collection<? extends E> c)方法的作用是相似的，都是将一个集合中的元素添加到数组中，差异之处是前者是在数组末尾插入，后者是在指定位置插入。接下来以addAll(int index, Collection<? extends E> c)为例，演示一下添加一个集合的过程：
2.4 删除元素
删除元素的逻辑就是删指定的（一个或多个）元素，然后将空出来的位置置为null，便于GC。
- 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);
//数组最后一个元素置为null
elementData[--elementCount] = null; // Let gc do its work
return oldValue;
}
- 2、删除数组中第一次出现的某个元素
public boolean remove(Object o) {
return removeElement(o);
}
public synchronized boolean removeElement(Object obj) {
modCount++;
//如果能检索出指定元素的位置，就删除该元素
int i = indexOf(obj);
if (i >= 0) {
removeElementAt(i);
return true;
}
return false;
}
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--;
//数组最后一个元素置为null
elementData[elementCount] = null; /* to let gc do its work */
}
Vector删除单个元素和ArrayList删除单个元素的过程相似。remove(Object o)和remove(int index)大致思路相似，先找到index，再删除对应位置上的元素，图示：
- 3、清空数组
public void clear() {
removeAllElements();
}
public synchronized void removeAllElements() {
modCount++;
//所有元素置为null
for (int i = 0; i < elementCount; i++)
elementData[i] = null;
elementCount = 0;
}
2.5 更新元素
- 1、替换指定位置的元素，并将被替换的元素返回
public synchronized E set(int index, E element) {
//检验位置参数合法性
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
//获取该位置现有元素，替换新元素，返回旧元素
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
- 2、替换指定位置的元素
//与上个方法相比，差异是不再将旧元素返回
public synchronized void setElementAt(E obj, int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
elementData[index] = obj;
}
2.6 获取元素
Vector中获取元素的方法有三个：获取某个位置、首部和尾部的元素。这也是底层是数组实现的集合类的常见操作。
- 1、获取数组任意位置上的元素
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
public synchronized E elementAt(int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
}
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
get(index)和elementAt(int index)都是获取某位置元素的方法。
- 2、获取数组第一个元素
public synchronized E firstElement() {
if (elementCount == 0) {
throw new NoSuchElementException();
}
//获取第一个元素
return elementData(0);
}
- 3、获取数组最后一个元素
public synchronized E lastElement() {
if (elementCount == 0) {
throw new NoSuchElementException();
}
//获取最后一个元素
return elementData(elementCount - 1);
}
2.7 检索元素
Vector中检索元素的方法也是大致分为两大类：从前向后检索和从后向前检索。
- 1、从头开始检索元素
从头部开始，从前向后获取元素出现的第一个位置。
public int indexOf(Object o) {
//从头开始检索某个元素
return indexOf(o, 0);
}
- 2、indexOf(Object o, int index)
从指定位置开始，从前向后获取元素出现的第一个位置。
public synchronized int indexOf(Object o, int index) {
//先判断要检索的元素是否为null
//检索null
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;
}
- 3、lastIndexOf(Object o)
从尾部开始，从后向前获取元素出现的最后一个位置。
public synchronized int lastIndexOf(Object o) {
//从末尾开始，从后向前检索
return lastIndexOf(o, elementCount-1);
}
- 4、lastIndexOf(Object o, int index)
从指定位置开始，从后向前获取元素出现的最后一个位置。
public synchronized int lastIndexOf(Object o, int index) {
//检索index合法性
if (index >= elementCount)
throw new IndexOutOfBoundsException(index + " >= "+ elementCount);
//判断要检索的元素是否为null
//检索null
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;
}
【Stack】
一、Stack介绍
Stack是栈，是Vector的“窄化”实现。在栈中，可以操作元素的一段叫栈顶（数组尾部），数组的另一端是栈底（数组首部），图示：
在栈中可以进行的操作是入栈和出栈。图示：
1.1 Stack的特点*
Stack的特点，可以简单归结为两点：
- 1、在底层数组的一端（栈顶）进行存储/取出元素
普通的数组，一般都可以从两端进行存储和取出元素的操作，但Stack作为Vector的“窄化”实现，严格规定只能在数组的一端进行操作。 - 2、先进后出（LIFO）
Stack中存储的元素，都是后进先出（LIFO，最后入栈的元素最先出栈），因为先存入Stack中的元素存入了Stack底部，在取出该元素时自然是最后一个取出的。 - 3、线程安全
Stack继承于Vector，所以也是线程安全的。
1.2 Stack的使用
Stack继承了Vector，所以Vector的方法Stack都有。同时，由于Stack具有先进后出的特点，所以多了一些方法。
- 1、创建一个空栈
public Stack()
- 2、此栈是否为空
public boolean empty()
- 3、查看栈顶的对象，而不从栈中删除
public synchronized E peek()
- 4、删除并返回此堆栈顶部的对象
public synchronized E pop()
- 5、将元素存入到栈的顶部
public E push(E item)
- 6、返回一个对象在此栈上的基于栈顶的相对位置
public synchronized int search(Object o)
这个方法优点特殊，看个示例：
Stack<String> stack = new Stack<String>();
stack.push("A");
stack.push("B");
stack.push("C");
int index = stack.search("A");
if(index != -1) {
System.out.println("元素A在Stack中的位置是：" + index);
}
else {
System.out.println("元素A不在Stack中");
}
运行结果：
元素A在Stack中的位置是：3
二、从源码理解Stack
2.1 创建对象
public Stack() {
//由于在子类的构造方法中默认有一条隐式的语句super()，所以此处是先调用其父类
//无参构造方法，因此Stack的初始化流程可以理解为和Vector的无参构造过程一致
}
2.2 添加（栈顶）元素
//将元素放置到栈顶
public E push(E item) {
//调用其父类的addElement方法
addElement(item);
return item;
}
//该方法的实现与Vector的方法相同，不过是线程安全的，因为方法用synchronized修饰
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
从addElement方法可以看出，栈底是数组的首部，每次向栈中添加元素时，都是在数组后面追加。
2.3 删除（栈顶）元素
public synchronized E pop() {
E obj;
int len = size();
//peek是获取栈顶元素的方法
obj = peek();
//调用其父类Vector中的方法，作用是根据索引删除数组中的一个元素
removeElementAt(len - 1);
return obj;
}
//Stack父类Vector中的removeElementAt方法，是线程安全的
public synchronized void removeElementAt(int index)
删除栈顶元素，其实就是删除数组尾部的元素。
2.4 获取（栈顶）元素
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
//调用了其父类中的elementAt方法
return elementAt(len - 1);
}
//Stack父类Vector中的方法，是线程安全的
public synchronized E elementAt(int index)
获取栈顶元素，其实就是获取数组尾部的元素。
2.5 判断Stack是否为空
public boolean empty() {
//调用了父类的size方法
return size() == 0;
}
//Stack父类Vector中的方法，是线程安全的
public synchronized int size()
2.6 获取元素相对于栈顶的位置*
//某个元素在栈中相对于栈顶(数组尾部)位置的方法
public synchronized int search(Object o) {
//栈中的栈顶元素是最后添加的，而search方法要返回某个元素相对于栈顶元素
//的位置，所以最后要返回size()-i
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
这个方法比较特殊，图示：
像上图中的元素“3”，相对于栈顶的位置是1，因此用search检索，返回值就是1。