JDK源码学习笔记——ArrayList

JDK源码学习笔记——ArrayList

1.1 实现接口

  • java.util.List :提供增删改查等基本操作
  • java.io.Serializable :标记接口,表示支持序列化
  • java.lang.Cloneable :标记接口,表示支持克隆
  • java.util.RandomAccess :这个接口可能很少注意到,其实也是一个标记接口,表示能够随机访问元素,简单来说就是底层是数组实现的集合。参考: RandomAccess 这个空架子有何用?

1.2 继承

  • java.util.AbstractList :抽象类,从注释中可以看到,它提供了List接口的基本实现,以最大程度地减少迭代遍历相关操作的实现。不过ArrayList基本都重写了AbstractList提供的实现。

2 属性

  • int elementData :储存元素的数组,ArrayList的真实大小
  • int sizeelementData 中实际存放元素的数量,我们经常调用的 size() 方法返回的也就是它

3 构造方法

3.1 ArrayList(int initialCapacity)

/**
     * 空数组,当初始化容量为0时,将elementData指向它
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    public ArrayList(int initialCapacity) {
        // 指定容量大于0 创建对应的Object数组
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        // 等于0 使用 EMPTY_ELEMENTDATA 
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        // 小于0 抛出异常
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
复制代码

尽量预估数组大小,使用该方法创建ArrayList,合理使用内存,避免数组扩容耗费性能。

3.2 ArrayList()

/**
     * Default initial capacity.
     * 默认初始化容量
     */
    private static final int DEFAULT_CAPACITY = 10;
    
    /**
     * 使用默认容量时的空数组。当使用无参构造时,为了节省内存(考虑到创建了ArrayList对象但没使用的情况)
     * 做了优化,在首次添加元素时,才将elementData初始化成长度为10的数组。
     * 与EMPTY_ELEMENTDATA区分开,以便在初始化时知道是直接初始化成10。
     * 而EMPTY_ELEMENTDATA从0开始按照1.5倍扩容。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    /**
     * 使用默认容量10创建ArrayList
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
复制代码

3.3 ArrayList(Collection<? extends E> c)

/**
     * 传入一个集合来创建ArrayList
     */
    public ArrayList(Collection<? extends E> c) {
        // 将集合转为Object数组
        elementData = c.toArray();
        // 如果数组长度不等于0
        if ((size = elementData.length) != 0) {
            // defend against c.toArray (incorrectly) not returning Object[]
            // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
            
            // 如果elementData不是Object数组类型,就创建个新的Object类型数组,
            // 并将elementData中的元素赋值进去,最终再把新数组赋值给elementData
            
            // 是为了修复JDK-626065的BUG,c.toArray不返回Ojbect[]类型数组
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        // 如果数组大小等于0,使用EMPTY_ELEMENTDATA
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
        
        // ??为什么一会用this.elementData,一会又不加this.了
    }
    
复制代码

4 主要方法

4.1 添加一个元素

boolean add(E e) 添加到尾部

/**
     * 将一个元素添加到末尾
     */
    public boolean add(E e) {
        // 定义于父类AbstractList中,用于记录数组被修改的次数,+1
        modCount++;
        add(e, elementData, size);
        return true;
    }
    
    private void add(E e, Object[] elementData, int s) {
        // 如果容量不足,进行扩容
        if (s == elementData.length)
            elementData = grow();
        // 元素放到数组末尾
        elementData[s] = e;
        // size +1
        size = s + 1;
    }
    
复制代码

void add(int index, E element) 添加到指定位置

/**
     * 在指定位置插入一个元素
     */
    public void add(int index, E element) {
        // 检查index是否在数组范围内
        rangeCheckForAdd(index);
        // 修改次数 +1
        modCount++;
        final int s;
        Object[] elementData;
        // 如果容量不够,进行扩容
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();
        // 将index位置及之后的元素向后挪一位
        // 数组复制
        System.arraycopy(elementData, // 原数组
                         index, // 从原数组的开始位置
                         elementData, // 目标数组
                         index + 1, // 在目标数组的开始位置
                         s - index); // 复制元素的个数
        // 将插入元素放在index的位置
        elementData[index] = element;
        // size + 1
        size = s + 1;
    }
复制代码

4.2 扩容

Object[] grow()

private Object[] grow() {
        // 扩容后容量至少比以前大1
        return grow(size + 1);
    }
    
    /**
     * @param minCapacity 所需最小扩容后容量
     */
    private Object[] grow(int minCapacity) {
        // 记录老的容量
        int oldCapacity = elementData.length;
        // 如果容量 > 0 或 数组不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA,计算新的容量大小并扩容
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth 最小扩大量*/
                    oldCapacity >> 1           /* preferred growth 首选扩大量*/);
            // 把元素拷贝到新数组中
            return elementData = Arrays.copyOf(elementData, newCapacity);
            /*
                ArraysSupport.newLength 计算新数组大小,取 minimum growth 和
                preferred growth 的更大值加上旧的容量。
                还涉及到一些数组最大长度的校验和处理,这里不细说。

                >> 是移位运算符,右移一位相当于除以二,也就是说这里是扩大到1.5倍
                如果是从0扩容,0 >> 1 还是0,此时使用minCapacity,也就是1
            */
        // 如果是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA,创建新数组
        } else {
            // 容量取 默认容量 和 minCapacity 中的更大值
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }
复制代码

