欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

ArrayList实现原理(JDK1.8)

程序员文章站 2022-05-31 22:04:11
ArrayList实现原理(JDK1.8) ArrayList 继承于AbstractList,实现了List接口,其实AbstractList 已经实现过List接口,这里重复实现使得接口功能更加清晰,JDK中很多类都是如此。 其中Cloneable接口是克隆标记接口,Serializable序列 ......

arraylist实现原理(jdk1.8)

ArrayList实现原理(JDK1.8)

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

arraylist 继承于abstractlist,实现了list接口,其实abstractlist 已经实现过list接口,这里重复实现使得接口功能更加清晰,jdk中很多类都是如此。

其中cloneable接口是克隆标记接口,serializable序列化标记接口,需要clone和序列化功能必须实现这两个接口,而randomaccess,单纯是一个标志接口 ,该接口表示该类支持快速随机访问,且在循环遍历时for循环的方式会优于用迭代器。

1.成员变量

   // 默认初始容量
   private static final int default_capacity = 10;

   // 空数组实例,初始容量为0或者传入集合为空集合(不是null)时使用
   private static final object[] empty_elementdata = {};
   
   // 空数组示例,无参构造时使用
   private static final object[] defaultcapacity_empty_elementdata = {};
   
   // arraylist内部数据容器
   transient object[] elementdata; // non-private to simplify nested class access
   
   // 实际元素数量
   private int size;

在arraylist中,主要有五个成员变量。default_capacity表示初始容量大小,即在我们初始化arraylist时不指定容量大小, 默认容量将会是10,object[] elementdata 则是arraylist内部实际存储对象的容易,也就是我们常说的arraylist是数组实现的。

在1.8中,空数组分为了两类情况,empty_elementdata 与 defaultcapacity_empty_elementdata,在标记空数组的时候区分了不同的情况。

2.构造方法

arraylist有三个构造方法,指定容量的arraylist(int initialcapacity) ,无参构造arraylist() 以及传入集合的arraylist(collection<? extends e> c)。

    public arraylist() {
        this.elementdata = defaultcapacity_empty_elementdata;
    }

最简单的莫过于无参构造,直接赋值为空数组defaultcapacity_empty_elementdata。其实对于常说的默认容量10,是在第一次添加元素调用add()方法时处理的,并不是构造方法中。

    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);
        }
    }

对于传入容量的构造方法,当传入参数 > 0时,直接初始化对应容量的数组,参数类型为int,也即arraylist的最大初始容量不能超过integer.max_value,事实上arraylist的最大容量也只能是integer.max_value。而初始容量传入0,会赋值为空数组empty_elementdata。如果 < 0,这个显然的不允许了,直接illegalargumentexception

    public arraylist(collection<? extends e> c) {
        elementdata = c.toarray();
        if ((size = elementdata.length) != 0) {
            // c.toarray might (incorrectly) not return object[] (see 6260652)
            if (elementdata.getclass() != object[].class)
                elementdata = arrays.copyof(elementdata, size, object[].class);
        } else {
            // replace with empty array.
            this.elementdata = empty_elementdata;
        }
    }

集合构造时,没有进行null校验,也就是说如果传入null,直接就会npe异常。集合构造的逻辑也很简单,当传入集合不为空时,调用arrays.copyof进行复制,并且容量 size为传入大小,而传入集合为空,则赋值为空数组empty_elementdata。

3.添加元素

arraylist在添加元素时,都会进行容量确认,可能会涉及到扩容,数组复制,所以效率相对较低。同时在添加元素时,arraylist并未对元素本身进行校验,所以是允许集合中存在null的情况。

3.1.尾部添加元素
    public boolean add(e e) {
        // 确定容量
        ensurecapacityinternal(size + 1);  // increments modcount!!
        // 设值
        elementdata[size++] = e;
        return true;
    }

在add()方法中,最主要的是确定容量ensurecapacityinternal(int mincapacity)方法。

    private void ensurecapacityinternal(int mincapacity) {
        ensureexplicitcapacity(calculatecapacity(elementdata, mincapacity));
    }

