深入挖掘 ArrayList工作原理及其实现

深入挖掘 ArrayList工作原理及其实现

文章目录

ArrayList工作原理及其实现

1.ArrayList集合使用2.通过JDK源码来研究ArrayList的实现

2.1 继承关系2.2 属性和默认值2.3 构造函数2.4 常见方法原码解析

2.4.1 add：添加元素2.4.2 remove：删除元素2.4.3 get：获取元素

ArrayList工作原理及其实现

特点、需要通过源码底层实现查看实现逻辑。

1.ArrayList集合使用

特点：

1、ArrayList可以存放重复数据
2、ArrayList中元素存放和插入顺序一致。
3、ArrayList中存放的数据可以为null
4、ArrayList集合底层采用的是数组来存储数据

构造函数：

//无参构造
ArrayList  list = new ArrayList <>();
//通过指定集合容量大小来实例化
ArrayList  list1 = new ArrayList <>(100);
//通过Collection集合实例来实例化一个新集合
ArrayList  list2 = new ArrayList <>(list);

2.通过JDK源码来研究ArrayList的实现

1、关注继承关系
2、属性和默认值
3、构造函数
4、扩容机制、扩容时机
5、底层数据结构（数组、链表、队列、栈、哈希表…）
6、常见方法实现原理（add、get、remove）

2.1 继承关系

public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable

类结构图

①ArrayList继承自AbstractList，AbstractList是抽象类，实现了List接口，它是一个数组队列，提供了相关的添加、修改、删除、遍历等基本功能实现，方法子类对方法复用，如果子类有特有功能可以重写父类的方法。
②ArrayList实现了List接口，List接口继承自Collection接口，在Collection接口提供的方法基础上，有一些新的方法提供，比如get、set、add等特有方法。
③ArrayList实现了RandomAccess接口，即提供了随机访问功能。
④ArrayList实现了Cloneable接口，即包含了函数clone()，能被克隆。
⑤ArrayList实现了Serializable接口，意味着ArrayList支持序列化，能通过序列化去传输（IO）。

2.2 属性和默认值

//默认的初始容量10
private static final int DEFAULT_CAPACITY = 10;
//空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
//存储数据：使用的是数组，数组存储的数据类型是Object
private transient Object[] elementData;
//用来记录存放数据的个数
private int size;

ArrayList底层存储元素是使用数组，类型为Object类型。数组中:elementData.length:表示的是当前数组容量，最大存储的数据个数； size：实际存放的数据个数，即数组中有效数据个数。

2.3 构造函数

        //有参构造函数：通过指定初始容量initialCapacity来实例化ArrayList
	public ArrayList(int initialCapacity) {
        super();
        //参数合法性校验
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
        //实例化一个大小为initialCapacity数组并将数组赋值给elementData
        this.elementData = new Object[initialCapacity];
    }

    //无参构造函数  elementData赋值为空数组
    public ArrayList() {
       // ArrayList(DEFAULT_CAPACITY);
        super();
        this.elementData = EMPTY_ELEMENTDATA;
        //将默认值的赋值在add中完成
    }

    //通过集合来实例化ArrayList
    public ArrayList(Collection c) {
        //将集合转化为数组，直接赋值给elementData
        elementData = c.toArray();
        //将集合中已有元素的大小赋值给size(有效数据个数)
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        //如果elementData类型不是Object类型，将其强转为Object类型
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

2.4 常见方法原码解析 2.4.1 add：添加元素

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
}

1、 ensureCapacityInternal(size + 1); 检查数组容量是否够

 private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

2 、 如果当前数组是空数组，那么就会初始化数组容量大小为 10 (添加第一个元素，集合是通过无参构造实例的时候)

3、 如果当前数组不是空数组，那么执行ensureExplicitCapacity(minCapacity);

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
    
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

1)modcount++: modCount属性是版本控制器，和业务无关，仅仅是做版本控制，在集合进行变更时（修改、删除、添加）会自增1

如果size+1 大于 数组的长度 那么进行 扩容 *** 作 grow(minCapacity);

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

扩容机制

①拿到数组的长度，把长度扩大到原来的1.5 倍，得到新的数组长度newCapacity

oldCapcity >> 1 效率 比 oldCapcity / 2 高

②如果新的数组长度小于size+1的长度 大于 新的数组长度，更新新的数组长度为size + 1，如果新的数组长度比最大值MAX_ARRAY_SIZE还要大，进入hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，如果minCapacity大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8

③调用Arrays.copyOf()函数将原有的集合数据拷贝到新容量为newCapacity的数组中

2.4.2 remove：删除元素

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

1、 如果删除对象是null ，遍历数组，找到null的元素，调用**fastRemove()**方法

2、 如果删除对象不是null，遍历数组，找到对应的元素，调用**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
    }

3、fastRemove方法

删除对应的元素后，需要将后面的元素一一往前移动一位。先统计需要移动的元素个数（删除元素后的元素个数），调用System.arraycopy()方法进行元素拷贝移动，最后将数组中最后一个元素置为null，有效元素个数-1。

2.4.3 get：获取元素

    public E get(int index) {
        //检查查询位置的合法性 index = size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

	 E elementData(int index) {
        return (E) elementData[index];
    }