4.3 添加多个元素

boolean addAll(Collection<? extends E> c) 向末尾添加

/**
     * 向末尾添加多个元素
     * 调用此方法相比一个一个添加元素,可以避免数组多次扩容
     */
    public boolean addAll(Collection<? extends E> c) {
        // 转换成数组
        Object[] a = c.toArray();
        // 修改次数+1
        modCount++;
        // 新加入元素个数
        int numNew = a.length;
        // 如果个数为0,返回false,ArrayList数组无变化,但修改次数是增加了的
        if (numNew == 0)
            return false;
        Object[] elementData;
        final int s;
        // 如果新加入元素不够放了,则进行扩容,要求扩容后至少能放得下新加入的数据
        if (numNew > (elementData = this.elementData).length - (s = size))
            elementData = grow(s + numNew);
        // 将新数组复制进elementData的末尾
        System.arraycopy(a, 0, elementData, s, numNew);
        // 计算size大小
        size = s + numNew;
        return true;
    }
复制代码

boolean addAll(int index, Collection<? extends E> c) 向指定位置添加

public boolean addAll(int index, Collection<? extends E> c) {
        // 检查是否越界
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        modCount++;
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Object[] elementData;
        final int s;
        // 扩容,至少装得下新数组
        if (numNew > (elementData = this.elementData).length - (s = size))
            elementData = grow(s + numNew);

        int numMoved = s - index;
        // 如果index位置已有元素,则将它开始及之后的元素向后移出位置来
        if (numMoved > 0)
            System.arraycopy(elementData, index,
                             elementData, index + numNew,
                             numMoved);
        // 将新数组加入elementData指定的位置
        System.arraycopy(a, 0, elementData, index, numNew);
        size = s + numNew;
        return true;
    }
复制代码

4.4 移除单个元素

E remove(int index) 移除指定位置的元素,并返回该元素

public E remove(int index) {
        // 校验 index不能 > size
        Objects.checkIndex(index, size);
        final Object[] es = elementData;

        // 记录被删除的值
        @SuppressWarnings("unchecked") E oldValue = (E) es[index];
        fastRemove(es, index);
        // 返回被删除的值
        return oldValue;
    }

    /**
     * 负责删除的核心逻辑,不关心返回被删除元素或越界校验等操作
     */
    private void fastRemove(Object[] es, int i) {
        // 修改次数+1
        modCount++;
        final int newSize;
        // size是比下标大 1 的,size-1 和 i 比较,其实是在判断i是不是数组最后一位
        // 如果不是最后一位,要把i后边的所有元素向前挪一位。
        if ((newSize = size - 1) > i) // 注意这里藏着 size - 1 的操作
            System.arraycopy(es, i + 1, es, i, newSize - i);
        // 将最后一位置空,帮助 GC
        es[size = newSize] = null;
    }
复制代码

boolean remove(Object o) 移除首个为 o 的元素,返回是否移除

public boolean remove(Object o) {
        final Object[] es = elementData;
        final int size = this.size;
        // 用于标记找到的第一个 o 的位置
        int i = 0;
        found: { // 利用break终止代码块执行,使代码更简洁
            // 如果 o 是 null
            if (o == null) {
                for (; i < size; i++)
                    if (es[i] == null)
                        break found;
            // 如果 o 不是 null
            } else {
                for (; i < size; i++)
                    if (o.equals(es[i]))
                        break found;
            }
            return false;
        }
        // 移除
        fastRemove(es, i);
        return true;
    }
