ArrayList集合源码阅读

骑猪看日落 2024-03-23 15:27 89阅读 0赞

#### 文章目录 ####

*  一. 知识点概述
 *  二. 源码阅读
 *   *  1. 类成员变量解释
     *  2. 重要方法分析
     *  3. 迭代器方法

## 一. 知识点概述 ##

ArrayList 是 Java 中的一种集合（Collection）类，它可以用来存储一组对象。下面是一些 ArrayList 的重要知识点：

1.  ArrayList 是动态数组，它的大小可以根据需要自动增长或缩小。
2.  ArrayList 是通过数组实现的，每个元素可以通过其索引进行访问。
3.  ArrayList 可以存储任意类型的对象，包括基本类型的包装器类和自定义对象。
4.  ArrayList 可以使用泛型来指定存储的对象类型，以增加类型安全性。
5.  ArrayList 可以使用 add() 方法添加元素，remove() 方法删除元素，get() 方法获取元素，set() 方法更新元素等。
6.  ArrayList 支持随机访问，它的 get() 方法的时间复杂度为 O(1)。
7.  ArrayList 是非线程安全的，多线程环境下应该使用线程安全的类或进行同步控制。
8.  ArrayList 与数组相比，它具有更强的灵活性和更多的功能，但在某些情况下可能会比数组效率低。
9.  ArrayList 可以使用迭代器（Iterator）来遍历集合中的元素。
10. ArrayList 可以使用 toArray() 方法将集合转换为数组。

总之，ArrayList 是 Java 中常用的一种集合类，它具有动态数组的特点，并提供了丰富的操作和功能，可以方便地操作集合中的元素。

## 二. 源码阅读 ##

### 1. 类成员变量解释 ###

private static final long serialVersionUID = 8683452581122892189L;
        private static final int DEFAULT_CAPACITY = 10;
        private static final Object[] EMPTY_ELEMENTDATA = {
        };
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
        };
        transient Object[] elementData; // non-private to simplify nested class access
        private int size;

> `serialVersionUID`：Serializable的版本控制号  
> `DEFAULT_CAPACITY`：默认初始化容量  
> `transient`：java 的transient关键字为我们提供了便利，你只需要实现Serilizable接口，将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中。  
> `size`：用来记录数组中的元素数

### 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() {
        
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
        public ArrayList(Collection<? extends E> c) {
        
            Object[] a = c.toArray();
            if ((size = a.length) != 0) {
        
                if (c.getClass() == ArrayList.class) {
        
                    elementData = a;
                } else {
        
                    elementData = Arrays.copyOf(a, size, Object[].class);
                }
            } else {
        
                // replace with empty array.
                elementData = EMPTY_ELEMENTDATA;
            }
        }

>  *  第一个构造函数，参数为用户传递的容量，如果容量大于0则创建一个指定容量的Object数组，如果是0则使用前面定义的EMPTY\_ELEMENTDATA空数组，小于0则抛出`IllegalArgumentException`异常
>  *  第二个构造函数为默认构造函数，直接使用前面定义的`DEFAULTCAPACITY_EMPTY_ELEMENTDATA`空数组
>  *  第三个构造函数，参数为其它集合数组 ，使用范型限定量集合数组的元素类型`<? extends E>`，其构造的原理是如果c类型是ArrayList类型直接赋值即可，否则使用`Arrays.copy()`方法将元素拷贝过来，`Arrays.copy()`方法的源码如下：

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

>  *  参数 ：`original`原始数组，`newLength`新数组长度，`newType`新数组类型
>  *  逻辑：该方法首先根据新数组类型创建一个新的数组对象，然后将原始数组中的元素复制到新数组中。如果新数组类型是Object\[\]，则直接创建一个Object类型的数组；否则，使用Array.newInstance()方法创建指定类型的数组。最后，将新数组返回。原始数组中从下标0开始的一部分元素会被复制到新数组中从下标0开始的位置。其中，Math.min(original.length, newLength)用于计算要复制的元素数量，取原始数组长度和新数组长度的最小值，以避免复制超出原始数组范围的元素。

*  trimToSize函数

public void trimToSize() {
        
            modCount++;
            if (size < elementData.length) {
        
                elementData = (size == 0)
                  ? EMPTY_ELEMENTDATA
                  : Arrays.copyOf(elementData, size);
            }
        }

