Java集合源码:(一) ArrayList源码解析(JDK8)

集合整体架构文章:

罗政:JAVA 集合整体架构

ArrayList概述

ArrayList 是一个 动态数组 ,它是 线程不安全 的,允许元素为null。底层数据结构依然是 数组 ,它是 占据一块连续的内存空间 (容量就是数组的 length ),所以它也有数组的缺点, 空间效率不高 。由于数组的内存连续,可以根据下标以O1的时间 读写(改查) 元素,因此 时间效率很高

当集合中的元素超出这个容量,便会进行 扩容操作 。扩容操作也是 ArrayList 的一个性能消耗比较大的地方,所以若 我们可以提前预知数据的规模 ,应该通过 public ArrayList(int initialCapacity) {} 构造方法,指定集合的大小,去构建 ArrayList 实例 ,以减少扩容次数,提高效率


ArrayList源码

重要的成员变量

transient Object[] elementData; // 实际的元素存储数组
private int size;   // 当前元素的个数,实现O(1)复杂度 求list大小
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
protected transient int modCount = 0; // 集合被修改的次数,遍历时不能移除靠它实现

构造函数

public ArrayList() {
       this.elementData = {}; // 初始为空数组
 }
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            // 构造了 一个指定大小的 Object数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
}

总结: 构造函数走完之后,会构建出数组elementData 和数量size=0。

add方法解析

public boolean add(E e) {
	ensureCapacityInternal(size + 1);  // size为当前数组真实存的元素
	elementData[size++] = e;
	return true;
}

ensureCapacityInternal 判断了是不是需要扩容,如果需要就进行扩容。然后将数据放入到size的位置,也就是数组的末尾,然后size加1,返回add成功。

复杂的在于 ensureCapacityInternal 扩容相关,下面我们来详细分析:

   private void ensureCapacityInternal(int minCapacity) { // minCapacity: 当前size + 1
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // 第一次 elementData 才为空 {}  , DEFAULT_CAPACITY:10
            return Math.max(DEFAULT_CAPACITY, minCapacity); //返回10
        }
       // 加入这个元素后的size 大小
        return minCapacity;
    }
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;  // 修改次数 加加
        if (minCapacity - elementData.length > 0) // 当前加入这个元素后 size就大于数组容量了,就已经是存不下了
            grow(minCapacity);  // 对elementData 进行扩容
    }

可见上面判断 加入元素后size 已经超出elementData的容量了就进行扩容grow。

 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;   
 private void grow(int minCapacity) {
        // 老的数组 容量 (并不是minCapacity) , minCapacity:是已有元素大小
        int oldCapacity = elementData.length;
        // 扩容后大小: 老的大小 + 老的大小/2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0) // 元素大小超过了容量
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)  // Integer.MAX_VALUE - 8
            // 这里为什么要用Integer.MAX_VALUE-8呢,因为数组在虚拟机中存储时需要8字节来存储其自身的大小
            newCapacity = hugeCapacity(minCapacity); //容量已经大于了  Integer.MAX_VALUE - 8
        // 拷贝元素 到新的数组 , 容量为新的 newCapacity 
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
   // 确认最大的 容量 
    private static int hugeCapacity(int minCapacity) {
        // 当前存的 元素已经超过了Integer.MAX_VALUE
        if (minCapacity < 0) //int 溢出了  , 如:Integer.MAX_VALUE +1  =  -2147483648
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

>> : 右移运算符,num >> 1,相当于num除以2 高位补0。

扩容的大小为: 老的大小 + 老的大小/2 。 使用了 Arrays.copyOf 进行数组复制。

    public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }

    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
       
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }
    // src: 源数组  
    //srcPos:从源数组的 哪个位置开始拷贝   
    //dest:拷贝到哪个数组,目的数组 
    //destPos:从目的数组的哪个位置开始放元素
    // length : 拷贝的源数组的多少个元素
    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

通过调用native层的 System.arraycopy 来进行高效数组拷贝。拷贝时会在内存重新建立一个数组对象。

拷贝特点实践:

String[] src = {"aa","bb"} ;
System.err.println(src);  // [aa, bb]
src = Arrays.copyOf(src, 5) ;
System.err.println();     // [aa, bb, null, null, null]

拷贝后,以前的元素位置不变,但是实际占用空间还是扩大了的。要注意的是: 如果数组里面是对象的话,只是拷贝了对象的地址,而不是将对象也重新构造,也就是浅拷贝。

为什么是浅拷贝呢,我们分析JVM层代码才知道

// arraycopy 最终会调用到这里
void _Copy_conjoint_jints_atomic(jint* from, jint* to, size_t count) {
    if (from > to) {  // from: 源数组的起始头地址       to:为拷贝后的数组起始地址
      jint *end = from + count;  // 拷贝后数组的末尾地址
      while (from < end)  // 直到 地址考满到 end
        *(to++) = *(from++); // 将源的地址 直接赋值到 新的
    }
    else if (from < to) {  // 这里就是 缩容了
      jint *end = from;  // 思想也是一样,就是 地址一个一个复制
      from += count - 1;
      to   += count - 1;
      while (from >= end)
        *(to--) = *(from--);
    }
  }

可以看到我们地址就是把地址一个一个复制的,所以如果是对象的话,就是拷贝的对象地址。

add方法总结

  • ArrayList add时,先判断当前元素 + 1 也就是新的大小 超过了 elementData.length 数组容量,则进行grow扩容。
  • 扩容的新的大小为:oldCapacity +(oldCapacity >>1) 也就是扩大原来容量的 1/2 。
  • 扩容底层使用System.arraycopy ,直接进行地址的拷贝,效率高,但是如果是对象就是浅拷贝。
  • 扩容时会额外需要很大内存,我们应该避免ArrayList扩容导致OOM,应该尽量指定ArrayList大小。

给大家奉献一篇由于ArrayList扩容导致的OOM文章:

ArrayList 扩容导致的OOM 异常


remove 方法解析

    public E remove(int index) {
        // 保证移除的下标在 size之内
        rangeCheck(index);
        // 修改次数++
        modCount++;
       // 获取移除下标的元素
        E oldValue = (E) elementData[index];

        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

        return oldValue;
    }
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

移动的思想,比如我有一个占用5个元素的数组,remove(2)

执行System.arraycopy 过程

总结remove

  • 底层也是通过 System.arraycopy 实现地址覆盖。
  • 要移动的元素个数为remove下标后的所有元素。
  • 优点就是不会扩容。


contains源码

    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }
    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

遍历了一遍elementData , 通过对象的 equals 方法判断是否找到,找到了第一个就返回找到的下标位置,否则返回 -1 。


forEach源码

    public void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        // 修改次数
        final int expectedModCount = modCount;
        @SuppressWarnings("unchecked")
        final E[] elementData = (E[]) this.elementData;
        final int size = this.size;
        // 这里每遍历一次 就 比较修改次数是否变化 , 变化了就退出for
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            action.accept(elementData[i]);
        }
        if (modCount != expectedModCount) {
            // 抛出 遍历不可修改集合的异常
            throw new ConcurrentModificationException();
        }
    }

也是遵循了一个法则: 遍历集合时不可修改集合。


方法就分析了上面几个,其实还有很多重载的没讲,不过已经已经授人以渔了。相必自己也会看源码了吧。


强烈推荐一篇 干货,精华 博客:


JAVA架构师修炼

本文完~

支付宝打赏 微信打赏

如果文章对您有帮助,您可以鼓励一下作者