复制代码

4.5 移除多个元素

boolean removeAll(Collection<?> c) 如果元素在集合 c 中就移除

/**
     * 删除多个元素
     */
    public boolean removeAll(Collection<?> c) {
        // 调用了批量删除方法
        return batchRemove(c, false, 0, size);
    }
复制代码

boolean batchRemove(Collection<?> c, boolean complement, final int from, final int end) 批量移除或保留元素

这个方法有点绕。先来看参数 complement ,它表示如果一个元素在集合c中,他是保留还是删除。结合另一个方法 public boolean retainAll(Collection<?> c) { return batchRemove(c, true, 0, size); } 就很容易理解了,当 complementfalse 时,是移除的逻辑。而为 true 时,是求两个集合的交集。

这个方法的大致逻辑是:(以移除为例)先找到第一个要移除的元素索引,记为 w ,它的下一位记为 r 。然后从 r 的位置开始遍历,如果是要删除的元素就跳过,如果是要保留的元素,就将它写到 w 指向的位置,覆盖之前的元素,再把 w 挪向下一位,继续遍历判断。最后再把数组末尾无用的元素置为null。下文代码后我贴了一张手绘图,可以结合起来理解。或者debug调试几次。

/**
     * 批量删除或保留多个元素
     * @param c 要删除的元素集合
     * @param complement 如果一个元素再 c 中,是删除还是保留
     * @param from 开始位置
     * @param end 结束位置
     * @return
     */
    boolean batchRemove(Collection<?> c, boolean complement,
                        final int from, final int end) {
        // 校验 c 不是 null
        Objects.requireNonNull(c);
        final Object[] es = elementData;
        int r;
        // Optimize for initial run of survivor 优化
        // 想在删除逻辑前线判断elementData中到底有没有 c 中的元素,但有不想重复遍历
        // 这里做的是 找到第一个不符合 complement 的元素的位置 r ,然后结束遍历
        for (r = from;; r++) {
            if (r == end)
                return false;
            if (c.contains(es[r]) != complement)
                break;
        }
        // w 标记 r 的位置,r + 1 指向下一个位置
        int w = r++; // 注意,这里等价于 w = r; r = r + 1; (i++ 和 ++i 的区别)
        try {
            for (Object e; r < end; r++)
                // 如果 r 位置的元素符合 complement ,将 r 位置的元素写入 w 位置的元素,w 向后挪一位
                // 如果不符合,w 不动,进行下次循环
                if (c.contains(e = es[r]) == complement)
                    es[w++] = e;
        } catch (Throwable ex) {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            // 如果 cntains()方法抛出异常,则将 r 位置后的数据写到 w 位置后
            // 这样我们剩余没有遍历的元素挪过去之后覆盖了跳过的元素,保证数组中不会多出来一些奇怪的元素
            System.arraycopy(es, r, es, w, end - r);
            w += end - r;
            // 把异常继续抛出去
            throw ex;
        } finally {
            // 增加修改次数
            modCount += end - w;
            // 尾部无用元素赋值为null
            shiftTailOverGap(es, w, end);
        }
        return true;
    }
    
    /**
     * 在数组 hi 和 lo 的位置各剪一刀,丢掉 hi 和 lo 中间的部分,然后把 hi 这一头和 
     * lo 那一头连起来
     * 
     * @param es 数组
     * @param lo 开始位置
     * @param hi 结束位置
     */
    private void shiftTailOverGap(Object[] es, int lo, int hi) {
        // 从 hi 位置开始的元素移动到 lo 位置后
        System.arraycopy(es, hi, es, lo, size - hi);
        // 将末尾没用的位置置空
        for (int to = size, i = (size -= hi - lo); i < to; i++)
            es[i] = null;
    }
复制代码
JDK源码学习笔记——ArrayList

批量移除给定范围内的多个元素 void removeRange(int fromIndex, int toIndex)

/**
     * 批量移除 [fromIndex, toIndex) (前闭后开)范围内的多个元素
     */
    protected void removeRange(int fromIndex, int toIndex) {
        // 参数不正确
        if (fromIndex > toIndex) {
            throw new IndexOutOfBoundsException(
                    outOfBoundsMsg(fromIndex, toIndex));
        }
        // 修改次数+1
        modCount++;
        // 该方法见上文
        shiftTailOverGap(elementData, fromIndex, toIndex);
    }
