ArrayList(线程不安全)
ArrayList是一个其容量能够动态增长的动态数组
继承关系
构造方法
是符合collection父接口的规范的
//传0则设置为默认容量
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);
}
}
//把collection中的元素取出来,再放在一个数组中
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();//这个地方说明引用不能为空,否则会出nullpointer异常
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;
}
}
//ArrayList的toarray,因为底层是用数组存的,所以就是把数组复制一下
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}//这里T其实就是object,所以上面需要做一个if判断,其他集合最后可能不是object
Fail-Fast
重要方法
add
在某个索引处添加元素,或者添加集合,删除元素,都是直接通过数组的复制(System.arrayCopy)来完成而不是元素的移动,可以根据情况决定调用次数
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
//在传入index参数的时候,都会对其进行检查
private void rangeCheck(int index)
//在调用add在某个index处插入的方法时采用这个进行检查
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
}
search
//从前往后找
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
//从后往前找
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
set
//修改该位置的值,返回原来该位置的值
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
Sort方法
根据由指定Comparator引起的顺序对该列表进行排序。
使用指定的比较器，此列表中的所有元素必须可以相互比较
如果指定的比较器为null则此列表中的所有元素都必须实现Comparable接口，并且应使用元素的自然顺序。
该列表必须是可修改的，但无需调整大小。
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
}
这里的核心方法其实是Arrays.sort()
public static <T> void sort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> c) {
if (c == null) {
//根据其对象的自然顺序，将指定对象数组的指定范围按升序排序。 要排序的范围从索引fromIndex （包括在内）到索引toIndex （不包括在内）。
// （如果fromIndex==toIndex ， fromIndex==toIndex排序的范围为空。）此范围中的所有元素必须实现Comparable接口
sort(a, fromIndex, toIndex);
} else {
rangeCheck(a.length, fromIndex, toIndex);
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, fromIndex, toIndex, c);//将被遗弃
else
TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
}
}
这里主要是sort()与TimSort.sort()这两个核心方法,让我们再看一看他们的实现
- sort()
//ComparableTimSort
static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {
assert a != null && lo >= 0 && lo <= hi && hi <= a.length;
int nRemaining = hi - lo;
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted
// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi);
binarySort(a, lo, hi, lo + initRunLen);
return;
}
-TimSort.sort()
//TimSort
static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
T[] work, int workBase, int workLen) {
assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;
int nRemaining = hi - lo;
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted
// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
binarySort(a, lo, hi, lo + initRunLen, c);
return;
}
发现没有,这两个方法的实现几乎一模一样,再看一下,不仅如此ComparableTimSort与TimSort这两个类也几乎一模一样.
这是源码给的注释
This is a near duplicate of TimSort, modified for use with arrays of objects
that implement Comparable, instead of using explicit comparators.
最后其实都是调用了binarySort(a, lo, hi, lo + initRunLen, c)进行排序
这里贴出源码
private static void binarySort(Object[] a, int lo, int hi, int start) {
assert lo <= start && start <= hi;
if (start == lo)
start++;
for ( ; start < hi; start++) {
Comparable pivot = (Comparable) a[start];
// Set left (and right) to the index where a[start] (pivot) belongs
int left = lo;
int right = start;
assert left <= right;
/*
* Invariants:
* pivot >= all in [lo, left).
* pivot < all in [right, start).
*/
while (left < right) {
int mid = (left + right) >>> 1;
if (pivot.compareTo(a[mid]) < 0)
right = mid;
else
left = mid + 1;
}
assert left == right;
/*
* The invariants still hold: pivot >= all in [lo, left) and
* pivot < all in [left, start), so pivot belongs at left. Note
* that if there are elements equal to pivot, left points to the
* first slot after them -- that's why this sort is stable.
* Slide elements over to make room for pivot.
*/
int n = start - left; // The number of elements to move
// Switch is just an optimization for arraycopy in default case
switch (n) {
case 2: a[left + 2] = a[left + 1];
case 1: a[left + 1] = a[left];
break;
default: System.arraycopy(a, left, a, left + 1, n);
}
a[left] = pivot;
}
}
将里面的元素转换成数组
//实际上经过一些预处理之后都会调用 System.arraycopy方法;
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
扩容
在add元素的时候
- 确保最小容量为size+1(所含元素的个数),ensureCapacityInternal(size+1)
- 计算出最小容量calculateCapacity(elementData, minCapacity),如果比默认的小就返回默认的,比默认的大,就返回自己
- ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)),判断当前数组长度与所需的最小容量
- 如果所需最小容量>当前数组长度,调用grow进行扩容
- 一般而言根据
newCapacity = oldCapacity + (oldCapacity >> 1);进行扩容- 如果这样之后数组长度依然不够,则直接
newCapacity = minCapacity;- 如果超过了定义的最大数组长度调用
newCapacity = hugeCapacity(minCapacity);- 最后进行扩容(实际上就是数组的复制)
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
内部类
1. private class Itr implements Iterator<E>
2. private class ListItr extends Itr implements ListIterator<E>
3. private class SubList extends AbstractList<E> implements RandomAccess
对外提供subList(int fromIndex, int toIndex)方法
Itr
An optimized version of AbstractList.Itr
主要作用就是返回一个他的实例作为迭代器
public Iterator<E> iterator() {
return new Itr();
}
ListItr
//这个方法事实上还是调用的下面这个方法
public ListIterator<E> listIterator() {
return new ListItr(0);
}
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
SubList
被用于求子列表的方法
//这个方法ArrayList与SubList均实现了,一模一样
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
重要属性
/**
*默认初始容量为十.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
*/
//这两个属性,只是为了初始化不报空指针异常
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//ArrayList中含有元素的数量
private int size;
//针对数组而言,指数组的长度
int length;
//最大数组位数要比最大整数小8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//用这个数组来存储集合中的元素
transient Object[] elementData;