ArrayList源码解析-Java8

目录

一.

二.

2.1

2.2

2.3 

2.4

2.5

2.6

2.7

一.ArrayList介绍

ArrayList在平时开发过程中使用得特别频繁,它的底层是使用数组,存在线程并发安全(并发读写);

与之密切相关的Vector,功能和ArrayList几乎一样(源码也几乎一样),但是Vector是并发安全的,因为Vectory的接口,大多是在方法上加了synchronized关键字进行同步操作,达到并发安全的效果。

二.ArrayList源码分析

2.1 重要的属性

/**
 * 默认容量
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 共享的静态变量(一个空的数组)
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 默认空容量的数组
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 保存ArrayList中元素的真实数据,使用transient表示序列化时不计入该字段
 */
transient Object[] elementData;

/**
 * 记录ArrayList中元素的个数
 */
private int size;

/**
 * 允许申请的最大容量
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

2.2 构造方法

ArrayList有三个构造方法,需要注意的是,使用无参构造方法来创建ArrayList时,不会创建数组,也就是说不会分配数组内存空间。代码如下:

public ArrayList() {
    // 无参构造方法,直接将保存数据的elementData设置为空数组
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(int initialCapacity) {
    // 传入的初始容量大于0,则会创建指定容量长度的数组
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 如果传入的初始容量为0,则指定为空数组
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        // 容量小于0,属于非法参数,直接抛出异常
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    }
}

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 {
        // 如果传入的集合为空,那么直接设置为空的数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

2.3 添加新元素

添加新元素,常用的就是追加新元素和在指定位置插入新元素。

需要注意的是,ArrayList总是在真正插入元素前判断是否需要扩容,如果需要扩容,则扩容后,再插入新元素;不需要扩容则直接插入元素。

/**
 * 添加新元素(append)
 *
 * @param e 新元素
 */
public boolean add(E e) {
    // 判断是否需要扩容(元素数量+1 如果超过数组容量,则会进行扩容)
    ensureCapacityInternal(size + 1);

    // 将新元素放到最后一个元素后面(同时元素数量加1)
    elementData[size++] = e;
    return true;
}

/**
 * 将新元素插入指定位置
 */
public void add(int index, E element) {
    // 检测index是否越界
    rangeCheckForAdd(index);

    // 检测是否需要扩容(若需要,则进行扩容),同时修改modCount+1
    ensureCapacityInternal(size + 1);

    // 将index后面元素统统往后移动一个位置,空出index位置
    System.arraycopy(elementData, index, elementData, index + 1, size - index);

    // 将新元素放入index位置
    elementData[index] = element;

    // 元素数量加1
    size++;
}

/**
 * 检测指定的index是否越界
 */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0) {
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}

2.4 数组扩容

前面每次add的时候,都会调用ensourCapacityInternal(size+1),这个方法里面就会判断是否需要进行扩容,如果需要扩容则会进行扩容操作。

除此之外,该方法还有另外一个重要的操作,就是modCount++,记录数组的变化次数,用于快速失败。

/**
 * 确保内部数组的容量满足minCapacity
 *
 * @param minCapacity 期望的最小容量
 */
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

/**
 * 计算容量(正确容量)
 *
 * @param elementData 保存元素的数组
 * @param minCapacity 期望的最小容量
 * @return 确定容量
 */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果数组为空数组,那么就取minCapacity和默认容量10的较大值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    // 数组不为空,直接返回minCapacity
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    // 记录数组的修改次数
    modCount++;

    // 是否minCapacity超过当前数组的长度(当前容量),证明需要扩容(扩容的时机,重要!!!!)
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);
    }
}

/**
 * 数组扩容
 *
 * @param minCapacity 希望扩容后的数组长度
 */
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;               // 旧数组的长度
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 新数组的容量(旧数组的1.5倍)

    // 判断计算后的新数组容量是否满足要求的最小容量
    // 如果不满足,则直接将新数组的容量设置为需要的容量
    if (newCapacity - minCapacity < 0) {
        newCapacity = minCapacity;
    }

    // 如果申请的容量大于允许申请的最大容量,则返回允许申请的最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        newCapacity = hugeCapacity(minCapacity);
    }

    // 申请一个新数组(新容量),然后将原数组的数据拷贝到新数组中
    elementData = Arrays.copyOf(elementData, newCapacity);
}

