ArrayList 的应用场景
ArrayList的底层数据结构是数组，也就是说它满足数组的特点，数组的优势在于：它在物理内存上的地址是一块连续的内存空间，这无疑对查询的操作是友好的，查询的时间复杂度为O(1)，但就结构改变的操作是很浪费时间的，因为当数组的元素很多的时候，ArrayList集合下大部分删除增加方法的时间复杂度接近O(n)，add(E e)除外，它是直接插入在数组末尾，时间复杂度为O(1)。
它与List接口下的其他集合的区别
List接口下有三个集合类：ArrayList、LinkedList、Vector
- LinkedList：底层是基于双向链表实现的，查询慢、增删效率高。
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
- Vector：底层是基于数组实现，同ArrayList相同，只不过它是线程安全的集合，被synchronize修饰
public synchronized void copyInto(Object[] anArray) {
System.arraycopy(elementData, 0, anArray, 0, elementCount);
}
当然List接口下面还有很多子类的实现类：比如Stack，它扩展自Vector集合，这里不会展开它，后期它处再详细解释。
ArrayList集合中的一些方法
- add(E e)，增加元素，如下是这个代码的执行流程，难懂的地方加了注释，请12345按照序列阅读
transient Object[] elementData;
//当你未指定容量大小的时候 如：List list = newArrayLIst();
//它的底层数组容量默认采用这个常量
private static final int DEFAULT_CAPACITY = 10;
public boolean add(E e) {
//1、判断当前数组容量的大小是否能执行增加元素这一操作
ensureCapacityInternal(size + 1);
//5、将这个新元素放在index++这个索引位置
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//2、如果数组的长度确实和默认大小是相等的
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//3、取这俩个之中大的那一个给这个minCapacity变量
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//4 确定新数组的大小
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//4.1 protected transient int modCount = 0;
//这个值是用来判断并发操作下
//处于迭代器遍历下的这个集合里面的值有没有被其他线程修改，如果变了，那么直接抛出异常
//这个机制称之为快速失败机制
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//4.2
grow(minCapacity);
}
/*
这个就是它的扩容机制了
*/
private void grow(int minCapacity) {
// 原数组容量大小，是指这个数组的长度而不是元素个数
int oldCapacity = elementData.length;
// 新数组的容量是原来的1.5倍。这里>>1操作是进行了一个移位运算，向右移一位，相当于除2
int newCapacity = oldCapacity + (oldCapacity >> 1);
//这下面就是和原来的miniCapacity比较、然后取值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//这里值的注意的是，当你的数组容量起初已经很大的时候，可能会超出它对数组本来的大小限制
//这时候就会进行一个再取值，反正最后的数组大小就是它指定的一个大小。不是你的值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 这里就是将原数组的内容拷贝到新长度的数组容器中，并覆盖掉原数组，让GC回收它
elementData = Arrays.copyOf(elementData, newCapacity);
}
- add(int index, E element)，按指定索引添加
public void add(int index, E element) {
//检查索引范围是否合法
rangeCheckForAdd(index);
//熟悉的方法，同add里的相同，这一步是再判断集合里面还有没有容量来容下这个元素
ensureCapacityInternal(size + 1);
//首先我们要明确一点，这个集合底层的删除和按索引添加其实就是创建了一个新的数组，将旧数组里的
//部分信息复制进新数组，下面这个方法可以这么理解
//参数：源数组、从源数组中的起始位置、目标数组、从目标数组的起始位置、复制的步长
System.arraycopy(elementData, index, elementData, index + 1,size - index);
//将元素放入新数组
elementData[index] = element;
size++;
}
- remove(int index) 删除元素
protected transient int modCount = 0;
public E remove(int index) {
//索引检查是否合法
rangeCheck(index);
//基于快速失败机制，为保证集合的安全性，如果这个modCount被修改，直接抛出异常，终止操作
modCount++;
E oldValue = elementData(index);
//需要移动的元素个数
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,numMoved);
//末尾索引位置的元素设置未null
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
- removeRange(int fromIndex, int toIndex) 删除指定范围内的元素
private final AbstractList<E> l;
private final int offset;
private int size;
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
//复制数组，从源数组toIndex位置开始，目标数组fromIndex位置开始。复制源数组numCount个元素
System.arraycopy(elementData, toIndex, elementData, fromIndex,numMoved);
// 将末尾空出来的位置numMoved个位置设置为null，等待GC回收
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
网友评论