搜索
您的当前位置：首页正文

Java集合类一：ArrayList（底层源码分析）

来源：好走旅游网

一、宏观关系

二、数据结构

 //默认初始容量
 private static final int DEFAULT_CAPACITY = 10;
 //数组的最大容量
 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 //一个空的数组实例
 private static final Object[] EMPTY_ELEMENTDATA = {};
 //一个空的默认大小的数组实例
 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 
 //存放数据的数组
 transient Object[] elementData;
 //记录数组的大小
 private int size;
 //记录集合结构被修改的次数
 protected transient int modCount = 0;

1、EMPTY_ELEMENTDATA

当调用有参构造指定容量的时候，会把数组elementData指向它。减少空数组频繁创建的内存开销。

2、DEFAULTCAPACITY_EMPTY_ELEMENTDATA

调用ArrayList的无参构造器的时候，会把数组elementData指向它。

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

思考1：为什么要区分为两个空数组实例呢，直接一个不行么？
是为了优化性能和内存使用：

  • EMPTY_ELEMENTDATA 允许 ArrayList 在不需要存储任何元素时不分配任何内存。
  • DEFAULTCAPACITY_EMPTY_ELEMENTDATA 允许 ArrayList 在添加第一个元素时直接扩展到一个合理的默认容量，而不是从一个非常小的容量开始逐步扩容，这样可以减少扩容操作的次数，提高性能。
    这种设计使得 ArrayList 能够在不同场景下灵活地管理内存，同时保持了添加元素时的高效性。

3、elementData

细心的肯定发现，elementData是用transient关键字来修饰的。

思考2：为什么要用transient来修饰呢？
ArrayList通过重写writeObject和readObject方法来实现自定义序列化，只将必要的元素序列化。（具体后面会分析）
——使用transient关键字修饰elementData数组的好处是，它允许ArrayList在序列化时只关注实际存储的数据，而不是整个数组的容量。这样可以使得序列化过程更加高效，并且可以根据需要调整序列化的细节。例如，如果ArrayList中的某些元素是临时的或者不需要序列化，那么可以通过这种方式来避免不必要的序列化操作。

4、modCount

是Java集合类中的一个保护级别的字段，记录集合结构被修改的次数（改变集合大小或者以其他方式干扰正在进行的迭代器遍历的操作，如添加、删除或替换集合中的元素。）

作用：支持 Java 集合的 fail-fast 迭代器机制
——————
fail-fast（快速失败）迭代器会在迭代过程中抛出 ConcurrentModificationException 异常，以响应不可预测的并发修改。这种机制确保了在迭代过程中，如果有其他线程对集合进行了结构性修改，迭代器能够及时检测到这种修改并报错，从而避免出现不确定的行为。

这里就想到了平时会遇到的一种实际情况：

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");

//使用for循环
for (int i = 0; i < list.size(); i++) {
    if (list.get(i).equals("b")) {
        list.remove(i); // 可能会抛出 ConcurrentModificationException
    }
}

//使用迭代器
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    if (item.equals("b")) {
        iterator.remove(); // 安全的，不会抛出 ConcurrentModificationException
    }
}

思考3：为什么用for循环会抛出异常，而用迭代器不会呢？
这里就和modCount相关，当对集合进行删除/添加操作的时候，modCount就会++

  • for循环的时候
    modCount值更改了，和迭代器在创建时会记录当前的 modCount 值不一致。迭代器就会抛出异常。
  • 迭代器遍历的时候
    如果你使用迭代器自带的 remove 方法删除元素，迭代器会更新其内部状态，包括 expectedModCount，以匹配集合的最新状态。因此，使用迭代器的 remove 方法删除元素是安全的，不会抛出 ConcurrentModificationException。

三、构造函数

1、无参构造

（上面已有，不做赘述）

2、有参构造

//指定容量大小
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);
        }
}

//传入集合
public ArrayList(Collection<? extends E> c) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
            	//如果传入集合也是ArrayList，就直接把elementData执行toArray后的数组a
                elementData = a;
            } else {
            	//如果不是，就调用Arrays.copyOf方法把a赋值给elementData
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
}

