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

Java ArrayList 详解

程序员文章站 2022-09-22 15:21:04
只记录目前为止关注的。JDK1.8 一、基础属性 1.1 内部参数 1.2 三个重载构造方法 二、操作及策略 2.1 动态扩容 扩容策略: 当数组全满了才扩容,新长度=旧长度\ 1.5 动态扩容有两个入口:供用户调用的显式扩容 和添加元素时的隐式扩容 ,不过均是调用 来根据传入所需容量值决定是否扩容 ......

只记录目前为止关注的。jdk1.8

一、基础属性

1.1 内部参数

    //空存储实例。直接new arraylist()便是以该空数组作为实例
    private static final object[] empty_elementdata = {};

    //默认容量大小,在由空实例进行首次扩容时,扩到到该长度。
    //实际使用中,并未实际存在capacity这个参数,需要扩容时直接根据旧数组的length进行扩容
    private static final int default_capacity = 10;

    //实际存储数组
    transient object[] elementdata;

    //存储元素个数
    private int size;

    //该字段用于迭代器的fail-fast机制【参考另一篇文章】
    protected transient int modcount = 0;

1.2 三个重载构造方法

    //构建一个空实例,elementdata指向容量为0的空数组
    public arraylist() {
        this.elementdata = defaultcapacity_empty_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);
        }
    }

    //以集合初始化创建列表
    //步骤:1. 调用toarray(),将给定集合转成数组(以arraylist为例,toarray()返回的是实际存在元素的那部分数组,即[0,size))
    //2. 让size直接等于给定集合的数组长度
    //3. 判断size如果为0则直接创建空存储实例,否则使用arrays.copyof将给定集合数组复制一份(浅拷贝),作为存储数组
    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;
        }
    }

    // arraylist 的 toarray()源码,复制[0,size)部分返回
    public object[] toarray() {
        return arrays.copyof(elementdata, size);
    }

二、操作及策略

2.1 动态扩容

扩容策略:当数组全满了才扩容,新长度=旧长度*1.5

动态扩容有两个入口:供用户调用的显式扩容ensurecapacity()和添加元素时的隐式扩容ensurecapacityinternal(),不过均是调用ensureexplicitcapacity()来根据传入所需容量值决定是否扩容,最终实际扩容操作在grow()方法中。

    //显式扩容入口方法
    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);
        }
    }

    //隐式扩容入口方法
    //其中参数 mincapacity 值为 size+1,由add方法调用传入
    private void ensurecapacityinternal(int mincapacity) {
        ensureexplicitcapacity(calculatecapacity(elementdata, mincapacity));
    }

    //添加方法
    public boolean add(e e) {
        // 传入最小所需容量为size+1
        ensurecapacityinternal(size + 1);  // increments modcount!!
        elementdata[size++] = e;
        return true;
    }


    //计算所需容量,实则不需要计算
    //只是单纯判断当前是否是空实例,为空就话返回 "默认容量"与mincapacity之间的较大值,不为空直接返回mincapacity
    //参数 mincapacity 只有两种情况:
    // 1. 隐式扩容时,如add()传入,其值为 size+1
    // 2. 显式扩容,用户指定
    private static int calculatecapacity(object[] elementdata, int mincapacity) {
        if (elementdata == defaultcapacity_empty_elementdata) {
            return math.max(default_capacity, mincapacity);
        }
        return mincapacity;
    }
    
    //在此处,根据最小所需容量来判断是否实际进行扩容
    private void ensureexplicitcapacity(int mincapacity) {
        modcount++;

        // overflow-conscious code
        if (mincapacity - elementdata.length > 0) //若已经占满,才进行扩容
            grow(mincapacity);
    }

    //实际扩容方法
    //可以看到扩容策略为:length + length*0.5(右移1位缩小1倍)
    //然后调用arrays.copyof浅复制
    private void grow(int mincapacity) {
        // overflow-conscious code
        int oldcapacity = elementdata.length;
        int newcapacity = oldcapacity + (oldcapacity >> 1); //旧长度+旧长度*2
        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);
    }

2.2 删除操作

arraylist中有两个remove方法public e remove(int index)public boolean remove(object o)

源码实现得其实挺简单,本来还在犹豫有没有必要把remove方法记录下来,但发现有个点值得注意以下:
注意点:jdk对于数组内元素统一移动操作,偏好使用system.arraycopy(ary, srcpos, ary, destpos, len)来移动

    //通过给定下标来删除元素,并返回删除元素
    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); // 使用system.arraycopyl来移动数组元素
        elementdata[--size] = null; // clear to let gc do its work  // 删除后size-1,并将先前最后一个元素置null

        return oldvalue; //返回删除元素
    }

    // 判断下标是否合理(<size),否则抛出异常
    private void rangecheck(int index) {
        if (index >= size)
            throw new indexoutofboundsexception(outofboundsmsg(index));
    }

    // 删除首个与给定元素相等的元素,元素判等使用equal方法
    // 成功返回true,失败返回false
    public boolean remove(object o) {
        if (o == null) { // 可以删除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])) { // 从头开始一个个检查,使用equal判等
                    fastremove(index);
                    return true;
                }
        }
        return false;
    }

    /*
     * 官方注释说得很清楚了:删除元素,但跳过边界检查且不返回删除元素。(就是remove(index)的缩略版
     * private remove method that skips bounds checking and does not
     * return the value removed.
     */
    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
    }