>  *  介绍：将此 ArrayList 实例的容量修剪为列表的当前大小。应用程序可以使用此操作来最小化 ArrayList 实例的存储。  
>     \-`modCount`介绍：该变量的作用是用于支持集合类的fail-fast机制，当多个线程同时对同一个集合进行修改时，可能会导致集合状态不一致的情况。为了避免这种情况，Java集合类通常会在集合结构发生变化时，立即抛出`ConcurrentModificationException`异常。当集合类中的数据结构被修改时，modCount值会自增，用于表示集合被修改的次数。在遍历集合元素时，集合类会检查modCount值是否与预期值相等，如果不相等则表示集合已经被修改过，抛出`ConcurrentModificationException`异常。因此，该变量的作用是记录集合被修改的次数，以支持集合类的fail-fast机制。

**fail-fast机制**：fail-fast机制是Java集合框架中一种用于检测并发修改的机制，它的主要思想是：当多个线程对同一个集合进行并发修改时，如果有一个线程对集合进行了修改，那么其他线程访问集合时就有可能会抛出ConcurrentModificationException异常，以保证集合的数据一致性。Java集合类通常使用一个叫做“修改次数”的计数器来实现fail-fast机制。这个计数器会记录集合的修改次数，当集合的结构发生变化时，计数器的值会自增。在遍历集合时，Java集合类会检查计数器的值是否与预期值相等，如果不相等就会抛出ConcurrentModificationException异常。modCount就是Java集合框架中用来记录集合被修改次数的计数器，它在Java集合类中的具体实现可能会略有不同。在大部分集合类中，当集合发生结构性修改时（比如添加或删除元素），modCount就会自增，而在遍历集合时，集合类会记录modCount的值，并在每次遍历元素前检查modCount是否与之前记录的值相等。如果不相等，就表示集合被修改过，就会抛出ConcurrentModificationException异常，以保证集合的数据一致性。总之，Java集合框架中的fail-fast机制是通过修改次数计数器（如modCount）和检查机制来实现的，以保证多线程并发修改集合时的数据一致性和安全性。

*  ArrayList自动增长和缩小功能实现的源码

我们知道 ArrayList 是动态数组，它的大小可以根据需要自动增长或缩小。

public void ensureCapacity(int minCapacity) {
        
            int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                // any size if not default element table
                ? 0
                // larger than default for default empty table. It's already
                // supposed to be at default size.
                : DEFAULT_CAPACITY;
    //如果指定的容量大于，扩容操作的最小容量
            if (minCapacity > minExpand) {
        
                ensureExplicitCapacity(minCapacity);
            }
        }
        private void ensureExplicitCapacity(int minCapacity) {
        
            modCount++;
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
          private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
         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);
        }
        
         private static int hugeCapacity(int minCapacity) {
        
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }

>  *  `ensureCapacity`函数的作用是设置我们指定容量的动态数组，如果元素超过指定容量，就会自动调整大小这段代码方法中的参数`minCapacity`表示要确保ArrayList对象至少能够容纳minCapacity个元素。该方法首先会根据ArrayList对象的当前元素容量，判断是否需要进行扩容操作。如果ArrayList对象的元素容量已经大于指定容量minCapacity，则不需要进行任何操作；否则，就需要进行扩容操作。在这里，`minExpand`变量的值表示需要进行扩容操作的最小容量，它的计算方式是：如果ArrayList对象的elementData数组不是默认的空数组（DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA），则可以容纳任意数量的元素，因此minExpand的值为0；否则，如果ArrayList对象的elementData数组是默认的空数组，则minExpand的值为DEFAULT\_CAPACITY，表示需要扩容到默认的初始容量。如果指定的minCapacity大于minExpand，则需要调用ensureExplicitCapacity()方法进行实际的扩容操作。否则，不需要进行扩容操作。总之，该方法的作用是确保ArrayList对象能够容纳指定数量的元素，并在需要时进行扩容操作。
>  *  `ensureExplicitCapacity`：用来进行扩容操作，如果指定容纳的元素`minCapacity`大于当前数组中的元素个数，则调用`grow`方法实现扩容操作
>  *  `grow`方法就是扩容的主体函数了，它的逻辑是首先使用`oldCapacity`记录当前数组的容量，然后定义`newCapacity`为原来容量的1.5倍（右移一位相当于翻一倍），然后如果用户指定的最小容量`newCapacity`大于newCapacity，就将`newCapacity`设置为`minCapacity`，如果`newCapacity`大于`MAX_ARRAY_SIZE`则调用`hugeCapacity`设置容量。最后调用`Arrays.copyOf`实现扩容