复制代码

根据条件移除元素 boolean removeIf(Predicate<? super E> filter)

略…

4.6 查找单个元素

int indexOf(Object o) 查找第一个指定元素的索引

public int indexOf(Object o) {
        return indexOfRange(o, 0, size);
    }

    int indexOfRange(Object o, int start, int end) {
        Object[] es = elementData;
        // o 为null的情况
        if (o == null) {
            for (int i = start; i < end; i++) {
                if (es[i] == null) {
                    return i;
                }
            }
        // o 不为null的情况
        } else {
            for (int i = start; i < end; i++) {
                if (o.equals(es[i])) {
                    return i;
                }
            }
        }
        // 没找到返回 -1
        return -1;
    }
复制代码

int indexOf(Object o) 查找最后一个指定元素的索引

public int lastIndexOf(Object o) {
        return lastIndexOfRange(o, 0, size);
    }

    int lastIndexOfRange(Object o, int start, int end) {
        Object[] es = elementData;
        if (o == null) {
            for (int i = end - 1; i >= start; i--) { // 倒序
                if (es[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = end - 1; i >= start; i--) {
                if (o.equals(es[i])) {
                    return i;
                }
            }
        }
        return -1;
    }
复制代码

int indexOf(Object o) 获得指定位置的元素

public E get(int index) {
        // 校验
        Objects.checkIndex(index, size);
        return elementData(index);
    }
    
    E elementData(int index) {
        return (E) elementData[index];
    }
复制代码

4.7 设置指定位置的元素

E set(int index, E element)

public E set(int index, E element) {
        // 校验
        Objects.checkIndex(index, size);
        // 记录旧值
        E oldValue = elementData(index);
        // 赋值新值
        elementData[index] = element;
        // 返回旧值
        return oldValue;
    }
复制代码

5 其他方法

5.1 转换为数组

Object[] toArray() 转换为Object[]

// ArrayList.java
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
    
    // Arrays.java
    public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }
复制代码

Object[] toArray() 转换为给定泛型的数组

public <T> T[] toArray(T[] a) {
        // 如果传入的数组大小没有 size 大
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            // 直接复制一个新数组返回
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        // 把 elementData 的数据复制到 a 中
        System.arraycopy(elementData, 0, a, 0, size);
        // 如果 a 的长度 大于 size ,就。。把 size 位置设置为 null ???
        if (a.length > size)
            a[size] = null;
        return a;
    }
复制代码

对中间 a[size] = null 的疑惑作者在方法注释中有写到:

* <p>If the list fits in the specified array with room to spare
     * (i.e., the array has more elements than the list), the element in
     * the array immediately following the end of the collection is set to
     * {@code null}.  (This is useful in determining the length of the
     * list <i>only</i> if the caller knows that the list does not contain
     * any null elements.)
复制代码

如果调用者明确知道数组中没有空元素,那么这对于确定list的length很有帮助。emmm…插入null值作为一个标记..或许调用者可以在遍历数组时判断元素为空就不再遍历了??

5.2 求哈希值

int hashCode()

public int hashCode() {
        // 记录开始前数组修改次数
        int expectedModCount = modCount;
        // 获取哈希值
        int hash = hashCodeRange(0, size);
        // 并发修改校验
        checkForComodification(expectedModCount);
        return hash;
    }

    int hashCodeRange(int from, int to) {
        final Object[] es = elementData;
        // 校验
        if (to > es.length) {
            throw new ConcurrentModificationException();
        }
        // 计算hash值
        int hashCode = 1;
        for (int i = from; i < to; i++) {
            Object e = es[i];
            // 为什么要乘31,看下文参考资料
            hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
        }
        return hashCode;
    }
    
    /**
     * 并发修改校验,如果操作前数组的修改次数和操作后的修改次数不一致,
     * 则抛出异常
     */
    private void checkForComodification(final int expectedModCount) {
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }
复制代码

参考资料: 田小波的技术博客——科普:String hashCode 方法为什么选择数字31作为乘子

5.3 判断相等

boolean equals(Object o)

public boolean equals(Object o) {
        // 与自己本身相比,直接返回 true
        if (o == this) {
            return true;
        }

        // 非 List 类型,直接返回 false
        if (!(o instanceof List)) {
            return false;
        }

        // 记录当前数组修改次数
        final int expectedModCount = modCount;
        // ArrayList can be subclassed and given arbitrary behavior, but we can
        // still deal with the common case where o is ArrayList precisely
        // 根据类型是否是ArrayList,选择不同的比较方式
        // ArrayList可以遍历数组,性能更优,而其他List只能用迭代器。
        boolean equal = (o.getClass() == ArrayList.class)
            ? equalsArrayList((ArrayList<?>) o)
            : equalsRange((List<?>) o, 0, size);
        // 并发修改校验
        checkForComodification(expectedModCount);
        return equal;
    }
    
    private boolean equalsArrayList(ArrayList<?> other) {
        // 记录传入list的修改次数
        final int otherModCount = other.modCount;
        final int s = size;
        boolean equal;
        // 先判断 size 是否相等
        if (equal = (s == other.size)) {
            final Object[] otherEs = other.elementData;
            final Object[] es = elementData;
            // 校验并发修改
            if (s > es.length || s > otherEs.length) {
                throw new ConcurrentModificationException();
            }
            // 遍历,比较每个对应元素是否相等
            for (int i = 0; i < s; i++) {
                if (!Objects.equals(es[i], otherEs[i])) {
                    equal = false; // 如果不相等跳出循环
                    break;
                }
            }
        }
        // 校验传入list的并发修改
        other.checkForComodification(otherModCount);
        return equal;
    }
    
    boolean equalsRange(List<?> other, int from, int to) {
        final Object[] es = elementData;
        // 并发修改校验
        if (to > es.length) {
            throw new ConcurrentModificationException();
        }
        // 用迭代器遍历逐个对比
        var oit = other.iterator();
        for (; from < to; from++) {
            // 如果oit没有下一个元素或当前元素不相等,直接返回 false
            if (!oit.hasNext() || !Objects.equals(es[from], oit.next())) {
                return false;
            }
        }
        // 返回oit是否还有剩余的元素。如果还有当然是不相等的
        return !oit.hasNext();
    }
复制代码

5.4 克隆

Object clone()

public Object clone() {
        try {
            // 调用父类克隆方法
            ArrayList<?> v = (ArrayList<?>) super.clone();
            // 拷贝新数组
            v.elementData = Arrays.copyOf(elementData, size);
            // 修改次数置为 0
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            // 实现Cloneable接口后不会再发生了
            throw new InternalError(e); // JVM 意外内部错误
        }
    }
复制代码

5.5 清空

void clear()

public void clear() {
        // 修改次数 + 1
        modCount++;
        // 遍历置空 倒序
        final Object[] es = elementData;
        for (int to = size, i = size = 0; i < to; i++)
            es[i] = null;
    }
复制代码

5.6 序列化与反序列化

void writeObject(java.io.ObjectOutputStream s) 序列化

@java.io.Serial
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        int expectedModCount = modCount;
        // 序列化 非静态,非 transient 属性
        s.defaultWriteObject();

        // 写入 size ,为了兼容 clone() 方法 ???
        s.writeInt(size);

        // Write out all elements in the proper order.
        // 逐个写入元素
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }
        // 并发修改校验
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }
复制代码

elementData 是加了 transient 关键字的,序列化时会只序列化size大小的真实使用的数组,不会序列化 elementData 预留出的那一部分。节省时间空间

void readObject(java.io.ObjectOutputStream s)

@java.io.Serial
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {

        // 反序列化 非静态,非 transient 属性
        s.defaultReadObject();

        // Read in capacity
        // 读取 size ,但忽略不用了
        s.readInt(); // ignored

        if (size > 0) {
            // like clone(), allocate array based upon size not capacity
            // emmm....
            SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
            Object[] elements = new Object[size];

            // 逐个读取元素
            for (int i = 0; i < size; i++) {
                elements[i] = s.readObject();
            }

            elementData = elements;
        } else if (size == 0) {
            // size 是 0 的话使用空数组
            elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new java.io.InvalidObjectException("Invalid size: " + size);
        }
    }
复制代码

6 End

省略了一些不常用的或简单的方法,以及逻辑重点不在ArrayList中的方法(比如sort()排序)。

原文 

https://juejin.im/post/5dc0e42b5188255fb6573526

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » JDK源码学习笔记——ArrayList

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址