ArrayList源码解读

程序员文章站 2022-10-15 23:04:05

目录 + 前言 + 类继承关系 + 成员变量解读 + 构造器 + 重要方法 + 迭代器内部实现解读 + 总结前言 1）本文章的JDK版本为JDK1.8，如果你使用的是其他版本，请参考你的Java源码！ 2）由于作者水平有限，本文只对部分的方法进行了分析。不足之处，希望大家指出，谢谢 3）如果你对J ......

前言

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()流程图：
ArrayList源码解读

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、总结

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

上一篇： iOS开发之使用addChildViewController：给控制器添加子控制器

下一篇：百家号赚钱攻略：新手怎么注册运营来获取收益？

ArrayList源码解读

目录

前言

1、继承关系

2、成员变量

3、构造器

4、方法

4.1 `public void trimtosize()`

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

4.3 `public int indexof(object o)`

4.4 `public int lastindexof(object o)`

4.6 add方法

4.7 remove方法

4.8 两种`toarray`

4.9 `public object clone()`

4.10 其他增删查改操作类似

5、迭代器内部类实现

6、总结

jQuery实现经典的网页3D轮播图封装功能【附源码下载】

解读Python编程中的命名空间与作用域

分布式定时任务(xxl-job执行器的启动过程源码分析)

详细解读Python中解析XML数据的方法

某度贴吧验证码识别(源码)

Android透明化和沉浸式状态栏实践及源码分析

Android TextView实现点击显示全文与隐藏功能（附源码）

java中匿名内部类解读分析

阅读EnumSet抽象类源码

java+SQL server2008学生信息管理系统源码

ArrayList源码解读

目录

前言

1、继承关系

2、成员变量

3、构造器

4、方法

4.1 public void trimtosize()

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

4.3 public int indexof(object o)

4.4 public int lastindexof(object o)

4.6 add方法

4.7 remove方法

4.8 两种toarray

4.9 public object clone()

4.10 其他增删查改操作类似

5、迭代器内部类实现

6、总结

jQuery实现经典的网页3D轮播图封装功能【附源码下载】

解读Python编程中的命名空间与作用域

分布式定时任务(xxl-job执行器的启动过程源码分析)

详细解读Python中解析XML数据的方法

某度贴吧验证码识别(源码)

Android透明化和沉浸式状态栏实践及源码分析

Android TextView实现点击显示全文与隐藏功能（附源码）

java中匿名内部类解读分析

阅读EnumSet抽象类源码

java+SQL server2008学生信息管理系统源码

4.1 `public void trimtosize()`

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

4.3 `public int indexof(object o)`

4.4 `public int lastindexof(object o)`

4.8 两种`toarray`

4.9 `public object clone()`