*  ArrayList常见的增、删、改、查功能等其它功能源码

1.  返回ArrayList的元素个数

public int size() {
        
            return size;
        }

1.  判空

public boolean isEmpty() {
        
            return size == 0;
        }

1.  判断集合中是否有某个元素，以及某个元素在数组中的索引

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

> 还有一个`lastIndexOf`，即返回指定元素在ArrayList中的最后出现的位置，其实就是for反向遍历即可

1.  ArrayList克隆

public Object clone() {
        
            try {
        
                ArrayList<?> v = (ArrayList<?>) super.clone();
                v.elementData = Arrays.copyOf(elementData, size);
                v.modCount = 0;
                return v;
            } catch (CloneNotSupportedException e) {
        
                // this shouldn't happen, since we are Cloneable
                throw new InternalError(e);
            }
        }

> 具体来说，该方法首先调用 Object 类的 clone() 方法创建一个当前 ArrayList 实例的浅拷贝，即复制当前 ArrayList 实例的字段值（包括 elementData 数组和 size 等）到一个新的 ArrayList 实例中。然后，该方法使用 Arrays.copyOf(Object\[\] original, int newLength) 方法将 elementData 数组复制到新的 ArrayList 实例中，并将新 ArrayList 实例的 modCount 值设为 0，以确保新 ArrayList 实例的修改次数与原始 ArrayList 实例相同。最后，该方法返回新的 ArrayList 实例，即当前 ArrayList 实例的副本。需要注意的是，该方法只是创建了当前 ArrayList 实例的副本，并不会对其中的元素进行深度拷贝。因此，如果原始 ArrayList 实例中包含可变对象（如 ArrayList 或 HashMap 等），则对副本进行修改可能会影响原始 ArrayList 实例。

**浅拷贝和深拷贝**  
Java 中的浅拷贝和深拷贝是指对象复制时所采用的不同策略。浅拷贝：浅拷贝是指将一个对象复制到一个新的对象中，但是新对象与原始对象共享相同的子对象。简单来说，浅拷贝只复制对象本身，不会对对象内部的引用类型属性进行复制，新对象与原始对象共享同一个引用类型属性的内存地址。这意味着，如果对新对象的引用类型属性进行修改，原始对象也会受到影响。  
Java 中的 Object 类提供了一个默认的浅拷贝方法 clone()，可以通过重写该方法实现浅拷贝。深拷贝：深拷贝是指将一个对象复制到一个新的对象中，但是新对象与原始对象不共享任何子对象。简单来说，深拷贝会复制对象本身和对象内部所有的引用类型属性，新对象与原始对象之间互相独立，对新对象的任何修改都不会影响原始对象。Java 中实现深拷贝的方式有很多，常用的方法包括序列化和反序列化、递归遍历对象并创建一个新的对象等。需要注意的是，在对对象进行拷贝时，浅拷贝虽然比较简单高效，但是由于共享内存地址的关系，可能会出现对原始对象产生不可预测的影响，因此在需要完全独立的新对象时，应该采用深拷贝。

1.  将ArrayList转换为普通数组对象

public Object[] toArray() {
        
            return Arrays.copyOf(elementData, size);
        }

1.  获得指定索引位置的元素

