ArrayList 源码阅读

灰太狼 2023-07-14 10:54 25阅读 0赞

class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable

因为数组比较重要，源码也好阅读，就找几个常用的记录一下，用到的或者自己理解能力上来后，慢慢的在深度阅读源码

1、数组默认的长度

> java jdk 1.8  
> 
>     private static final int DEFAULT_CAPACITY = 10;
> 
> ***ArrayList 默认的长度为 10***

2、ArrayList的有参构造，进行实例化数组容量

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

3、数组的toArray操作

public <T> T[] toArray(T[] a) {
            if (a.length < size)
                // Make a new array of a's runtime type, but my contents:
                return (T[]) Arrays.copyOf(elementData, size, a.getClass());
            System.arraycopy(elementData, 0, a, 0, size);
            if (a.length > size)
                a[size] = null;
            return a;
        }

其中的arrayCopy 调用了native的方法，实现了元素的拷贝

public static native void arraycopy(Object src,  int  srcPos,
                                            Object dest, int destPos,
                                            int length);

4、set方法，替换特定位置的元素

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

首先进行数组长度的判断，避免数组越界，所以在foreach或者for循环，进行remove操作，影响了原有的数组长度，就会数组越界

5、add方法：add方法比较特殊，涉及自动扩容，***一般浮动默认容量的一半***

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

注意此处的modCount ，事实上线程安全本身就不允许读的时候被修改，

private void ensureCapacityInternal(int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    
            ensureExplicitCapacity(minCapacity);
        }
    
        private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }

扩容操作：

如果add操作的下标不超过原集合长度的一半，不进行扩容；如果下标过大，会扩容值整型的最大值（详见源码）

/**
         * Increases the capacity to ensure that it can hold at least the
         * number of elements specified by the minimum capacity argument.
         *
         * @param minCapacity the desired minimum capacity
         */
        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;
        }

6、add (index, element) 操作

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

这个方法和add（e）还不同，如果数组下标超过当前的集合下标，不会自动扩容，而是提示越界

/**
         * A version of rangeCheck used by add and addAll.
         */
        private void rangeCheckForAdd(int index) {
            if (index > size || index < 0)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

然后实现替换原有属性的操作，

7、remove（index）删除操作，此处调用了GC操作

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

8、remove(Element)操作：底层的fastRemove也是循环遍历当前元素的下表，然后调用remove(index)删除操作

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

9、clear操作：实现数组的清理操作，全部置为null

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

10.addAll() 也是用到了扩容操作

public boolean addAll(Collection<? extends E> c) {
            Object[] a = c.toArray();
            int numNew = a.length;
            ensureCapacityInternal(size + numNew);  // Increments modCount
            System.arraycopy(a, 0, elementData, size, numNew);
            size += numNew;
            return numNew != 0;
        }

11、forEach方法

@Override
        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 (int i=0; modCount == expectedModCount && i < size; i++) {
                action.accept(elementData[i]);
            }
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
        }

12、sort操作

@Override
        @SuppressWarnings("unchecked")
        public void sort(Comparator<? super E> c) {
            final int expectedModCount = modCount;
            Arrays.sort((E[]) elementData, 0, size, c);
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            modCount++;
        }

public static <T> void sort(T[] a, int fromIndex, int toIndex,
                                    Comparator<? super T> c) {
            if (c == null) {
                sort(a, fromIndex, toIndex);
            } else {
                rangeCheck(a.length, fromIndex, toIndex);
                if (LegacyMergeSort.userRequested)
                    legacyMergeSort(a, fromIndex, toIndex, c);
                else
                    TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
            }
        }

用到的这个并么有读懂，说以前的是用comparator进行的比较，然后用了系统的拷贝，不能使用静态的boolean在循环依赖中，在以后的版本将会被淘汰

