基于java10.1
零、前言
如果想读读源码测试功力，或读读源码修养身心，或读读源码满足自虐倾向，我建议第一个类是：ArrayList
第一、常用----所以用法比较熟悉，看完源码你也会更明白如何去用
第二、相对简单----1595行代码，刨去注释的一大堆也没有太多，还是hold的住的
总得来说ArrayList源码最主要的是对System.arraycopy的理解，很多操作都是基于此
void arraycopy( Object src, //源数组
int srcPos,//源数组中的起始位置
Object dest,//目标数组
int destPos,//目的地数据中的起始位置
int length);//要复制的数组元素的数量
一.继承与实现：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
image
二、成员变量
//serialVersionUID来验证版本一致性
private static final long serialVersionUID = 8683452581122892189L;
//默认列表的容量
private static final int DEFAULT_CAPACITY = 10;
//一个空的Object数组--空数组(本文中别名：空1)
private static final Object[] EMPTY_ELEMENTDATA = {};
//另一个空的Object数组--默认容量空数组(本文中别名：空2)
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//列表中盛放的数组
transient Object[] elementData; //非私有来简化内部类访问
//内部元素个数
private int size;
//最大数组尺寸，这里是Integer最大值-8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
二.构造方法
1.构造方法1：无参构造
使用无参构造ArrayList,在未添加元素前,内部数组的长度是为0。在添加第一个元素时，才会扩容到10
//无参构造：elementData=空2
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2.构造方法2：一参构造：指定初始容量
//入参initialCapacity：初始容量
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {//入参>0有效
//创建长度为入参的Object数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {//入参<0异常
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
}
}
3.构造方法3：用已有Collection对象，创建ArrayList
// 入参c：已有的容器对象
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();//传入的集合转化为数组并赋值给elementData
//获取数组长度赋值值给size，当size不为0
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
//Arrays.copyOf见：A--01
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {//入参 = 0 时：elementData=空1
this.elementData = EMPTY_ELEMENTDATA;
}
}
A--01:java.util.Arrays#copyOf(U[], int, java.lang.Class<? extends T[]>)
将一个数组拷贝指定长度，变为另一种类型的数组
@param <U> 初始数组类型
@param <T> 返回数组类型
@param original 被拷贝数组
@param newLength 拷贝的长度
@param newType 返回的数组类型
@return
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
return copy;
}
三.常用方法的源码分析
1.添加: 代号m1
m1 : java.util.ArrayList#add(E)
modCount:父类AbstractList中的protected变量,每次添加和移除都会+1，记录所有的修改次数
作用：在Iterator使用时校验期望修改的次数与真实修改次数是否相同
*@param e 添加的元素
public boolean add(E e) {
modCount++;//列表在结构上修改的次数
add(e, elementData, size);//此处调用三参的添加方法：见：m1-1
return true;//返回是否添加成功
}
m1-1 : java.util.ArrayList#add(E, java.lang.Object[], int)
*@param e 添加的元素
*@param elementData 数组
*@param s 索引位置
private void add(E e, Object[] elementData, int s) {
//要添加的索引为等于数组的长度时进行扩容操作
if (s == elementData.length)
elementData = grow();//grow()返回一个扩容后的数组：见：m-1-1
//将传入的元素放到数组的最后一位
elementData[s] = e;(注：由于数组标号从零开始，新数组长度s+1,最后一个元素下标号为s)
size = s + 1;//将成员变量size+1
}
m-1-1 : java.util.ArrayList#grow()
扩容操作
private Object[] grow() {
return grow(size + 1);//调用了一参的grow()方法
}
*@param minCapacity 最小容量
private Object[] grow(int minCapacity) {
//newCapacity(minCapacity)扩容核心操作：见m-1-1-1
return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));
}
m-1-1-1：java.util.ArrayList#newCapacity
扩容核心操作: 最小容量size+1,旧容量:数组长，新容量：1.5倍旧容量
拿教室举例：minCapacity就是班级学生数量+1，oldCapacity就是扩建前的座位数，newCapacity就是扩建后的座位数
*@param minCapacity 最小容量
private int newCapacity(int minCapacity) {
//oldCapacity：旧容量 newCapacity：1.5倍旧容量
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//即+50%
if (newCapacity - minCapacity <= 0) { //新容量小于等于最小容量
//如果elementData=空2，扩容到DEFAULT_CAPACITY(即10)，这就是分空1和空2的目的
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
//新容量大于最小容量时， newCapacity没达到最大尺寸返回newCapacity，否则hugeCapacity(minCapacity)
return (newCapacity - MAX_ARRAY_SIZE <= 0) ? newCapacity : hugeCapacity(minCapacity);
}
//minCapacity大于数组最大尺寸，返回整型的最大值，否则返回数组最大尺寸
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE)? Integer.MAX_VALUE: MAX_ARRAY_SIZE;
}
2.定位添加：代号：m2
m2 : java.util.ArrayList#add(int, E)
* @param 插入的索引位置
* @param 插入的元素
public void add(int index, E element) {
rangeCheckForAdd(index);//m2-1:检查索引合法性
modCount++;
final int s;//局部变量，记录方法执行前size值
Object[] elementData//局部变量，记录方法执行前elementData数组
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();//扩容1.5倍
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);//m2-2：核心方法
elementData[index] = element;
size = s + 1;
}
m2-1 ：java.util.ArrayList#rangeCheckForAdd
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)//索引在(0,size)之外报异常
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
m2-2 ：java.util.ArrayList#rangeCheckForAdd
//将[源数组src]从[指定位置srcPos]选取连续[长度length]个元素复制到[目标数组dest]的[指定位置destPos]。
public static native
void arraycopy( Object src, //源数组
int srcPos,//源数组中的起始位置
Object dest,//目标数组
int destPos,//目的地数据中的起始位置
int length);//要复制的数组元素的数量
arraycopy.png
3.添加所有：代号m3
* @param 已有的容器对象
* @return 列表是否已被修改
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();//将容器对象转化为数组a
modCount++;//修改次数+1
int numNew = a.length;//临时变量numNew记录a的长度
if (numNew == 0)//a的长度为0
return false;//说明列表未被修改
Object[] elementData;//临时变量elementData:数组
final int s;//临时变量s：数组长度
//加入的元素大于数组容积和当前元素个数之差，也就是放入这些元素后会占满
if (numNew > (elementData = this.elementData).length - (s = size))
//扩容
elementData = grow(s + numNew);
//将a数组，从0开始，拷贝numNew个元素到elementData数组的s索引处
System.arraycopy(a, 0, elementData, s, numNew);
size = s + numNew;//维护size
return true;////说明列表被修改
}
4.定点添加所有：代号m4
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);//见：m2-1
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);//至此同上m3
int numMoved = s - index;//添加的位置之后的元素个数
if (numMoved > 0)//说明index在元素个数之内
//将elementData数组，从index开始，拷贝numMoved个元素到elementData数组的index + numNew索引处
//相当于挪一下索引位后的元素
System.arraycopy(elementData, index,
elementData, index + numNew,
numMoved);
//将a数组，从0开始，拷贝numNew个元素到elementData数组的index索引处
System.arraycopy(a, 0, elementData, index, numNew);
size = s + numNew;
return true;
}
5.根据索引删除：代号m5
m5 : java.util.ArrayList#remove(int)
public E remove(int index) {
Objects.checkIndex(index, size);//检查索引合法性
final Object[] es = elementData;//将集合赋予临时变量es
E oldValue = (E) es[index];//临时变量记录删除值
fastRemove(es, index);//m5-1:删除的核心方法
return oldValue;//返回删除的值
}
m5-1 : java.util.ArrayList#fastRemove
/**
* 私有的移除方法：跳过边界检查并且不反会移除的值
*/
private void fastRemove(Object[] es, int i) {
modCount++;//修改次数+1
final int newSize;//新尺寸：元素总量-1
if ((newSize = size - 1) > i)//索引在元素总量-1之内
//将es数组，从i + 1开始，拷贝size - (i+1)个元素到es数组的i索引处
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
6.移除指定元素
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
//寻找到第一次出现的指定元素索引位置
fastRemove(es, i);//m5-1:删除的核心方法
return true;
}
7.移除所有指定元素：代号m7
public boolean removeAll(Collection<?> c) {
return batchRemove(c, false, 0, size);//batchRemove见:m7-1
}
m7-1:java.util.ArrayList#batchRemove
boolean batchRemove(Collection<?> c, boolean complement,
final int from, final int end) {
Objects.requireNonNull(c);
final Object[] es = elementData;//es变量记录当前数组
int r;
// Optimize for initial run of survivors
for (r = from;; r++) {
if (r == end)//没有找到该元素
return false;
if (c.contains(es[r]) != complement)//包含但还没有全部扫描
break;
}
int w = r++;
try {
for (Object e; r < end; r++)
if (c.contains(e = es[r]) == complement)
es[w++] = e;
} catch (Throwable ex) {
System.arraycopy(es, r, es, w, end - r);
w += end - r;
throw ex;
} finally {
modCount += end - w;
//shiftTailOverGap:见m7-1-1
shiftTailOverGap(es, w, end);
}
return true;
}
7-1-1.范围移除
private void shiftTailOverGap(Object[] es, int lo, int hi) {
//将es数组，从hi开始，拷贝size - hi个元素到es数组的lo索引处
System.arraycopy(es, hi, es, lo, size - hi);
for (int to = size, i = (size -= hi - lo); i < to; i++)
es[i] = null;//将移除的元素置空
}
8.获取元素：代号m8
m8 : java.util.ArrayList#get
/**
* 返回列表中指定位置的元素
*/
public E get(int index) {
//m8-1:检查索引是否合法(1.9开始有)
Objects.checkIndex(index, size);
return elementData(index);//m8-2
}
m8-1 : java.util.Objects#checkIndex
public static
int checkIndex(int index, int length) {
return Preconditions.checkIndex(index, length, null);//m8-1-1
}
m8-1-1 : jdk.internal.util.Preconditions#checkIndex
//判断索引值是否在(0,length)
public static <X extends RuntimeException>
int checkIndex(int index, int length,
BiFunction<String, List<Integer>, X> oobef) {
if (index < 0 || index >= length)
throw outOfBoundsCheckIndex(oobef, index, length);//这就是经常遇到的角标越界
return index;
}
m8-2 : java.util.ArrayList#elementData
E elementData(int index) {
return (E) elementData[index];//返回数组在索引上的值
}
9.修改元素
public E set(int index, E element) {
//检查索引是否越界
Objects.checkIndex(index, size);
//记录旧值
E oldValue = elementData(index);
//设置新值
elementData[index] = element;
//返回旧值
return oldValue;
}
四、其他方法
1.获取集合大小：java.util.ArrayList#size
public int size() {
return size;
}
2.是否非空：java.util.ArrayList#isEmpty
public boolean isEmpty() {
return size == 0;
}
3.清空：java.util.ArrayList#clear
public void clear() {
modCount++;//操作数+1
final Object[] es = elementData;//es存储当前数组
for (int to = size, i = size = 0; i < to; i++)
es[i] = null;//全部置空
}
4.元素出现的索引位
indexOf(el) 元素第一次出现的索引位置
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;//从头开始找，直到相等时，返回i
}
return -1;//找不到返回-1
}
lastIndexOf(el) 元素最后一次出现的索引位置
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;//从后往前找，直到相等时，返回i
}
return -1;//找不到返回-1
}
5.是否包含某元素
public boolean contains(Object o) {
return indexOf(o) >= 0;//找到有索引就ok
}
4.转换为数组：java.util.ArrayList#toArray(T[])
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
public <T> T[] toArray(T[] a) {
if (a.length < size)
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
五、迭代器：
1.Iterator上一篇讲的挺详细：见--Java容器源码攻坚战--第一战：Iterator
2.这里主要讲ArrayList特有的私人迭代器：ListIterator
可以认为是Iterator的升级版，继承自Iterator，而且多了一些操作
ListIterator
public interface ListIterator<E> extends Iterator<E> {
boolean hasNext();//是否有下一元素
E next();//下一元素
boolean hasPrevious();//是否有前一元素
E previous();//前一元素
int nextIndex();//下一个元素索引
int previousIndex();//前一个元素索引
void remove();//移除
void set(E e);//设置
void add(E e);//添加
}
public ListIterator<E> listIterator() {
return new ListItr(0);
}
public ListIterator<E> listIterator(int index) {
rangeCheckForAdd(index);
return new ListItr(index);
}
ListIterator实现类
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {//构造函数传入索引值
super();
cursor = index;//游标处于索引位
}
public boolean hasPrevious() {
return cursor != 0;//游标不为0说明有前元素
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
//索引为游标-1
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
//elementData储存当前数组
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;//游标-1
return (E) elementData[lastRet = i];//返回元素
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
//设置最后返回的那个元素索引
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
//在最后返回的那个元素索引处添加元素
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
就酱紫，ArrayList还有个SubList没有接触过，暂时就不看了
后记：捷文规范
1.本文成长记录及勘误表
| 项目源码 | 日期 | 备注 |
|---|---|---|
| V0.1--无 | 2018-10-2 | Java容器源码攻坚战--第二战：ArrayList |
| V0.2--无 | - | - |
2.更多关于我
| 笔名 | 微信 | 爱好 | |
|---|---|---|---|
| 张风捷特烈 | 1981462002 | zdl1994328 | 语言 |
| 我的github | 我的简书 | 我的CSDN | 个人网站 |
3.声明
1----本文由张风捷特烈原创,转载请注明
2----欢迎广大编程爱好者共同交流
3---个人能力有限，如有不正之处欢迎大家批评指证，必定虚心改正
4----看到这里，我在此感谢你的喜欢与支持
网友评论