E elementData(int index) {
        
            return (E) elementData[index];
        }
    
        public E get(int index) {
        
            rangeCheck(index);
    
            return elementData(index);
        }
     private void rangeCheck(int index) {
        
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

> 底层原理就是返回数组指定下标的元素，`rangeCheck`就是检查给定的index是否超出了数组的大小，是则抛出`IndexOutOfBoundsException`异常

1.  更改指定位置的元素

public E set(int index, E element) {
        
            rangeCheck(index);
    
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }

1.  添加元素
2.

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

> 首先调用`ensureCapacityInternal`来对数组扩容，然后加到数组最后面

1.  指定位置添加元素

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

> 原理就是，将原来数组的index后面的元素利用拷贝向后面移动一位，将index位置空出来，然后再把新的元素加入到这个位置即可  
> `System.arraycopy`它的作用是将一个数组中的指定范围的元素复制到另一个数组中的指定位置，参数介绍：  
> 1.源数组(Object src)：需要拷贝的源数组。  
> 2.源数组中的拷贝起始位置(int srcPos)：源数组中需要拷贝的起始位置，拷贝从该位置开始。  
> 3.目标数组(Object dest)：拷贝到目标数组中的目标数组。  
> 4.目标数组中的拷贝起始位置(int destPos)：目标数组中需要拷贝到的起始位置，拷贝从该位置开始。  
> 5.需要拷贝的元素个数(int length)：拷贝的元素个数，即从源数组中拷贝的元素个数。

1.  删除指定位置的元素

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

>  *  参数为数组下标，首先记录要删除的元素，然后同样使用 `System.arraycopy`将index+1后面的元素拷贝到index开始的位置，即覆盖了index出的元素，同时将数组最后一个元素设置为null，然后返回删除的元素即可

1.  按照元素内容删除元素

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

>  *  该函数会删除所有与参数匹配的元素，其原理是首先找到的指定元素在数组中的索引，然后调用`fastRemove`函数，按照锁索引对元素进行删除

1.  删除集合中所有元素

public void clear() {
        
            modCount++;
    
            // clear to let GC do its work
            for (int i = 0; i < size; i++)
                elementData[i] = null;
    
            size = 0;
        }

> 它将所有元素设置为空值，同时size设置为0

当然还有其它重要的方法，具体的原理实现方法都和上面介绍的类似，下面只做简单介绍：  
`public boolean addAll(int index, Collection<? extends E> c)`：在指定索引位置加入一个集合中所有元素，也是用的`System.arraycopy`方法  
`protected void removeRange(int fromIndex, int toIndex)`：删除指定范围的元素，也是`System.arraycopy`方法

### 3. 迭代器方法 ###

*  获取一个迭代器对象

public ListIterator<E> listIterator(int index) {
        
            if (index < 0 || index > size)
                throw new IndexOutOfBoundsException("Index: "+index);
            return new ListItr(index);
        }
     public ListIterator<E> listIterator() {
        
            return new ListItr(0);
        }

> 第一个：指定index位置的对象为迭代器指向的第一个元素  
> 第二个：指定0位置的对象为迭代器指向的第一个元素

*  内部类实现`Iterator`接口

private class Itr implements Iterator<E> {
        
            int cursor;       // index of next element to return
            int lastRet = -1; // index of last element returned; -1 if no such
            int expectedModCount = modCount;
    
            Itr() {
        }
    
            public boolean hasNext() {
        
                return cursor != size;
            }
    
            @SuppressWarnings("unchecked")
            public E next() {
        
                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;
                return (E) elementData[lastRet = i];
            }
    
            public void remove() {
        
                if (lastRet < 0)
                    throw new IllegalStateException();
                checkForComodification();
    
                try {
        
                    ArrayList.this.remove(lastRet);
                    cursor = lastRet;
                    lastRet = -1;
                    expectedModCount = modCount;
                } catch (IndexOutOfBoundsException ex) {
        
                    throw new ConcurrentModificationException();
                }
            }
    
            @Override
            @SuppressWarnings("unchecked")
            public void forEachRemaining(Consumer<? super E> consumer) {
        
                Objects.requireNonNull(consumer);
                final int size = ArrayList.this.size;
                int i = cursor;
                if (i >= size) {
        
                    return;
                }
                final Object[] elementData = ArrayList.this.elementData;
                if (i >= elementData.length) {
        
                    throw new ConcurrentModificationException();
                }
                while (i != size && modCount == expectedModCount) {
        
                    consumer.accept((E) elementData[i++]);
                }
                // update once at end of iteration to reduce heap write traffic
                cursor = i;
                lastRet = i - 1;
                checkForComodification();
            }
    
            final void checkForComodification() {
        
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
            }
        }

*  自定义迭代器对象

private class ListItr extends Itr implements ListIterator<E> {
        
            ListItr(int index) {
        
                super();
                cursor = index;
            }
    
            public boolean hasPrevious() {
        
                return cursor != 0;
            }
    
            public int nextIndex() {
        
                return cursor;
            }
    
            public int previousIndex() {
        
                return cursor - 1;
            }
    
            @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];
            }
    
            public void set(E e) {
        
                if (lastRet < 0)
                    throw new IllegalStateException();
                checkForComodification();
    
                try {
        
                    ArrayList.this.set(lastRet, e);
                } 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();
                }
            }
        }