ArrayList源码解读(JDK 8)

男娘i 2024-03-17 14:26 12阅读 0赞

## ArrayList源码解读(JDK 8) ##

ArrayList作为数组型链表，它继承于AbstractList类，并实现于RandomAccess、Serializable、Cloneable、List接口，从继承实现关系来看， 他实现了Serializable、Cloneable使其具有了可序列化和可克隆的机制;它实现了RandomAccess接口使其具有快速随机访问的机制;而List接口他又实现了Collection使其具有了集合的特性。对于Collection接口又实现了Iterable使集合具有了迭代遍历、for-each的特性。对于AbstractList他是对List的一个抽象在其中完成了对List以最大程度地减少实现由“随机访问”数据存储（如数组）支持的此接口所需的工作量。以及对像LinkedList这样的链表式结构采用顺序读的方式。对源码进行查看时，ArrayList的任意方法上均没有加synchronized以及相关的锁机制，所以他是线程不安全的。  
![在这里插入图片描述][19c091155cf94f94a0746e1010e625fe.png_pic_center]

### 源码之旅 ###

1.  属性解释
    
        //无参创建的默认容量
         private static final int DEFAULT_CAPACITY = 10;
         //一个空的元素数组
         private static final Object[] EMPTY_ELEMENTDATA = {
              };
         //用无参构造创建时默认为该对象
         private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
              };
         //元素数组 
         transient Object[] elementData;
         //元素个数
         private int size;
         //最大数组长度 减8的目的为了数据的正确性
         private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    注:transient关键字表示不希望该属性被序列化
2.  构造方法
    
        //无参构造直接将DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋给elementData
        //此时的elementData长度还未0，并不为10,这是jdk7后期版本的一个改变，当他在第一次给其添加元素时才会被扩容为10
         public ArrayList() {
              
             this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
         }
         /**
          * 入参: 初始化容量大小
          * 大于0时直接创建一个指定大小的Object数组并赋给elementData
          * 等于零时就将EMPTY_ELEMENTDATA的成员赋给它
          * 小于0时直接报错
          */
         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);
             }
         }
         /**
          *入参: 继承于E的任意类型(包含E)的Collection集合
          * 将c转为数组对象
          * 将a.length 的长度赋给size 
          * 如果为0则将空数组赋给elementData
          * 如果不为零就判断c个字节码是不是ArrayList的字节码对象一致，如果一致直接赋* 值，
          * 如果不是调用Arrays.copyof方法将数组a中的元素size大小后a中的元素复制到新的数组中并返回，赋给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 {
              
                 elementData = EMPTY_ELEMENTDATA;
             }
         }
    
    注:
    
    1.  <?> 支持任意类型
    2.  <? extends A> 继承于A的任意类型(包含A),规定上限
    3.  <? super A> A类以及A的父类,规定下限
3.  扩容方法
    
        public void ensureCapacity(int minCapacity) {
              
             //如果elementData与DEFAULTCAPACITY_EMPTY_ELEMENTDATA相等就将DEFAULT_CAPACITY 10 给minExpand,不等就为0
             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;
             /**
              * 如果minExpand不能满足需要就进行再次扩容
              */
             if (minCapacity > minExpand) {
              
                 ensureExplicitCapacity(minCapacity);
             }
         }
        
         private static int calculateCapacity(Object[] elementData, int minCapacity) {
              
             if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
              
                 //在需要的容量在和DEFAULT_CAPACITY的比较取大的
                 return Math.max(DEFAULT_CAPACITY, minCapacity);
             }
             //如果不相等，取需要的容量
             return minCapacity;
         }
        
         private void ensureCapacityInternal(int minCapacity) {
              
             ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
         }
        
         private void ensureExplicitCapacity(int minCapacity) {
              
             modCount++;
             /**
              * 需要的容量和elementData长度比较如果大于0则需要扩容
              */
             if (minCapacity - elementData.length > 0)
                 grow(minCapacity);
         }
        
        
         private static int hugeCapacity(int minCapacity) {
              
             //超出int 的范围溢出 minCapacity小于0 直接OOM
             if (minCapacity < 0) 
                 throw new OutOfMemoryError();
             //如果大于MAX_ARRAY_SIZE就用Integer.MAX_VALUE为容量，如果小于就用规定的最大容量，即Integer.MAX_VALUE-8
             return (minCapacity > MAX_ARRAY_SIZE) ?
                 Integer.MAX_VALUE :
                 MAX_ARRAY_SIZE;
         }
        
         private void grow(int minCapacity) {
              
             /**
              * 原来的数组长度
              */
             int oldCapacity = elementData.length;
             //将新容量扩大到原来的i.5倍
             //(oldCapacity >> 1)使容量的大小缩小一半  即 6 --> 0b0110 计算后 0b0011
             int newCapacity = oldCapacity + (oldCapacity >> 1);
             //如果扩容之后的仍然小于它要求的，就将要求的赋给新的容量
             if (newCapacity - minCapacity < 0) 
                 newCapacity = minCapacity;
             //如果newCapacity大于最大ArrayList最大的容量
             if (newCapacity - MAX_ARRAY_SIZE > 0)
                 newCapacity = hugeCapacity(minCapacity);
             //将新的容量赋给elementData
             elementData = Arrays.copyOf(elementData, newCapacity);
         }
    
        public boolean add(E e) {
              
             //扩容并修改modCount
             ensureCapacityInternal(size + 1);  // Increments modCount!!
             elementData[size++] = e;
             return true;
         }
         /**
          *入参:添加元素的位置索引,元素
          */
         public void add(int index, E element) {
              
             rangeCheckForAdd(index);  //检查是否越界 越界报错
             //修改modCount
             ensureCapacityInternal(size + 1);  // Increments modCount!!
             System.arraycopy(elementData, index, elementData, index + 1,
                              size - index);//将元素的0~index-1 和 index+1到size-index进行复制,也就是说将index这个位置给空出来 
             elementData[index] = element;//将index位置的数组赋值
             size++; //增加数组中的元素个数
         }
    
        private void rangeCheckForAdd(int index) {
              
            if (index > size || index < 0)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 
        }
    
        /**
         * 入参:对象
         */
         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; //未找到返回负数
        }
