JavaSE7 ArrayList源码 上
浏览数：14 /
时间：2015年06月08日
这是jre7版本的
public class ArrayList<E>
extends AbstractList<E>//这个 extends AbstractCollection<E> implements List<E>
implements List<E>, RandomAccess, Cloneable, Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* 看下面这两个私有属性，就知道ArrayList实际上就是一个数组
* 其（数组、ArrayList）数据结构就是一个简单的线性序列
*/
//数组elementData 存储ArrayList的所有数据
private transient Object[] elementData;
//size<=elementData.length,两者没什么特别关系
//size是数组elementData中元素（E） 的个数
private int size;
private static final int MAX_ARRAY_SIZE = 2147483639;
/**
* 构造方法1
* 可以初始化数组大小
* 例：ArrayList<E> array = new ArrayList<E>(10000);
* 这时候size=0,但是数组的容量是10000
*/
public ArrayList(int paramInt)
{
if (paramInt < 0) {
throw new IllegalArgumentException("Illegal Capacity: " + paramInt);
}
this.elementData = new Object[paramInt];
}
/**
* 构造方法2
* 默认构造方法，初始化数组大小是10,感觉好小啊
*/
public ArrayList()
{
//表示调用构造方法1
this(10);
}
/**
* 构造方法3
* 可以放一个实现Collection接口的集合进去
*/
public ArrayList(Collection<? extends E> paramCollection)
{
// 1.将集合转换成数组，elementData指向这个数组
this.elementData = paramCollection.toArray();
// 2.设置size值
this.size = this.elementData.length;
// 3.判断ele..是不是Object数组,不是的话创建一个，将内容（基本类型的值，对象的引用）copy进新数组中，返回
if (this.elementData.getClass() != [Ljava.lang.Object.class) {
this.elementData = Arrays.copyOf(this.elementData, this.size, [Ljava.lang.Object.class);
}
}
???
?
?下面看一下，构造方法3中的第一步（假设传进来的是一个ArrayList）和第三步。
/**
* ArrayList实现的 Collection接口中toArray()方法
*/
public Object[] toArray()
{
return Arrays.copyOf(this.elementData, this.size);
}
/**
* 在Arrays类中找到的copyOf的方法
*/
public static <T> T[] copyOf(T[] paramArrayOfT, int paramInt)
{
return (Object[])copyOf(paramArrayOfT, paramInt, paramArrayOfT.getClass());
}
/**
* 直接看这个吧，上面构造方法3的第三步调用的也是这个方法
*/
public static <T, U> T[] copyOf(U[] paramArrayOfU, int paramInt, Class<? extends T[]> paramClass)
{
//根据给定的paramClass数组类型，生成一个大小paramInt的新数组
Object[] arrayOfObject =
//三目运算
paramClass == [Ljava.lang.Object.class ?
//构造方法3的第三步走的这里
(Object[])new Object[paramInt] :
//Array.newInstance 是native的，看不到了
(Object[])Array.newInstance(paramClass.getComponentType(), paramInt);
//这个也是 native方法，x = Math.min(paramArrayOfU.length, paramInt)
//复制paramArrayOfU[0~x]内容到arrayOfObjec[0~x]中，用这个操作数组还是很爽的
System.arraycopy(paramArrayOfU, 0, arrayOfObject, 0, Math.min(paramArrayOfU.length, paramInt));
return arrayOfObject;
}
?
?
??其实一般的构造方法3，第三步都会走。
ArrayList<String> array = new ArrayList<String>(Arrays.asList("a","b"));
//对应构造方法3的第一步
Object[] elementData = Arrays.asList("a","b").toArray();
System.err.println(elementData.getClass());//输出class [Ljava.lang.String;
??
?
下面继续源码:对数组进行扩容
/**
* 给数组瘦身，释放资源，确定数组大小不会改变时用这个
* 生成一个新数组大小与元素个数一样
*/
public void trimToSize()
{
//记录对arrayList的操作次数？不知道有什么用处
this.modCount += 1;
int i = this.elementData.length;
if (this.size < i) {
//上面介绍过了
this.elementData = Arrays.copyOf(this.elementData, this.size);
}
}
/**
* 手动给数组扩容，生成一个容量不小于paramInt数组，然后将内容copy进去
*/
public void ensureCapacity(int paramInt)
{
if (paramInt > 0) {
ensureCapacityInternal(paramInt);
}
}
/**
* 给定数值不能比当前数组容量小。
*/
private void ensureCapacityInternal(int paramInt)
{
this.modCount += 1;
if (paramInt - this.elementData.length > 0) {
grow(paramInt);
}
}
/**
* 执行扩容
*/
private void grow(int paramInt)
{
int i = this.elementData.length;
//自己会根据当前容量算出一个扩容值，跟给定值比较选择最大的
//移位操作符>> 参考：http://flyouwith.iteye.com/blog/2163032
int j = i + (i >> 1);
if (j - paramInt < 0) {
j = paramInt;
}
if (j - 2147483639 > 0) {
//限定数组最大的容量不能超过多少
j = hugeCapacity(paramInt);
}
//继续copy
this.elementData = Arrays.copyOf(this.elementData, j);
}
/**
* 最大数值能不能超过Integer.MAX_VALUE
* 2147483647
*/
private static int hugeCapacity(int paramInt)
{
if (paramInt < 0) {
throw new OutOfMemoryError();
}
return paramInt > 2147483639 ? Integer.MAX_VALUE : 2147483639;
}
?下面内容是一些基本方法
/**
* 返回数组中元素个数
*/
public int size()
{
return this.size;
}
/**
* 是否只有一副皮囊
*/
public boolean isEmpty()
{
return this.size == 0;
}
/**
* 是否包含制定paramObject
*/
public boolean contains(Object paramObject)
{
return indexOf(paramObject) >= 0;
}
/**
* paramObject 在数组中的一次出现的位置
* 通过对象的equals比较
*/
public int indexOf(Object paramObject)
{
int i;
if (paramObject == null) {
for (i = 0; i < this.size; i++) {
if (this.elementData[i] == null) {
return i;
}
}
} else {
for (i = 0; i < this.size; i++) {
if (paramObject.equals(this.elementData[i])) {
return i;
}
}
}
return -1;
}
/**
* paramObject 在数组中最后一次出现的位置
* 从后面开始循环
* 通过对象的equals比较
*/
public int lastIndexOf(Object paramObject)
{
int i;
if (paramObject == null) {
for (i = this.size - 1; i >= 0; i--) {
if (this.elementData[i] == null) {
return i;
}
}
} else {
for (i = this.size - 1; i >= 0; i--) {
if (paramObject.equals(this.elementData[i])) {
return i;
}
}
}
return -1;
}
/**
* 复制
* 数组存基本类型的值，对象的引用。
* 所以copy的不过是引用，都指向一个对象
*/
public Object clone()
{
try
{
ArrayList localArrayList = (ArrayList)super.clone();
localArrayList.elementData = Arrays.copyOf(this.elementData, this.size);
localArrayList.modCount = 0;
return localArrayList;
}
catch (CloneNotSupportedException localCloneNotSupportedException)
{
throw new InternalError();
}
}
/**
* 转换成数组，对象存引用
*/
public Object[] toArray()
{
return Arrays.copyOf(this.elementData, this.size);
}
/**
* 新建一个数组，放到这里拷贝ArrayList中内容
*/
public <T> T[] toArray(T[] paramArrayOfT)
{
//如果给定数组容量小于size ，则生成一个大小是size的数组，然后把内容copy进去
if (paramArrayOfT.length < this.size) {
return (Object[])Arrays.copyOf(this.elementData, this.size, paramArrayOfT.getClass());
}
//否则直接copy，上面有介绍这个方法的含义
System.arraycopy(this.elementData, 0, paramArrayOfT, 0, this.size);
if (paramArrayOfT.length > this.size) {
paramArrayOfT[this.size] = null;
}
return paramArrayOfT;
}
/**
* 返回数组指定位置的元素
*/
E elementData(int paramInt)
{
return this.elementData[paramInt];
}
/**
* 返回指定位置的元素
*/
public E get(int paramInt)
{
rangeCheck(paramInt);//检核是否越界
return elementData(paramInt);
}
/**
* 替换指定位置的元素，返回被替换元素
*/
public E set(int paramInt, E paramE)
{
rangeCheck(paramInt);//检核是否越界
Object localObject = elementData(paramInt);
this.elementData[paramInt] = paramE;
return localObject;
}
/**
* 在末尾添加元素。
* 第一步上面有介绍这个方法。扩容
* 注意：size加1
*/
public boolean add(E paramE)
{
ensureCapacityInternal(this.size + 1);
this.elementData[(this.size++)] = paramE;
return true;
}
/**
* 指定位置添加元素，从指定位置开始后面元素统一后移一位
* 这里不是用的for循环来移位，而是copy，即使这样也比LinkedList慢好多
* 这个如果用for循环的话时间复杂度是O(this.size - paramInt) copy应该是比这小的
* 但是肯定比LinkedList 的O(1) 要大的多
* 注意：size加1
*/
public void add(int paramInt, E paramE)
{
rangeCheckForAdd(paramInt);//检核是否越界
ensureCapacityInternal(this.size + 1);
System.arraycopy(this.elementData, paramInt, this.elementData, paramInt + 1, this.size - paramInt);
this.elementData[paramInt] = paramE;
this.size += 1;
}
/**
* 跟上面性质是一样的。把删除位置后面的元素统一向前移动一位
* 比LinkedList慢
* 注意：size减1
*/
public E remove(int paramInt)
{
rangeCheck(paramInt);//检核是否越界
this.modCount += 1;
Object localObject = elementData(paramInt);
int i = this.size - paramInt - 1;
if (i > 0) {
System.arraycopy(this.elementData, paramInt + 1, this.elementData, paramInt, i);
}
this.elementData[(--this.size)] = null;
return localObject;
}
/**
* 删除对象，现查到对象在集合中的位置
* 比LinkedList慢
*/
public boolean remove(Object paramObject)
{
int i;
if (paramObject == null) {
for (i = 0; i < this.size; i++) {
if (this.elementData[i] == null)
{
fastRemove(i);
return true;
}
}
} else {
for (i = 0; i < this.size; i++) {
if (paramObject.equals(this.elementData[i]))
{
fastRemove(i);
return true;
}
}
}
return false;
}
/**
* 因为是在集合众找到的位置。所以不需要检核，直接删除
*/
private void fastRemove(int paramInt)
{
this.modCount += 1;
int i = this.size - paramInt - 1;
if (i > 0) {
System.arraycopy(this.elementData, paramInt + 1, this.elementData, paramInt, i);
}
this.elementData[(--this.size)] = null;
}
/**
* 清空，通过for循环
*/
public void clear()
{
this.modCount += 1;
for (int i = 0; i < this.size; i++) {
this.elementData[i] = null;
}
this.size = 0;
}
/**
* 添加一个集合到当前集合后面
* 先把要添加的集合转变成数组，然后对this数组扩容，copy到this数组中
* 比LinkedList慢
*/
public boolean addAll(Collection<? extends E> paramCollection)
{
Object[] arrayOfObject = paramCollection.toArray();
int i = arrayOfObject.length;
ensureCapacityInternal(this.size + i);
System.arraycopy(arrayOfObject, 0, this.elementData, this.size, i);
this.size += i;
return i != 0;
}
/**
* 在指定位置插入集合，
* 先将扩容，然后移位，之后把内容copy进来
* 比LinkedList慢
*/
public boolean addAll(int paramInt, Collection<? extends E> paramCollection)
{
rangeCheckForAdd(paramInt);//检核是否越界
Object[] arrayOfObject = paramCollection.toArray();
int i = arrayOfObject.length;
ensureCapacityInternal(this.size + i);
int j = this.size - paramInt;
if (j > 0) {
System.arraycopy(this.elementData, paramInt, this.elementData, paramInt + i, j);
}
System.arraycopy(arrayOfObject, 0, this.elementData, paramInt, i);
this.size += i;
return i != 0;
}
/**
* 这是protected的不能用。。
* remove区间的内容
* 先把paramInt2后的内容copy到paramInt1后面
* 然后把后面paramInt2-paramInt1位置的元素清空
*/
protected void removeRange(int paramInt1, int paramInt2)
{
this.modCount += 1;
int i = this.size - paramInt2;
System.arraycopy(this.elementData, paramInt2, this.elementData, paramInt1, i);
int j = this.size - (paramInt2 - paramInt1);
while (this.size != j) {
this.elementData[(--this.size)] = null;
}
}
/**
* 检核越界
*/
private void rangeCheck(int paramInt)
{
if (paramInt >= this.size) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(paramInt));
}
}
/**
* 检核越界
*/
private void rangeCheckForAdd(int paramInt)
{
if ((paramInt > this.size) || (paramInt < 0)) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(paramInt));
}
}
/**
* 异常信息
*/
private String outOfBoundsMsg(int paramInt)
{
return "Index: " + paramInt + ", Size: " + this.size;
}
??
?
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
