ArrayList源码解读

目录

• 前言
• 类继承关系
• 成员变量解读
• 构造器
• 重要方法
• 迭代器内部实现解读
• 总结

前言

1）本文章的jdk版本为jdk1.8，如果你使用的是其他版本，请参考你的java源码！
2）由于作者水平有限，本文只对部分的方法进行了分析。不足之处，希望大家指出，谢谢
3）如果你对java中的数组还没有理解，可以先学习数组及其在jvm中的存储方式，可以参考下面文章
java中数组在内存中的存放原理讲解

1、继承关系

public class arraylist<e> extends abstractlist<e>     
implements list<e>, randomaccess, cloneable, java.io.serializable

2、成员变量

• private static final int default_capacity = 10;
  arraylist默认的初始容量
  
• private static final object[] empty_elementdata = {};
  默认的空object数组
• private static final object[] defaultcapacity_empty_elementdata = {};
  与默认初始容量对应的object数组
• transient object[] elementdata;
  存放元素的数组
• private int size;
  动态数组的size
  
• private static final int max_array_size = integer.max_value - 8;
  最大的数组size = 0x7ffffff7 = (integer.max_value = 0x7fffffff)-8

3、构造器

//指定初始化容量的构造器，它通过判断int值大小来初始化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);
    }
}    
//默认的
public arraylist() {
this.elementdata = defaultcapacity_empty_elementdata;
}    
   
public arraylist(collection<? extends e> c) {
    elementdata = c.toarray();
    if ((size = elementdata.length) != 0) {
        // c.toarray might (incorrectly) not return object[] (see 6260652)
        /*类型判断，如果elementdata的类型不是object[]数组，则将其
         *复制为object类型的数组，并且elementdata的大小小于size时，多于的位置
         *填入null
        if (elementdata.getclass() != object[].class)
            elementdata = arrays.copyof(elementdata, size, object[].class);
    } else {
        // replace with empty array.
        this.elementdata = empty_elementdata;
    }
} 

4、方法

4.1 public void trimtosize()

 /**
 * arraylist大小整理，在size < elementdata.length 且 size != 0时，
 * elementdata将会被截断为size的长度！！！！
 * elementdata将会被截断为size的长度！！！！
 */
public void trimtosize() {
    modcount++;
    if (size < elementdata.length) {
        elementdata = (size == 0)
          ? empty_elementdata
          : arrays.copyof(elementdata, size);
    }
}
 

4.2 public void ensurecapacity(int mincapacity)及相关私有方法

/**
 *    增加数组的容量的判定，这个操作只有在 mincapacity>minexpand 时，
 * 才能完成操作。
 *    注意下面的三目运算符，minexpand的值取决于
 * 你是否已经在你的arraylist对象中放入了值。
 * @param   mincapacity   the desired minimum capacity
 */
public void ensurecapacity(int mincapacity) {
    int minexpand = (elementdata != defaultcapacity_empty_elementdata)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. it's already
        // supposed to be at default size.
        : default_capacity;

    if (mincapacity > minexpand) {
        ensureexplicitcapacity(mincapacity);
    }
}

private void ensureexplicitcapacity(int mincapacity) {
    modcount++;

    // overflow-conscious code
    if (mincapacity - elementdata.length > 0)
        grow(mincapacity);
}

/* 核心方法，动态数组的增长实现
 * 一般情况按oldcapacity的半数增长，但最大的size不能大于integer.max_value
 * 原数组会被copy到一个新的数组(size=newcapacity)中，多于的位置填充null
 */
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;
}

grow()流程图：

4.3 public int indexof(object o)

//返回指定元素第一次出现的索引，无则返回 -1
public int indexof(object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            //如果使用 o.equals()则会抛出空指针异常(null.equals()是错的)
            if (elementdata[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            //object类的equals90直接调用“==”
            if (o.equals(elementdata[i]))
                return i;
    }
    return -1;
}

4.4 public int lastindexof(object o)

//返回指定元素最后一次出现的索引，无则返回 -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;
}

4.6 add方法

//（1）在尾部添加
public boolean add(e e) {
    //确定是否需要扩容
    ensurecapacityinternal(size + 1);  // increments modcount!!
    elementdata[size++] = e;
    return true;
}

//（2）在指定位置添加
public void add(int index, e element) {
    //判定是否索引越界
    rangecheckforadd(index);
    //确定是否需要扩容
    ensurecapacityinternal(size + 1);  // increments modcount!!

    //从指定数组的指定开始位置到指定结束位置复制一个数组，在本节末尾给出了该方法的详细解释
    system.arraycopy(elementdata, index, elementdata, index + 1,
                     size - index);

    //将index位置的原element替换为新的element
    elementdata[index] = element;
    size++;
}

//（3）两个索引越界检查方法
private void rangecheck(int index) {
    if (index >= size)
        throw new indexoutofboundsexception(outofboundsmsg(index));
}

private void rangecheckforadd(int index) {
    if (index > size || index < 0)
        throw new indexoutofboundsexception(outofboundsmsg(index));
}
//索引越界信息
private string outofboundsmsg(int index) {
    return "index: "+index+", size: "+size;
}

public static void arraycopy(object src, int srcpos,object dest, int destpos,int length)

• src - 源数组。
• srcpos - 源数组中的起始位置。
• dest - 目标数组。
• destpos - 目标数据中的起始位置。
• length - 要复制的数组元素的数量。

从指定源数组中复制一个数组，复制从指定的位置开始，到目标数组的指定位置结束。从 src 引用的源数组到 dest 引用的目标数组，数组组件的一个子序列被复制下来。被复制的组件的编号等于 length 参数。源数组中位置在 srcpos 到 srcpos+length-1 之间的组件被分别复制到目标数组中的 destpos 到 destpos+length-1 位置。
如果参数 src 和 dest 引用相同的数组对象，则复制的执行过程就好像首先将 srcpos 到 srcpos+length-1 位置的组件复制到一个带有 length 组件的临时数组，然后再将此临时数组的内容复制到目标数组的 destpos 到 destpos+length-1 位置一样。

这样一来，arraylist的插入就很好理解了，先将 __index 及其后__面的所有元素复制一份，然后从 index+1 处到destpos+length-1；然后将 index 处的元素替换为新的元素即可！。

4.7 remove方法

在理解了add方法之后，remove方法就很好理解了。

//移除指定位置的元素
public e remove(int index) {
    rangecheck(index);

    modcount++;
    e oldvalue = elementdata(index);

    //所要移除元素的位置之所以不用 index - 1，
    //是因为rangcheck()方法中是判断 index>size，而不是>=
    int nummoved = size - index - 1;
    if (nummoved > 0)
        system.arraycopy(elementdata, index+1, elementdata, index,
                         nummoved);
    //将最后一个元素置null，方便垃圾回收器回收
    //至于为什么置null能方便gc回收，请阅读“对象生命周期”和jvm垃圾回收机制的相关书籍和文章
    elementdata[--size] = null; // clear to let gc do its work

    return oldvalue;
}

//注意for循环，是移除所有满足条件的obj
public boolean remove(object o) {
    //空判断！集合框架中有大量空判断，自己在编程过程中也要注意空判断，
    //以免抛出“空指针异常”
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementdata[index] == null) {
                //不进行索引越界检查的快速remove
                fastremove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementdata[index])) {
                fastremove(index);
                return true;
            }
    }
    return false;
}