从源码中可以看出,当底层数组满的时候(插入新元素,size+1,超过底层数组的容量),则需要进行扩容,扩容时,会创建1.5倍旧数组的新数组,并将旧数组的元素拷贝到新数组中(顺序不会变)。

2.5 删除元素

删除元素有两种方式,分别是删除指定元素和删除指定下标的元素。

删除元素之后,如果删除的不是最后一个元素,则需要将删除元素后面的元素往前挪一个位置,并将空出来的最后一个位置置位null(help GC)。

/**
 * 删除指定位置的元素
 */
public E remove(int index) {
    // 判断数组是否越界
    rangeCheck(index);

    // 修改次数加1
    modCount++;

    // 从数组中返回下标为index的元素
    E oldValue = elementData(index);

    // 计算需要移动的元素数量
    int numMoved = size - index - 1;
    
    // 如果需要移动的元素数量大于0(也就是删除的元素不是最后一个元素)
    // 则将index+1开始元素一次往前移动一个位置
    if (numMoved > 0) {
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    }
    
    // 将最后一个元素的位置删除(置位null,让GC的时候清除对应的内存)
    elementData[--size] = null;

    // 返回被删除的元素
    return oldValue;
}

/**
 * 判断数组是否越界
 *
 * @param index 指定数组下标
 */
private void rangeCheck(int index) {
    if (index >= size) {
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}

/**
 * 返回数组中下标为index的元素
 * @param index
 * @return
 */
@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

/*--------------------------------------------------------*/

/**
 * 删除指定元素(遍历数组中的元素,删除第一个匹配的元素)
 *
 * @return true:删除元素; false:未找到要删除的元素
 */
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++) {
            // 对于null,直接只用==进行比较
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
        }
    } else {
        for (int index = 0; index < size; index++) {
            // 对于非null的元素,使用equals方法进行比较
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
        }
    }
    
    return false;
}

/**
 * 快速删除指定下标的元素(不检测数组越界,不返回被删除的元素)
 */
private void fastRemove(int index) {
    // 修改次数加1
    modCount++;

    // 判断需要移动的元素数量
    int numMoved = size - index - 1;

    // 如果需要移动的元素数量大于0(删除的不是最后一个元素)
    // 则将index后面的元素一次往前移动
    if (numMoved > 0) {
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    }

    // 将数组空出的最后一个位置置位null(GC时清除元素),然后数组元素减1
    elementData[--size] = null; // clear to let GC do its work
}

 2.6 数组缩容

可以思考这种场景,一个ArrayList,刚开始初始容量为0,添加元素后,容量分别调为10、16...1024,但是后期数组元素在不断的删除元素,虽然数组中只剩下了5个元素,但是数组的长度是1024,这是极大地浪费,此时需要进行缩容,就是让底层数组调整为适合长度,最适合的长度就是刚好和元素数量个数相同。

ArrayList提供了trimToSize方法,就是进行缩容操作,将底层数组设置为刚好装下现有元素的长度

/**
 * 缩容操作,将底层数组组调整为size长度
 */
public void trimToSize() {
    // 修改次数加1
    modCount++;

    // 如果数组中的元素数量小于数组的长度,才进行缩容
    // 如果数组中没有元素,则将底层数组切换为一个空数组,否则就换为size大小的数组
    if (size < elementData.length) {
        elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
    }
}

2.7 获取元素

获取元素的过程,比较简单:

/**
 * 返回ArrayList中index下标的元素
 */
public E get(int index) {
    // 数组越界检测
    rangeCheck(index);

    // 返回index下标的元素
    return elementData(index);
}

/**
 * 判断数组是否越界
 *
 * @param index 指定数组下标
 */
private void rangeCheck(int index) {
    if (index >= size) {
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}

/**
 * 返回数组中下标为index的元素
 *
 * @param index
 * @return
 */
@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

原文地址:https://www.cnblogs.com/-beyond/p/13254542.html

相关推荐