4.  移除
    
        public E remove(int index) {
              
            rangeCheck(index); //检查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; //让gc销毁
        
            return oldValue; //放回移除对象
        }
        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;//未找到删除失败 
        }
5.  清空
    
        public void clear() {
              
                modCount++;
                for (int i = 0; i < size; i++)
                    elementData[i] = null; //将所有的elementData元素置空
                size = 0;
            }
6.  批量删除
    
        private boolean batchRemove(Collection<?> c, boolean complement) {
              
             final Object[] elementData = this.elementData;
             int r = 0, w = 0;
             boolean modified = false;
             //存在即删除
             try {
              
                 for (; r < size; r++)
                     if (c.contains(elementData[r]) == complement)
                         elementData[w++] = elementData[r];
             } finally {
              
                 if (r != size) {
              
                     System.arraycopy(elementData, r,
                                      elementData, w,
                                      size - r);
                     w += size - r;
                 }
                 if (w != size) {
              
                     for (int i = w; i < size; i++)
                         elementData[i] = null;
                     modCount += size - w;
                     size = w;
                     modified = true;
                 }
             }
             return modified;
         }
7.  排序
    
        /**
          * 本质调用的Arrays.sort的方法
          */
         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++;
         }

mparator<? super E> c) \{  
final int expectedModCount = modCount;  
Arrays.sort((E\[\]) elementData, 0, size, c);  
if (modCount != expectedModCount) \{  
throw new ConcurrentModificationException();  
\}  
modCount++;  
\}

[19c091155cf94f94a0746e1010e625fe.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/cd4a572215f64d1283add3044bf3c80b.png