当前位置：首页 > 分类 > JAVA基础 > JDK源码-ArrayList
JDK源码-ArrayList
1，ArrayList的秘密都在构造函数里
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2，接着 elementData 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
/**
* 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;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
翻译elementData的注释
存储ArrayList元素的数组缓冲区。
ArrayList的容量是这个数组缓冲区的长度。
添加第一个元素时，任何elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都将扩展为默认的DEFAULT_CAPACITY容量。
3，接着DEFAULT_CAPACITY
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
默认容量为10
4，看下添加第一个元素时发生了什么
/**
* Appends the specified element to the end of this list.
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
确定内部容量，size作为成员变量private int size;，实例化时默认赋值为0，也就是用（0+1）1去确定内部容量。
size 加 1 ，并给索引位置赋值。
返回true。
这样添加就完成了，是否扩容并在下标位置赋值。
5，进入ensureCapacityInternal方法
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
ensureExplicitCapacity(minCapacity);
}
如果是空数组，用传入的容量和默认的容量 之中 大的那一个作为初始化容量。也就是10个元素以内容量一直是10；
6，上面是初始化，下面才是真正的确定容量。进入ensureExplicitCapacity方法。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0) grow(minCapacity);
}
修改次数 加1。这个参数用作并发修改控制。
如果需要的容量大于数组的长度，用需要的容量扩容。
7，扩容，grow（）
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);
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
数组的原容量oldCapacity
准备的容量oldCapacity + (oldCapacity >> 1)；>>1向右位移1位，高位补0，即除以2，结果为1.5倍的原容量。
准备的容量不够，就用需要的容量。
准备的容量大于最大的数组容量，就取最小的大于需要的容量的容量。
原则就是实现最小扩容。
8，常问：从list里面移除元素
//从下标处移除元素，注意参数是int，如果是integer,会调用第二个方法。
public E remove(int index) {
rangeCheck(index);//边界检查
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;
}
//移除指定元素，快速移除，跳过边界检查并且不返回已删除的值。
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
第一个方法从下标处移除元素，注意参数是int，如果使用integer，会调用第二个方法。
第二个方法移除指定元素，移除的时候也是用的下标移除，但不是调的第一个方法，因为index一定是合法的而且移除的值是用户传进来的。也就是它跳过边界检查并且不返回已删除的值。
重点：list移除只需要调用remove方法，不需要使用循环遍历，迭代器，stream等实现。
9，ConcurrentModificationException
final void checkForComodification() {
if (expectedModCount != ArrayList.this.modCount)
throw new ConcurrentModificationException();
}
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
foreach时，final int expectedModCount = modCount;
modCount已确定且不可修改，而添加移除等方法中会调用checkForComodification方法，所以抛出异常。
10，fail-fast 快速失败
<p><a name="fail-fast">
* The iterators returned by this class's {@link #iterator() iterator} and
* {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:</a>
* if the list is structurally modified at any time after the iterator is
* created, in any way except through the iterator's own
* {@link ListIterator#remove() remove} or
* {@link ListIterator#add(Object) add} methods, the iterator will throw a
* {@link ConcurrentModificationException}. Thus, in the face of
* concurrent modification, the iterator fails quickly and cleanly, rather
* than risking arbitrary, non-deterministic behavior at an undetermined
* time in the future.
Arraylist类73行定义，翻译为
这个类的iterator和listierator方法是快速失败的：如果迭代器被创建，不管何时何地，只要不是调用迭代器自己的remove或add方法，迭代器将抛出一个ConcurrentModificationException。因此如果是并发修改，迭代器会迅速而彻底地失败。翻译的不行，可自行翻译。
11，序列化
transient Object[] elementData;
可见elementData被transient 修饰，也就是不参与序列化，但是如果这个参数都不参与序列化，那反序列化的时候得到的不就是一个空列表吗，所以肯定是参与序列化了，下面看看它怎么被序列化的。
1.首先该类是实现了序列化接口Serializable。默认不序列化transient 属性。
2.看下Serializable接口，56行注释如下。
* Classes that require special handling during the serialization and
* deserialization process must implement special methods with these exact
* signatures:
*
* <PRE>
* private void writeObject(java.io.ObjectOutputStream out)
* throws IOException
* private void readObject(java.io.ObjectInputStream in)
* throws IOException, ClassNotFoundException;
* private void readObjectNoData()
* throws ObjectStreamException;
* </PRE>
翻译：在序列化和反序列化过程中需要特殊处理的类必须实现具有以下确切签名的特殊方法：writeObject，readObject，readObjectNoData。
3.找下看ArrayList类有没有writeObject方法。751行
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
可见确实是序列化了elementData，同时还重复序列化了size，因为s.defaultWriteObject();就包含了size（size没有被transient 修饰）。
4.相同的readObject方法。774行
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
注意：在使用序列化时，一定要加上
private static final long serialVersionUID = 1L;
否则，一旦增加或减少类成员变量个数，在反序列化时导致失败。
12，排序算法sort()
使用归并排序（或者叫合并排序）merge sort
优点：
快速：保证及时运行，
nlog(n)并且在几乎有序的列表上运行的速度明显更快。经验测试表明，它与高度优化的快速排序一样快。通常认为，快速排序比合并排序要快，但它不稳定且不能保证n log(n)性能。稳定：不会对相等元素进行重新排序。如果邮件程序的用户按邮寄日期对收件箱进行排序，然后按发件人对其进行排序，则用户自然希望来自给定发件人的当前连续邮件列表将（仍）按邮寄日期进行排序。仅当第二种情况稳定时，才能保证这一点。
归并排序简例
/**
* 名称：归并排序
* 顺序：从左到右，小到大
* 逻辑：把一个数组分成两半，再分成两半，一直分，直到每一半只有1个元素，
* 然后把分出来的两个只有1个元素的数组排序合并成一个数组，
* 然后继续排序合并直到完成整个排序。
* 注意这里是把下标分段。
* 原则：分段比较
* 例子：假如数组为{8,4,2,7,9,10}
* 先分成{8,4,2}{7,9,10}
* 在分成{8,4}{2}{7,9}{10}
* 在分成{8}{4}{2}{7}{9}{10}
* {8}{4}是一个分出来的，先比较{8}{4},成为{4,8}
* 在与{2}比较,成为{2,4,8}。右边成为{7,9,10},
* 在比较{2,4,8}{7,9,10},
* 拿这个当例子说一下比较过程，上面也是一样的
* 2跟7比，把小2复制到临时数组backup{2}
* 然后4跟7比，把小4复制到backup{2,4}
* 然后8跟7比，把小7复制到backup{2,4,7}
* 然后8跟9比，把小8复制到backup{2,4,7,8}
* 然后发现左边的比完了，没数据了，那就把右边的全都直接复制到backup
* 成为{2,4,7,8,9,10}
*/
public static void mergeSort(int[] a){
int[] backup = new int[a.length];
recMergeSort(backup, 0, a.length-1, a);
}
private static void recMergeSort(int[] backup ,int startIndex,int endIndex,int[] a){
if(startIndex == endIndex){
return ;
}else{
int mid = (startIndex + endIndex)/2 ;
recMergeSort(backup, startIndex, mid, a);
recMergeSort(backup, mid+1, endIndex, a);
merge(backup,startIndex,mid+1,endIndex,a);
}
}
private static void merge(int[] backup ,int startIndex,int midIndex,int endIndex,int[] a){
int j = 0;
int start = startIndex;
int mid = midIndex-1;
int n = endIndex-startIndex+1 ;//当前数组的长度
//下面是排序合并
//当比较的两半都有数据，即下标小于等于这一半的最大下标
while (startIndex<=mid && midIndex<=endIndex) {
if(a[startIndex]<a[midIndex]){
backup[j++] = a[startIndex++];
}else{
backup[j++] = a[midIndex++];
}
}
//当有一半比完了，把剩下没比的放到最后
while (startIndex<=mid) {
backup[j++] = a[startIndex++];
}
//当有一半比完了，把剩下没比的放到最后
while (midIndex<=endIndex) {
backup[j++] = a[midIndex++];
}
//排序合并完复制到原数组的相应段落位置上
for(j=0;j<n;j++){
a[start+j] = backup[j] ;
}
}
快速排序简例
/**
* 名称：快速排序
* 顺序：从小到大
* 逻辑：把数组分成小于最后一个数的一边和大于最后一个数的一边，找到最后一个数的位置。然后被分出来的两边继续这样操作。
* 原则：递归分成大小两边，当两边同时阻塞，互换元素位置。
* 例子：假如数组为{8,4,2,7,9,10,30,32,5,11},长度10
* 分成大于11和小于11的两块
* 左边{8,4,2,7,9,10}遇到30阻塞，右边直接就遇到5阻塞了，把30跟5换位，{8,4,2,7,9,10,5,32,30,11}
* 左边{8,4,2,7,9,10,5}遇到32阻塞，右边{32,30}遇到5阻塞，这时候整个数组都跟11比过一次了
* 把11跟32的位置互换{8,4,2,7,9,10,5,11,30,32}，找到了11的位置，不会再改变。
* 下面继续这样处理11左边，和11右边的。
*/
public static void quickSort(int[] a){
_quickSort(0,a.length-1, a);
}
private static void _quickSort(int left,int right,int[] a){
if(right-left<=0){
return ;
}else{
int lastElement = a[right];
int lastElementFixIndex = parition(left,right,lastElement,a);
//从上面得到的数位置把数组分成两段，递归上面的操作
_quickSort(left, lastElementFixIndex-1, a);
_quickSort(lastElementFixIndex+1, right, a);
}
}
private static int parition(int left,int right,int lastElement,int[] a){
int _left = left -1 ;
int _right = right ;
while(true){
//直到遇到大的数停止
while(a[++_left]<lastElement){}
//直到遇到小的数停止
while(_right>0 && a[--_right]>lastElement){}
//整个数组都处理完了，跳出循环
if(_left>=_right){
break;
}else{
//大的数和小的数位置互换，小的放左边。继续进入while（true）,加_left,减_right，直到break
swap(_left,_right,a);
}
}
//_left>=_right，break时，_left位置的数其实是大于right位置的数，因为他是遇到大的才停止。
//换位置，这个基数找到了自己的位置，且之后不再变化，返回下标
swap(_left,right,a);
return _left ;
}
private static void swap(int index1,int index2,int[] a){
int temp = a[index1] ;
a[index1] = a[index2] ;
a[index2] = temp ;
}