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

JDK源码深入学习之ArrayList

程序员文章站 2023-12-03 10:50:52
ArrayList概述ArrayList:是一个可以动态改变大小的数组。ArrayList继承于AbstractList,实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。设计初衷就是为了解决数组大小不可动态拓展的局限性。ArrayList因为直接用的数组下标取的元素,所以查询效率较高。但是由于增删涉及数组元素的移动,所以增删效率比较低ArrayList是线程不安全的ArrayList继承关系图:ArrayList源码解读一...

ArrayList概述

ArrayList:是一个可以动态改变大小的数组。
ArrayList:直接用的数组下标取的元素,所以查询效率较高。但是由于增删涉及数组元素的移动,所以增删效率比较低
ArrayList:线程不安全的,建议使用Vector或者CopyOnWriteArrayList
ArrayList:继承于AbstractList,实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。设计初衷就是为了解决数组大小不可动态拓展的局限性。
ArrayList继承关系图:
JDK源码深入学习之ArrayList

ArrayList源码解读(JDK1.8)

ArrayList全局变量

    // 默认的数组初始化大小为10
    private static final int DEFAULT_CAPACITY = 10;

    // 用于空实例的共享空数组实例
    private static final Object[] EMPTY_ELEMENTDATA = {};

    // 用于默认大小为空的共享数组的实例。我们将其与空实例的共享空数组实例分开来,以了解添加第一个元素时要膨胀多少。
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    // 实际存放数据的数组
    transient Object[] elementData; 
    
    // arrayList的长度
    private int size;

ArrayList三个构造器

1.传入创建ArrayList大小为initialCapacity的有参构造器,创建一个指定大小的数组
创建大小 initialCapacity > 0,创建initialCapacity大小的ArrayList
创建大小 initialCapacity = 0,创建初始化大小为10的ArrayList
创建大小 initialCapacity < 0,抛异常不支持

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

2.无参构造器,创建一个空数组
注意:无参初始化并不是在无参构造方法的位置执行的,而是在第一次执行add方法的时候执行了容器大小的设置。所以容器的初始大小应该是0

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

3.传入一个集合Collection的有参构造器,创建一个与Collection c一样大小的数组,并把c中元素赋值至新数组

    public ArrayList(Collection<? extends E> c) {
        // 将c转换成数组
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // 如果数组的类型不是object,转为object类型
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 指向一个空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

arraycopy()方法:将原数组赋值到新创建的数组中(由于ArrayLits底层都会用到arraycopy方法,这里我提前说明一下)

src:原数组

srcPos:原数组中开始复制的位置

dest:目标数组

destPos:目标数组存放的位置,即从原数组的复制过来的元素从这个位置开始存放数据

length:复制数组的长度

    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

add()添加元素

JDK源码中ArrayListd添加一个元素提供了2个add()方法,分别是添加在ArrayList末尾和在具体某个下标位置添加元素。ArrayList在添加元素时会检查当前数组是否已经满了,如果满了则会进行1.5倍扩容。

    /**
     * add方法1:ArrayList末尾添加一个元素
     * @param e 添加的元素
     * @return
     */
    public boolean add(E e) {
        // 添加元素时,判断数组大小是否越界,越界则需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    /**
     * add方法2,在某个下标位置添加元素
     * @param index 下标位置
     * @param element 添加的元素
     */
    public void add(int index, E element) {
        // 检查下标是否在数组范围内
        rangeCheckForAdd(index);

        // 添加元素时,判断数组大小是否越界,越界则需要扩容
        ensureCapacityInternal(size + 1);

        // 1.从index位置开始复制原数组elementData到最后一个元素
        // 2.copy至原数组elementData的index+1的位置开始(size - index)个元素,也就是后面所有元素
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);

        // 给index位置赋值新添加元素
        elementData[index] = element;

        // arrayList长度+1
        size++;
    }

ArrayList在添加元素时动态扩容:
ensureCapacityInternal是ArrayLlist比较核心的一个方法,用于数组大小不够时进行扩容

    private void ensureCapacityInternal(int minCapacity) {
        // 计算添加元素后的新数组容量,若新容量导致数组越界则扩容
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        // 修改的次数,添加一次修改次数+1。用于快速失败迭代器(和列表迭代器)
        modCount++;

        // 如果当前数组长度不满足于最小所需新容量,则扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    private void grow(int minCapacity) {
        // 扩容原数组大小的1.5倍
        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);
    }
    
     /*
     *计算添加元素后的新数组容量
     *若当前数组为空,容量为默认数组大小10和minCapacity最大的一个
     *若当前数组不为空,容量为minCapacity
     */
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

get()取得元素

get():直接用数组下标取得,所以ArrayList查询速度比较快

    /**
     * 取得一个元素
     * @param index 取得元素下标
     * @return
     */
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

remove()删除元素

JDK提供2个移除元素的方法,分别是以下标或元素来移除元素。
具体移除都是先移除指定位置的元素,然后将该元素之后的元素集体前移一位。如果这个元素位置十分靠前,而数组长度又很大,此时就会极大的耗费性能。

    /**
     * 移除一个元素
     * @param index 待移除元素下标
     * @return
     */
    public E remove(int index) {
        // 校验待移除元素下标是否在数组范围内
        rangeCheck(index);

        // 操作计数+1
        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            // 1.复制elementData数组从(index+1)位置开始的元素,
            // 2.把复制的元素从index位置开始,拷贝numMoved个元素至elementData,也就是(index+1)位置后所有元素
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }
    
    
     /**
     * 移除一个元素
     * @param index 待移除元素
     * @return
     */
    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;
    }

clone()克隆:拷贝一个ArrayList

注意:ArrayList的clone()是浅拷贝
浅拷贝:被复制对象的任何变量都含有和原来的对象相同的值,而任何的对其他对象的引用仍然指向原来的对象。对拷贝后的引用的修改,还能影响原来的对象。
深拷贝:把要复制的对象所引用的对象都复制了一遍,对现在对象的修改不会影响原有的对象。

    /**
     * 克隆:ArrayList是浅拷贝,拷贝一个List
     * @return
     */
    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);
        }
    }

ArrayList三种遍历方式

(1)随机访问,通过索引值去遍历。由于ArrayList实现了RandomAccess接口,它支持通过索引值去随机访问元素。(索引取数据,效率最高)

        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }

(2)for循环遍历

        for (Object str : list) {
            System.out.println(str);
        }

(3)迭代器访问

        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()){
            String str = iterator.next();
            System.out.println(str);
        }

总结

  1. ArrayList的元素有序可重复
  2. ArrayList底层的操作都是基于数组的操作
  3. ArrayList查询快,增删慢
  4. ArrayList线程不安全
  5. ArrayList每次扩容1.5倍
  6. ArrayList允许存放null

本文地址:https://blog.csdn.net/qq_38425803/article/details/107086438