首先会调用calculatecapacity(object[] elementdata, int mincapacity) 计算容量然后再ensureexplicitcapacity(int mincapacity)

    private static int calculatecapacity(object[] elementdata, int mincapacity) {
        if (elementdata == defaultcapacity_empty_elementdata) {
            return math.max(default_capacity, mincapacity);
        }
        return mincapacity;
    }

这里仅仅判断了是否是空数组defaultcapacity_empty_elementdata(== 地址比较),如果前面还有印象的话,这个只会在无参构造时,才会初始化为defaultcapacity_empty_elementdata,这时候会取default_capacity(10)与传入mincapacity的较大值,常说的默认容量大小10也就是在这里诞生的。

而其他的情况,都直接但会mincapacity,也即 size + 1,如果首次添加,那就是1。

    private void ensureexplicitcapacity(int mincapacity) {
        modcount++;
        // overflow-conscious code
        if (mincapacity - elementdata.length > 0)
            grow(mincapacity);
    }

modcount是一个操作计数器,add与remove都会 + 1。当我们需要在循环中删除arraylist元素时,需要使用迭代器iterator的remove()方法,此时直接使用list的删除有针对modcount的校验,会抛出 concurrentmodificationexception异常。

如果mincapacity大于数组容量,则调用grow(int mincapacity)进行扩容。

    private void grow(int mincapacity) {
        // overflow-conscious code
        int oldcapacity = elementdata.length;
        // 新容量增长 0.5倍
        int newcapacity = oldcapacity + (oldcapacity >> 1);
        if (newcapacity - mincapacity < 0)
            newcapacity = mincapacity;
        if (newcapacity - max_array_size > 0) // max_array_size = integer.max_value - 8
            newcapacity = hugecapacity(mincapacity);
        // mincapacity is usually close to size, so this is a win:
        elementdata = arrays.copyof(elementdata, newcapacity);
    }

扩容时,新的容量为原容量 + 原容量的一半,也就是0.5倍增长。如果增长后的新容量比计算出来的容量mincapacity小,则赋值为mincapacity,如果大于max_array_size(integer.max_value - 8),则进入hugecapacity(int 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;
    }

这里可以看到,当mincapacity < 0 时,会产生outofmemoryerror,这是一个error子类,这是需要避免的。什么时候mincapacity会小于0呢,当arraylist大小为integer.max_value后,还需要扩容,则会发生错误。

这个方法,我们可以看出,当arraylist需要的容量首次大于max_array_size时,会设置为max_array_size,然后再次扩容时会变成integer.max_value,如果还不够,那就会发生错误。

扩容的最后一步是调用arrays.copyof进行元素的复制,这个最终也是调用system.arraycopy进行操作的。同时size++,实际元素的数量也增加 1。

3.2.中间添加元素
    public void add(int index, e element) {
        rangecheckforadd(index);
        // 确认容量大小
        ensurecapacityinternal(size + 1);  // increments modcount!!
        system.arraycopy(elementdata, index, elementdata, index + 1, size - index);
        elementdata[index] = element;
        size++;
    }

在中间添加元素的逻辑和尾部添加元素基本一样。

    private void rangecheckforadd(int index) {
        if (index > size || index < 0)
            throw new indexoutofboundsexception(outofboundsmsg(index));
    }

添加元素前,首先要进行范围检查,添加的范围只能在[0,size]之间,index == size时,其实就是尾部插入。然后确认容量新的容量,这个方法尾部添加时已经讲过,接着数组复制,这步复制会跳过index位置的处理,最后再对index位置赋值,即完成了index位置的添加。

可以看到最后调用了size++,add(int index, e element)方法总是会添加元素,即使该index位置存在数据,只是会将原来的index位置数据往后挤动一位,并不会进行覆盖。

ArrayList实现原理(JDK1.8)

3.3.批量添加

