美文网首页Java语言Java集合框架程序员
ArrayList源码解析(基于Java8)

ArrayList源码解析(基于Java8)

作者: 紫霞等了至尊宝五百年 | 来源:发表于2018-01-30 14:35 被阅读66次


    首先:执行List<Person> list1 = new ArrayList<>();
    在堆内存开辟了一块空间,既然是new出来的,那我们直接从构造函数入手

    很简单一行代码,继续看一下

    this.elementData

    DEFAULTCAPACITY_EMPTY_ELEMENTDATA

    分别是什么



    Object[]数组,也就是说该数组可以放任何对象(所有对象都继承自父类Object)

    static修饰的变量,常驻于方法区,我们不需要new,JVM会提前给我们初始化好,这个特性在实际开发过程中,经常拿来做缓存
    fianl修饰的变量,JVM也会提前给我们初始化好

    继续,执行list1.add(person1)看怎么处理add的


    先看ensureCapacityInternal方法,有个参数size,看一下这个size从哪来的

    size是int基本数据类型,成员变量初始化的为0

    继续往下看


    ensureCapacityInternal是在add里面调用的

    private void ensureCapacityInternal(int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //如果底层数组就是默认的缓存数组,取两个参数的大的一个值继续往下调用,很明显这个大值为10
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    
            ensureExplicitCapacity(minCapacity);
     }
    
     private void ensureExplicitCapacity(int minCapacity) {
            modCount++;//记录修改次数
    
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    

    扩容

        private void grow(int minCapacity) {
            // 取到旧数组的长度
            int oldCapacity = elementData.length;
            //计算新数组的长度
            //>>是移位运算符,相当于int newCapacity = oldCapacity + (oldCapacity/2),但性能会好一些
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            //保证长度在正常范围内
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // 用计算出来的数组长度,往下传继续处理
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    

    这就是数组的扩容,一般是oldCapacity + (oldCapacity >> 1),相当于扩容1.5倍

    跟进到Arrays这个工具类,很简单


    再看copyOf()方法



    System.arraycopy()方法用了一个native来修饰。
    native的方法,是由其它语言来实现的,一般是(C或C++),所以这儿没有实现代码。
    这是一个数组拷贝方法,大家还在写for循环拷贝数组吗?以后多用这个方法吧,简单又方便还能获得得更好的性能。


    顺便看一看size()方法的源码


    很简单,就是返回size值,而不是底层数组的长度,就是为何String里叫length()而List里叫size()的原因

    有人说,诶,就一个元素,在堆内存中占了10个位置,好浪费啊,没办法,你要享受ArrayList的便利与丰富的API,就得牺牲一下空间作为代价

    ArrayList还提供了其它构造方法,我们顺便来看一下

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

    当我们在写代码过程中,如果我们大概知道元素的个数,比如一个班级大概有40-50人,我们优先考虑List<Person> list2 = new ArrayList<>(50)以指定个数的方式去构造,这样可以避免底层数组的多次拷贝,进而提高程序性能。

    在长度为n数组中:
    直接通过下标去访问元素,时间复杂度为O(1)
    需要循环查找元素的时候,时间复杂度为O(n)

    删除

    删除指定位置的元素

    public E remove(int index) {
            rangeCheck(index);
    
            //维护的一个变量,记录修改次数
            modCount++;
            //根据数组下标拿到底层数组里的元素
            E oldValue = elementData(index);
    
            //计算数组需要拷贝的元素个数
            int numMoved = size - index - 1;
            if (numMoved > 0)
                //拷贝删除位置(index)+1后面的numMoved个元素并从删除位置(index)开始复制
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            //相当于:size = size - 1; elementData[size] == null
            //size减1,数组最后一个位置赋值为null
            elementData[--size] = null; // clear to let GC do its work
    
            //返回事先拿到的删除元素
            return oldValue;
    }
    

    这段代码里还调了一个方法rangeCheck()方法,我们看一下

    private void rangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    

    好简单对不对,就是检查底层数组下标是否越界。我们再看另外一种删除方式

    删除指定对象元素

    public boolean remove(Object o) {
            //如果要删除的元素为null
            if (o == null) {
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) {
                        //循环查找null,找到后执行fastRemove()方法
                        fastRemove(index);
                        //删除成功,返回true
                        return true;
                    }
            } else {
                //要删除元素非空
                for (int index = 0; index < size; index++)
                    if (o.equals(elementData[index])) {
                        //equals循环对比,对比成功则执行fastRemove()方法
                        fastRemove(index);
                        //删除成功,返回true
                        return true;
                    }
            }
            //其他情况,返回 false
            return false;
    }
    

    再看一下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
    }
    

    和上面用下标删除方式一致,就是少了某些代码,就不细说了

    相关文章

      网友评论

      • 李2牛:这就是数组的扩容,一般是oldCapacity + (oldCapacity >> 1),相当于扩容1.5倍。
        乍一看以为是想着左移应该是乘以,仔细一看才发现是右移除以2

      本文标题:ArrayList源码解析(基于Java8)

      本文链接:https://www.haomeiwen.com/subject/ntlczxtx.html