//跳过边界检查的私有移除方法，并且不返回删除的值。
//相比 remove 少了检查，和返回值，一个对象的创建
private void fastremove(int index) {
    modcount++;
    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
} 

4.8 两种toarray

public object[] toarray() {
    return arrays.copyof(elementdata, size);
}

@suppresswarnings("unchecked")
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;
}

此方法担当基于数组的 api 和基于 collection 的 api 之间的桥梁。

4.9 public object clone()

//返回这个arraylist实例的一个浅副本。（元素本身没有被复制。）
//它的modcount将会置0
//todo 不懂对象克隆的原理
public object clone() {
    try {
        arraylist<?> v = (arraylist<?>) super.clone();
        v.elementdata = arrays.copyof(elementdata, size);
        v.modcount = 0;
        return v;
    } catch (clonenotsupportedexception e) {
        // this shouldn't happen, since we are cloneable
        throw new internalerror(e);
    }
}

4.10 其他增删查改操作类似

5、迭代器内部类实现

未完待续...

6、总结

1. 适用范围
   • 和刚学习使用它时一样、arraylist有其特殊的应用场景，与linkedlist相对应。其优点是随机读取，缺点是插入元素时需要移动大量元素，效率不太高。
2. 关于 null 判断
   • 在写这篇文章前，自己也试着在 leetcode 上自己实现链表和数组，但是老报空指针异常。估计也是因为没有进行 null判断 引起的。
3. 对象置null，方便 gc 回收垃圾