arraylist除了add()与add(int index, e element),还有两个批量添加的方法。

    public boolean addall(collection<? extends e> c) {
        object[] a = c.toarray();
        int numnew = a.length;
        // 确认容量
        ensurecapacityinternal(size + numnew);  // increments modcount
        system.arraycopy(a, 0, elementdata, size, numnew);
        size += numnew;
        return numnew != 0;
    }

    public boolean addall(int index, collection<? extends e> c) {
        // 范围检查
        rangecheckforadd(index);
        object[] a = c.toarray();
        int numnew = a.length;
        // 确认容量
        ensurecapacityinternal(size + numnew);  // increments modcount
        int nummoved = size - index;
        if (nummoved > 0)
            system.arraycopy(elementdata, index, elementdata, index + numnew, nummoved);
        system.arraycopy(a, 0, elementdata, index, numnew);
        size += numnew;
        return numnew != 0;
    }

有了前面单个元素的添加基础,批量添加就很好懂了,唯一的区别就是在数组复制时,是复制整个待添加的集合。对于index位置的批量添加,中间插入的话(nummoved > 0),第一次复制会腾出中间要添加集合长度的位置,第二次将添加的集合复制到index位置。

4.修改元素

对于arraylist中元素的修改,如果是对象属性的修改,可以直接修改引用对象,但对于基本类型包装类或者string呢,并没有办法通过引用修改,亦或者我们要更换对象引用,这时候就需要调用set(int index, e element)。

    public e set(int index, e element) {
        // 范围检查
        rangecheck(index);
        e oldvalue = elementdata(index);
        elementdata[index] = element;
        return oldvalue;
    }

这个方法实现很容易,arraylist的修改本质就是对数组的值进行更改。首先进行范围检查,防止数组越界,这个很好理解,arraylist内部就是数组,然后对index位置的值进行替换即可。

    private void rangecheck(int index) {
        if (index >= size)
            throw new indexoutofboundsexception(outofboundsmsg(index));
    }

elementdata(int index)获取了原来的值,用于set返回值,elementdata实现更加简单,就是数组取值。

5.移除元素

arraylist中移除元素的方法有三个,按索引删除remove(int index)、按元素删除remove(object o)以及批量删除removeall(collection<?> c)等。

5.1.索引删除
    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;
    }

由于移除元素,并不涉及内部数组大小变化,所以实现相对较简单。必须要的范围检查,这个已经丝毫不陌生了,然后判断是否是尾部删除,如果不是尾部删除,则进行system.arraycopy复制,复制的目的是将index后的元素向前挪动 1 位元素以覆盖要删除的index位置,然后size减 1。

在移除方法中,可以看到modcount进行增加。同时对移除后尾部的元素赋值为null了,让gc生效。

ArrayList实现原理(JDK1.8)

5.2.按元素删除
    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;
    }

按元素删除的时候,首先判断了元素是否为null,因为arraylist中是可以添加null的,这里不同分支的逻辑是一样的,都是遍历集合比较是否和传入元素相同,只是比较一个是 == null 一个是 equals。如果相同则删除,然后return了,所以remove(object o)方法只会删除集合第一个与传入对象相同的元素。

重点就是这个fastremove了。

    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
    }

看到这个方法第一感觉是什么?是不是似曾相识,没错,fastremove和按指针删除基本上市一样的,只是少了范围校验和获取删除前的元素这两步。

5.3.批量删除
    public boolean removeall(collection<?> c) {
        objects.requirenonnull(c);
        return batchremove(c, false);
    }