思考4：为什么要用Arrays.copyOf（）

  • 确保类型兼容
    传入的集合通过toArray方法返回一个数组，但是这个数组的类型不一定就是Object[]（可能存在向上转型的情况）。用Arrays.copyOf()的方法能确保新数组的类型是Object[]
  • 安全性
    如果 c 是 ArrayList，c.toArray() 返回的数组实际上是 String[] 类型，如果直接将这个数组赋值给 elementData，而 elementData 期望的是 Object[] 类型，那么在尝试存储非字符串类型的 Object 时，就会抛出 ArrayStoreException。
    总之使用 Arrays.copyOf() 可以确保无论 c.toArray() 返回什么类型的数组，最终 elementData 总是 Object[] 类型，从而避免了潜在的类型问题

四、成员方法

1、add相关方法

》不带参数

public boolean add(E e) {
        //扩容判断后才赋值
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
}

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
		//如果是无参构造的空数组，那么就去默认容量10和传入容量的大者；否则直接为传入容量
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
}

//保证显式的容量
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        //如果需要的容量比目前数组的长度更大，就调用grow进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
}

//扩容
private void grow(int minCapacity) {
        
        int oldCapacity = elementData.length;
        //扩容1.5倍
        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);
}

//校验处理
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
}

总结：

  • 懒初始化，如果是第一次添加元素，会直接给默认的初始容量10。
  • 之后每次超出就会新建一个1.5倍大的数组（如果仍然不够就直接赋值当前最小需要的容量值），将旧数组中的所有元素复制到新数组中。然后把内部的数组引用指向新的数组，旧数组的引用会丢失，然后被垃圾回收。
    这个复制过程是通过System.arraycopy()方法完成的，这是一个高效的数组复制方法。

》带参数

public void add(int index, E element) {
        //范围检查
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
}

private void rangeCheckForAdd(int index) {
		//这个就是我们常见的数组下标越界异常
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

2、remove相关方法

 public E remove(int index) {
        //范围检查
        rangeCheck(index);

        modCount++;
        E oldValue = 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));
}

3、clear()

public void clear() {
    // 将 size 设置为 0，表示没有元素
    size = 0;
    // 将数组中的所有元素位置置为 null，以帮助垃圾回收
    for (int i = 0; i < size; i++) {
        elementData[i] = null;
    }
}

注意：clear之后只是把内部数组元素个数size置为0，但是内部数组的内存空间大小是不变的。

4、序列化方法

》writeObject()

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioural compatibility with 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();
        }
    }

writeObject方法在序列化的时候调用，负责把ArrayList的状态写入到ObjectOutputStream。
这个方法会先写modCount，然后写入ArrayList的实际大小size，最后逐个写入存储在elementData中的数据。

》readObject()

private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in capacity
        s.readInt(); // ignored

        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            int capacity = calculateCapacity(elementData, size);
            SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

readObject方法在反序列化的时候调用，负责从ObjectInputStream中读取ArrayList的状态。这个方法先读取modCount和size。然后根据读取的大小创建一个新的elementData数组，并且逐个读取元素来填充到这个数组中。

5、内部迭代器相关

public Iterator<E> iterator() {
        return new Itr();
}
//迭代器的内部类
private class Itr implements Iterator<E> {
        int cursor;       // 下一个要返回元素的下标
        int lastRet = -1; // 最近一次返回元素的下标，在调用next() 或 previous() 方法时，lastRet 都会被更新为返回元素的索引
        int expectedModCount = modCount;

		Itr() {}
		public boolean hasNext() {
            return cursor != size;
        }

		@SuppressWarnings("unchecked")
        public E next() {
        	//modCount检查
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            //返回元素，并且更新lastRet
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                //remove后会把lastRet设置为-1，防止连续调用remove
                lastRet = -1;
                //更新expectedModCount为当前值
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
       }
      
       public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
       }

		//判断modCount与最开始记录的是否一致
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
        
        @SuppressWarnings("unchecked")
        public E previous() {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[lastRet = i];
        }
}

从上述可以看出，ArrayList有一个内部迭代器，每次在调用next()、add()、remove()方法时，都会先判断modCount和expectedModCount是否相等，不相等说明在迭代期间是否被更改过表结构。
————
而上文提到的用迭代器的remove、add不会报错，就是因为内部迭代器在调用这些方法后，会把expectedCount更新。

注意：
remove方法使用lastRet来定位删除元素的，所以remove得在 previous() 、next()之后调用。如果 lastRet 为 -1，表示没有元素被迭代，那么调用 remove() 或 set() 就是非法的，迭代器也会抛出 IllegalStateException 异常。

五、总结

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

Copyright © 2019- 版权所有

Top