/**
         * Old merge sort implementation can be selected (for
         * compatibility with broken comparators) using a system property.
         * Cannot be a static boolean in the enclosing class due to
         * circular dependencies. To be removed in a future release.
         */
        static final class LegacyMergeSort {
            private static final boolean userRequested =
                java.security.AccessController.doPrivileged(
                    new sun.security.action.GetBooleanAction(
                        "java.util.Arrays.useLegacyMergeSort")).booleanValue();
        }

sort底层用了comparable的比较，然后使用swap进行交换位置

private static void mergeSort(Object[] src,
                                      Object[] dest,
                                      int low,
                                      int high,
                                      int off) {
            int length = high - low;
    
            // Insertion sort on smallest arrays
            if (length < INSERTIONSORT_THRESHOLD) {
                for (int i=low; i<high; i++)
                    for (int j=i; j>low &&
                             ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                        swap(dest, j, j-1);
                return;
            }
    
            // Recursively sort halves of dest into src
            int destLow  = low;
            int destHigh = high;
            low  += off;
            high += off;
            int mid = (low + high) >>> 1;
            mergeSort(dest, src, low, mid, -off);
            mergeSort(dest, src, mid, high, -off);
    
            // If list is already sorted, just copy from src to dest.  This is an
            // optimization that results in faster sorts for nearly ordered lists.
            if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
                System.arraycopy(src, low, dest, destLow, length);
                return;
            }
    
            // Merge sorted halves (now in src) into dest
            for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
                if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
                    dest[i] = src[p++];
                else
                    dest[i] = src[q++];
            }
        }

此处的不同分支，在jdk1.8之后用了二分法，这个方法比较好，以后可能会用这个方法

private static <T> void binarySort(T[] a, int lo, int hi, int start,
                                           Comparator<? super T> c) {
            assert lo <= start && start <= hi;
            if (start == lo)
                start++;
            for ( ; start < hi; start++) {
                T pivot = a[start];
    
                // Set left (and right) to the index where a[start] (pivot) belongs
                int left = lo;
                int right = start;
                assert left <= right;
                /*
                 * Invariants:
                 *   pivot >= all in [lo, left).
                 *   pivot <  all in [right, start).
                 */
                while (left < right) {
                    int mid = (left + right) >>> 1;
                    if (c.compare(pivot, a[mid]) < 0)
                        right = mid;
                    else
                        left = mid + 1;
                }
                assert left == right;
    
                /*
                 * The invariants still hold: pivot >= all in [lo, left) and
                 * pivot < all in [left, start), so pivot belongs at left.  Note
                 * that if there are elements equal to pivot, left points to the
                 * first slot after them -- that's why this sort is stable.
                 * Slide elements over to make room for pivot.
                 */
                int n = start - left;  // The number of elements to move
                // Switch is just an optimization for arraycopy in default case
                switch (n) {
                    case 2:  a[left + 2] = a[left + 1];
                    case 1:  a[left + 1] = a[left];
                             break;
                    default: System.arraycopy(a, left, a, left + 1, n);
                }
                a[left] = pivot;
            }
        }

13、modCount 解释

> 在ArrayList的所有涉及结构变化的方法中都增加modCount的值，包括：add()、remove()、addAll()、removeRange()及clear()方法。这些方法每调用一次，modCount的值就加1。

这位仁兄讲的可以 [https://blog.csdn.net/qq\_24235325/article/details/52450331][https_blog.csdn.net_qq_24235325_article_details_52450331]

[https://blog.csdn.net/qq\_35275233/article/details/104864063][https_blog.csdn.net_qq_35275233_article_details_104864063]

使用modCount和expectModCount 主要还是避免同时add或者set造成的并发冲突，但是modCount没有用volatile修改，所以多线程不可见，fail-fast不能保证一定成功

[https_blog.csdn.net_qq_24235325_article_details_52450331]: https://blog.csdn.net/qq_24235325/article/details/52450331
[https_blog.csdn.net_qq_35275233_article_details_104864063]: https://blog.csdn.net/qq_35275233/article/details/104864063