Java集合(一) —— Collection源码分析
Java集合(二) —— ArrayList源码分析
Java集合(三) —— LinkedList源码分析
Java集合(四) —— PriorityQueue源码分析
Java集合(五) —— HashSet源码分析
Java集合(六) —— LinkedHashSet源码分析
Java集合(七) —— TreeSet源码分析
Java集合(八) —— HashMap源码分析
Java集合(九) —— LinkedHashMap源码分析
Java集合(十) —— TreeMap源码分析
1.ArrayList继承图
ArrayList.png
2.ArrayList的数据结构
// 源码
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
可以看到ArrayList的底层是通过数组实现的。
数组（Array）是一种线性表数据结构，用一组连续的内存空间，来存储一组具有相同类型的数据。
3.ArrayList性能分析
1.因为ArrayList是基于数组实现的，所以可以通过下标快速访问元素(包括get&set)，其时间复杂度为O(1)。
2.增加/删除元素：最理想的状况是从数组末尾增加或删除元素，不需要移动数据，时间复杂度为O(1);最糟糕的状况是从头部新增或删除一个元素，导致所有的元素都要移动一位，时间复杂度为O(n)；
3.因为每个位置插入/删除元素的概率是一样的，所以平均时间复杂度为（1+2+…n）/n=O(n)
总结(对比LinkedList)：
- ArrayList具有较好的查询性能，而新增/删除都可能引起大量元素的移动，性能较差，所以ArrayList适用于查询较多，新增/删除较少的场景。
- LinkedList(下一章会介绍)是基于链表的，在查询(随机访问)时性能较差，因为需要在双向链表中寻找index的位置再返回，所以LinkedList适用于查询较少，新增/删除较多的场景。
- LinkedList需要额外的内存空间保存索引信息。
4.源码分析
- 成员变量分析
/**
* 默认初始容量大小为 10
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 指定该ArrayList容量为0时，返回该空数组。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 当调用无参构造方法，返回的是该数组。刚创建一个ArrayList 时，其内数据量为0。
* 它与EMPTY_ELEMENTDATA的区别就是：该数组是默认返回的，而后者是在用户指定容量为0时返回。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 存储集合元素的底层实现：真正存放元素的数组。
* 被标记为transient，在对象被序列化的时候不会被序列化。
*/
transient Object[] elementData;
/**
* 实际元素数量
*/
private int size;
- 构造函数分析
/**
* 默认将elementData 指向一个空数组，即其大小为0，要在第一次添加元素时容量才扩大至10。(可以认为是一种懒加载机制，避免浪费内存空间)
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 指定容量的构造函数
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
/**
* 使用指定集合构造ArrayList
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
3.核心方法分析
- add(E e)
public boolean add(E e) {
// 检查是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 新增元素
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 第一次添加元素时，minCapacity = 1，所以返回默认容量DEFAULT_CAPACITY = 10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
// list被修改次数
modCount++;
// overflow-conscious code
// minCapacity = 10
if (minCapacity - elementData.length > 0)
// 进行扩容
grow(minCapacity);
}
/**
* 扩容
*/
private void grow(int minCapacity) {
// 当前数组容量
int oldCapacity = elementData.length;
// 扩容新容量
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果扩容后容量仍小于期望的最小容量
if (newCapacity - minCapacity < 0)
// 将期望的最小容量赋值给新容量
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 如果扩容后的容量大于临界值，则进行大容量分配
newCapacity = hugeCapacity(minCapacity);
// 进行数组复制
elementData = Arrays.copyOf(elementData, newCapacity);
}
关于扩容
int newCapacity = oldCapacity + (oldCapacity >> 1);
首先说明，扩容并非网上所说在原来基础上增加一半。oldCapacity >> 1是位运算，假设oldCapacity = 10，则newCapacity = 15；下一次扩容时，oldCapacity = 15，newCapacity = 22。(不懂位运算的请自行百度)
- add(int index, E element)
public void add(int index, E element) {
// 数组越界检查
rangeCheckForAdd(index);
// 检查是否需要扩容
ensureCapacityInternal(size + 1);
// 拷贝数组
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 指定位置新增元素
elementData[index] = element;
// 数组大小+1
size++;
}
- remove(int index)
public E remove(int index) {
// 下标越界检查
rangeCheck(index);
// 修改次数+1
modCount++;
E oldValue = elementData(index);
// 需要移动的元素数量
int numMoved = size - index - 1;
if (numMoved > 0)
// 移动元素操作
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
- get(int index)
public E get(int index) {
// 数组越界检查
rangeCheck(index);
// fail-fast：快速失败机制
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
E elementData(int index) {
return (E) elementData[index];
}
关于快速失败机制
fail-fast 机制，即快速失败机制，是java集合(Collection)中的一种错误检测机制。当在迭代集合的过程中该集合在结构上发生改变的时候，就有可能会发生fail-fast，即抛出 ConcurrentModificationException异常。fail-fast机制并不保证在不同步的修改下一定会抛出异常，它只是尽最大努力去抛出，所以这种机制一般仅用于检测bug。
- clear()
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
- set(int index, E element)
/**
* 替换指定索引元素
*/
public E set(int index, E element) {
// 数组越界检查
rangeCheck(index);
// 记录旧的元素
E oldValue = elementData(index);
// 替换元素
elementData[index] = element;
return oldValue;
}
