最近在恶补数据结构和算法,顺带着把 ArrayList 和 Vector 看了看,因此写了这篇文章记录下。我们知道 ArrayList 和 Vector 底层数据结构都是数组,而数组这种数据结构一旦创建它的容量就不可改变了,而我们平常使用的这两个类却一直能插入元素,这是为什么呢?下面我们开始按照 API 一个一个解析,注意我们不可能把每个 API 都面面俱到,因此只介绍一些常用的,其它的自行查看
- transient Object[] elementData;
- private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
- private static final Object[] EMPTY_ELEMENTDATA = {};
- public ArrayList() {
- //初始化一个没有容量数组
- this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
- }
- public ArrayList(int initialCapacity) {
- if (initialCapacity > 0) {
- //传入的容量如果大于0,初始化一个自定义容量的数组
- this.elementData = new Object[initialCapacity];
- } else if (initialCapacity == 0) {
- //传入的容量等于0,初始化一个没有容量的数组
- this.elementData = EMPTY_ELEMENTDATA;
- } else {
- throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
- }
- }
假设我们使用的是无参的构造,即初始容量为 0
- //成员变量,默认值是0
- private int size;
- public boolean add(E e) {
- //扩充容量,size+1是我们需要的容量
- ensureCapacityInternal(size + 1); // Increments modCount!!
- //按照下标存入数组,存入后数组中元素个数size就会加1
- elementData[size++] = e;
- return true;
- }
- private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
- private static final int DEFAULT_CAPACITY = 10;
- private void ensureCapacityInternal(int minCapacity) {
- if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
- //添加第一个元素时,会直接把我们需要的容量改为10
- minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
- }
- //决定是否需要扩充容量
- ensureExplicitCapacity(minCapacity);
- }
- //记录修改次数
- protected transient int modCount = 0;
- private void ensureExplicitCapacity(int minCapacity) {
- //modCount只是记录修改次数
- modCount++;
- // overflow-conscious code
- 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;
- //扩充为当前数组容量的1.5倍
- int newCapacity = oldCapacity + (oldCapacity >> 1);
- //扩充后的容量还是小于我们需要的容量,就直接扩充为我们需要的容量
- if (newCapacity - minCapacity < 0)
- newCapacity = minCapacity;
- //扩充后的容量大于Integer.MAX_VALUE - 8,就采用hugeCapacity方法中的策略扩充
- if (newCapacity - MAX_ARRAY_SIZE > 0)
- newCapacity = hugeCapacity(minCapacity);
- //该方法最终会复制旧的数组中的数据项到新的扩充后的数组中
- elementData = Arrays.copyOf(elementData, newCapacity);
- }
上面方法中,主要有 hugeCapacity 方法和 Arrays.copyOf 方法,我们先看 hugeCapacity 方法
- private static int hugeCapacity(int minCapacity) {
- if (minCapacity < 0) // overflow
- throw new OutOfMemoryError();
- //判断我们需要的容量是否大于Integer.MAX_VALUE - 8
- //大于就扩充容量为Integer最大值,小于就扩充为Integer.MAX_VALUE-8
- return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE: MAX_ARRAY_SIZE;
- }
我们再看 Arrays 类的静态方法 copyOf
- public static <T> T[] copyOf(T[] original, int newLength) {
- //调另一个重载方法
- return (T[]) copyOf(original, newLength, original.getClass());
- }
- public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
- @SuppressWarnings("unchecked")
- //创建一个新的扩充容量后的数组
- T[] copy = ((Object)newType == (Object)Object[].class)
- ? (T[]) new Object[newLength]
- : (T[]) Array.newInstance(newType.getComponentType(), newLength);
- //将原始数组从0索引开始复制所有的数据项,到新的数组中,新的数组从0开始接收数据项
- //其实就是复制旧的数组的数据项到新的扩充后的数组中
- System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
- return copy;
- }
从上面代码我们可以得到 ArrayList 的扩充容量机制,但是为什么要有这么一个扩容机制呢?其实这是由数组本身这种数据结构所决定的,数组一旦创建,它的容量就固定了,因此只能猜测它的大小,而我们却又不知道用户到底有多少数据项,猜大了浪费空间,猜小了又不能完全存储用户的数据。所以我们想到达到随着数据项的插入进行动态扩展的目的,就必须创建一个新的容量的数组,并且把旧的数组的数据项复制到新的数组中。ArrayList 大体采用 1.5 倍扩容,并且并不是每次添加元素都要扩容,这是考虑到创建新数组,复制数据的效率问题,以空间换时间。具体的扩容策略见下表:
添加第 N 个元素 | 添加后的数组容量 |
---|---|
只创建不添加 | 初始容量 0 |
1 | 10 |
2 | 10 |
3 | 10 |
... | 10 |
11 | 15 |
12 | 15 |
... | 15 |
16 | 22 |
17 | 22 |
... | ... |
m | Integer.MAX_VALUE - 8 |
... | Integer.MAX_VALUE - 8 |
Integer.MAX_VALUE - 8 | Integer.MAX_VALUE - 8 |
Integer.MAX_VALUE - 7 | Integer.MAX_VALUE |
... | Integer.MAX_VALUE |
remove 有两个重载的方法,一个是根据索引开始移除,一个是根据元素开始移除,其实归根到底都是根据索引移除,先看根据索引移除
- public E remove(int index) {
- if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- //修改次数+1
- modCount++;
- //获取数组中对应索引的元素,最后直接返回
- E oldValue = (E) elementData[index];
- //需要移动的元素数量
- int numMoved = size - index - 1;
- //判断是否需要移动,比如index为最后一个元素时,只需要最后一个元素置为null即可,不需要移动
- if (numMoved > 0)
- //从数组中删除项的后一位开始复制之后的所有元素,复制到数组中,数组从删除项的那一位开始接收
- //即删除项后面的所有元素都向前移动一位
- System.arraycopy(elementData, index + 1, elementData, index, numMoved);
- //最后一个数据项置为null,尽快让GC回收,并且ArrayList的size减一
- elementData[--size] = null; // clear to let GC do its work
- return oldValue;
- }
再看另外一个根据元素移除
- public boolean remove(Object o) {
- if (o == null) {
- for (int index = 0; index < size; index++)
- if (elementData[index] == null) {
- //注意这个数组是可以重复的,这里只是线性查找到元素的第一个索引,然后调fastRemove方法移除
- fastRemove(index);
- return true;
- }
- } else {
- for (int index = 0; index < size; index++)
- if (o.equals(elementData[index])) {
- //注意这个数组是可以重复的,这里只是线性查找到元素的第一个索引,然后调fastRemove方法移除
- fastRemove(index);
- return true;
- }
- }
- return false;
- }
- private void fastRemove(int index) {
- //修改次数+1
- modCount++;
- //需要移动的元素数量
- int numMoved = size - index - 1;
- //判断是否需要移动,比如index为最后一个元素时,只需要最后一个元素置为null即可,不需要移动
- if (numMoved > 0)
- //从数组中删除项的后一位开始复制之后的所有元素,复制到数组中,数组从删除项的那一位开始接收
- //即删除项后面的所有元素都向前移动一位
- System.arraycopy(elementData, index + 1, elementData, index, numMoved);
- //最后一个数据项置为null,尽快让GC回收,并且ArrayList的size减一
- elementData[--size] = null; // clear to let GC do its work
- }
整体删除过程如下图
- public void clear() {
- //修改次数+1
- modCount++;
- //所有元素置为null,尽快让GC回收
- for (int i = 0; i < size; i++)
- elementData[i] = null;
- //元素个数置为0
- size = 0;
- }
- public E set(int index, E element) {
- if (index >= size)
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- //获取数组中对应索引的旧元素,最后直接返回
- E oldValue = (E) elementData[index];
- //直接插入新的元素到数组中指定的索引
- elementData[index] = element;
- return oldValue;
- }
- public E get(int index) {
- if (index >= size)
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- //返回数组中对应索引的元素
- return (E) elementData[index];
- }
- public int indexOf(Object o) {
- if (o == null) {
- //ArrayList中的元素是可以重复的,这里从0索引开始线性查找元素的第一个索引,直接返回
- for (int i = 0; i < size; i++)
- if (elementData[i]==null)
- return i;
- } else {
- //ArrayList中的元素是可以重复的,这里从0索引开始线性查找元素的第一个索引,直接返回
- for (int i = 0; i < size; i++)
- if (o.equals(elementData[i]))
- return i;
- }
- //找不到就返回-1
- return -1;
- }
- public int lastIndexOf(Object o) {
- if (o == null) {
- //ArrayList中的元素是可以重复的,这里从最后一个索引开始线性查找元素,
- //找到第一个索引就直接返回,因此这里返回的是元素的最后一个索引
- for (int i = size-1; i >= 0; i--)
- if (elementData[i]==null)
- return i;
- } else {
- //ArrayList中的元素是可以重复的,这里从最后一个索引开始线性查找元素,
- //找到第一个索引就直接返回,因此这里返回的是元素的最后一个索引
- for (int i = size-1; i >= 0; i--)
- if (o.equals(elementData[i]))
- return i;
- }
- //找不到就返回-1
- return -1;
- }
- public boolean contains(Object o) {
- //ArrayList是否包含某个元素,其实就是看indexOf方法能否找到某个元素的索引
- return indexOf(o) >= 0;
- }
- private int size;
- public int size() {
- //add、remove、clear等都会对元素个数修改
- return size;
- }
- public boolean isEmpty() {
- //ArrayList是否为空,即判断元素个数size是否等于0
- return size == 0;
- }
由于 Vector 和 ArrayList 很多方法的实现都是一样的,部分只是在方法上加了同步,因此只介绍和 ArrayList 不同的 API
假设我们调的是无参构造
- protected Object[] elementData;
- //扩充容量时的增长量
- protected int capacityIncrement;
- public Vector() {
- //调一个参数的构造
- this(10);
- }
- public Vector(int initialCapacity) {
- //initialCapacity为10,调两个参数的构造
- this(initialCapacity, 0);
- }
- public Vector(int initialCapacity, int capacityIncrement) {
- super();
- //第一个参数为10表示初始化数组的容量,第二个参数为0表示扩充容量时的增长量
- if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
- //初始化容量为10的数组
- this.elementData = new Object[initialCapacity];
- this.capacityIncrement = capacityIncrement;
- }
可以看到 Vector 对象一创建就会初始化一个容量为 10 的数组,而 ArrayList 是初始化一个容量为 0 的数组,添加第一个元素才会扩充容量为 10
- protected int elementCount;
- //加了同步修饰符
- public synchronized boolean add(E e) {
- //修改次数+1
- modCount++;
- //扩充容量,elementCount+1是我们需要的容量,elementCount就是ArrayList中的size
- ensureCapacityHelper(elementCount + 1);
- //按照下标存入数组,存入后数组中元素个数elementCount就会加1
- elementData[elementCount++] = e;
- return true;
- }
- private void ensureCapacityHelper(int minCapacity) {
- //需要的容量比现有的容量大的话,需要扩充容量
- if (minCapacity - elementData.length > 0)
- grow(minCapacity);
- }
- private void grow(int minCapacity) {
- int oldCapacity = elementData.length;
- //由于我们调的是无参构造,这里扩充容量的增长量capacityIncrement为0,
- //所以这里是扩充为原来的2倍,而ArrayList是扩充1.5倍
- 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);
- }
Vector 和 ArrayList 的扩容机制稍有不同,ArrayList 不添加元素时容量为 0,Vector 不添加元素时容量为 10,并且 ArrayList 是 1.5 倍扩容,Vector 是 2 倍扩容,具体见下表:
添加第 N 个元素 | 添加后的数组容量 |
---|---|
只创建不添加 | 10 |
1 | 10 |
2 | 10 |
3 | 10 |
... | 10 |
11 | 20 |
12 | 20 |
... | 20 |
21 | 40 |
22 | 40 |
... | ... |
m | Integer.MAX_VALUE - 8 |
... | Integer.MAX_VALUE - 8 |
Integer.MAX_VALUE - 8 | Integer.MAX_VALUE - 8 |
Integer.MAX_VALUE - 7 | Integer.MAX_VALUE |
... | Integer.MAX_VALUE |
一个根据索引移除,一个根据元素移除,这两个方法和 ArrayList 一样,只是加了 synchronized 修饰符
和 ArrayList 一样,只是加了 synchronized 修饰符
和 ArrayList 一样,只是加了 synchronized 修饰符
和 ArrayList 一样,只是加了 synchronized 修饰符
比 ArrayList 多了一个方法,并且加了同步,而且可以从指定索引向后开始查找,这种设计要比 ArrayList 要好
- 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;
- }
比 ArrayList 多了一个方法,并且加了同步,而且可以从指定索引向前开始查找,这种设计要比 ArrayList 要好
- 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;
- }
和 ArrayList 一样,只是加了 synchronized 修饰符
和 ArrayList 一样,只是加了 synchronized 修饰符
和 ArrayList 一样,只是加了 synchronized 修饰符
来源: http://www.jianshu.com/p/c4027084ac43