对于removeall(collection< ? > c),校验非空后调用了batchremove(collection< ? > c, boolean complement)。

    private boolean batchremove(collection<?> c, boolean complement) {
        final object[] elementdata = this.elementdata;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                // 找出不需要移除的元素,放在数组的前面
                if (c.contains(elementdata[r]) == complement)
                    elementdata[w++] = elementdata[r];
        } finally {
            // preserve behavioral compatibility with abstractcollection,
            // even if c.contains() throws.
            if (r != size) {
                system.arraycopy(elementdata, r, elementdata, w, size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let gc do its work
                for (int i = w; i < size; i++)
                    elementdata[i] = null;
                modcount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

这个方法看着可能有一点点绕,但明白其原理后就很清晰了,首先遍历数组,找出在要移除数组中不包含的元素,从原数组头部开始放,这样的数有w个,即最终数组前w个元素都是在集合c中包含的,而剩下的位置的元素则不关心,最后就是讲w到size的元素赋值为null,以便gc工作。

6.循环删除

前面也提到了,arraylist在循环删除时会报错,这个究竟是怎么回事呢?

如果我们想删除一个集合中全部的某一个元素,例如下面集合ss中的a元素。

        list<string> ss = new arraylist<>();
        ss.add("a");
        ss.add("b");
        ss.add("a");
        ss.add("b");
        ss.add("c");

当我们需要删除一个时,我们可以调用remove方法删除,根据索引或者根据元素都用,但是多个时,我们不知道每一个元素的索引,而根据值也不知道有多少个a存在,所以我们需要遍历集合。

这时候就可能存在问题了。

        for (string s : ss) {
            if("a".equals(s)){
                ss.remove(s);
            }
        }

无论是fori的还是foreach的删除,都会抛出java.util.concurrentmodificationexception,这是因为arraylist循环时每一次取值都会调用其内部类itr.next()方法。

        public e next() {
            // 校验modcount
            checkforcomodification();
            int i = cursor;
            if (i >= size)
                throw new nosuchelementexception();
            object[] elementdata = arraylist.this.elementdata;
            if (i >= elementdata.length)
                throw new concurrentmodificationexception();
            cursor = i + 1;
            return (e) elementdata[lastret = i];
        }

在该方法最开始的地方,有校验modcount的checkforcomodification()方法,这个方法中比较了modcount和expectedmodcount,不相等就会抛出concurrentmodificationexception异常。

        final void checkforcomodification() {
            if (modcount != expectedmodcount)
                throw new concurrentmodificationexception();
        }

那expectedmodcount到底是什么,为什么和modcount不相等呢。

    private class itr implements iterator<e> {
        int cursor;       // index of next element to return
        int lastret = -1; // index of last element returned; -1 if no such
        int expectedmodcount = modcount;

expectedmodcount是itr的成员变量,这个在进行循环时会初始化赋值为modcount,最开始的时候他们是相等的,经过前面的探究,我们已经知道在remove调用时modcount会自增,所以checkforcomodification就会抛出异常。

而我们常使用的这个做法就是使用 itr 的remove。

        iterator<string> it = ss.iterator();
        while (it.hasnext()){
            if("a".equals(it.next())){
                it.remove();
            }
        }

这样删除时就没有任何问题了,这是因为 itr 的remove中,对expectedmodcount进行了重新赋值,使得每一次调用后值都相等。

        public void remove() {
            if (lastret < 0)
                throw new illegalstateexception();
            checkforcomodification();
            try {
                // 调用arraylist的删除
                arraylist.this.remove(lastret);
                cursor = lastret;
                lastret = -1;
                // expectedmodcount重新赋值
                expectedmodcount = modcount;
            } catch (indexoutofboundsexception ex) {
                throw new concurrentmodificationexception();
            }
        }

7.其他方法

arraylist中主要的就是构造方法、add和remove了,这几个方法看懂后,其他方法实现就比较清晰了。

比如get方法,其实就是根据索引获取了数组的元素。

    public e get(int index) {
        // 范围检查
        rangecheck(index);
        // 从数组获取值,即 elementdata[index]
        return elementdata(index);
    }

例如size方法, 就是返回了size属性的值。

    public int size() {
        return size;
    }

而isempty方法,就是判断size是否为0.

    public boolean isempty() {
        return size == 0;
    }

在arraylist中,有一个获取子集合的sublist方法,这个方法返回的是一个内部类sublist,该类并没重新创建新的数组,依旧持有了arraylist数组的元素的引用,所以当修改arraylist元素的时候,sublist的元素也会跟着修改,这个在实际开发中一定要注意。

    public list<e> sublist(int fromindex, int toindex) {
        sublistrangecheck(fromindex, toindex, size);
        return new sublist(this, 0, fromindex, toindex);
    }