Java集合-ArrayList

参考文献

• Collection - ArrayList 源码解析
• 死磕 java集合之ArrayList源码分析

ArrayList-JDK8

属性

/**
 * 该常量代表ArrayList默认的初始化容量，实际上这个值在ArrAyList中的使用非常少
    * 只出现在ArrayList第一次确认容量的时候——而且还是在默认情况下
    * Default initial capacity.
    */
   private static final int DEFAULT_CAPACITY = 10;

   /**
    * 该常量值是在ArrayList初始化的时候使用，用来将elementData数组赋值为一个没有元素的空数组。
    * 注意：只是在初始化时使用
    * 空数组,用于空实例的共享空数组实例(若传入的容量为0时使用).
    * Shared empty array instance used for empty instances.
    */
   private static final Object[] EMPTY_ELEMENTDATA = {};

   /**
    * 该常量值在ArrayList第一次被添加元素时使用，用来作为在默认的情况下ArrayList第一次扩容大小的判定依据
    * 注意：只是在第一次扩容时使用
    * 空数组,传传入容量时使用,添加第一个元素的时候会重新初始为默认容量大小
    * Shared empty array instance used for default sized empty instances. We
    * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
    * first element is added.
    */
   private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

   /**
    * 该变量和Vector容器中的同名变量意义相同，都是实际用来存储ArrayList中的各个元素数据
    * The array buffer into which the elements of the ArrayList are stored.
    * The capacity of the ArrayList is the length of this array buffer. Any
    * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    * will be expanded to DEFAULT_CAPACITY when the first element is added.
    */
   transient Object[] elementData; // non-private to simplify nested class access

   /**
   * 该变量用于记录当前ArrayList容器的大小，类似于Vector容器的elementCount变量
    * 真正存储元素的个数,而不是elementData数组的长度.
    * The size of the ArrayList (the number of elements it contains).
    *
    * @serial
    */
   private int size;

构造函数

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // 若传入的初始容量大于0,则新建一个数组来存储元素
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 若传入初始容量等于0,则使用空数组EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        // 若传入的初始容量小于0,则抛出异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                initialCapacity);
    }
}

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    // 若没有传入初始容量,则使用空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    // 使用这个数组是在添加第一个元素的时候会扩容到默认大小10
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {
    // 集合转数组
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        // 检查c.toArray()返回的是不是ArrayList
        if (c.getClass() == ArrayList.class) {
            // 若是则直接将转换后的集合赋值给elementData
            elementData = a;
        } else {
            // 不是则,重新拷贝成Object[].class类型
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // 如果c是空集合,则初始化为空数组EMPTY_ELEMENTDATA
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

添加方法

 /**
    * Appends the specified element to the end of this list.
    *
    * @param e element to be appended to this list
    * @return <tt>true</tt> (as specified by {@link Collection#add})
    */
   public boolean add(E e) {
       // 检查是否需要扩容
       ensureCapacityInternal(size + 1);  // Increments modCount!!
       // 把元素插入到最后一位
       elementData[size++] = e;
       return true;
   }
private void ensureCapacityInternal(int minCapacity) {
       // 若是空数组,就初始化为默认大小DEFAULT_CAPACITY
       if (elementData == EMPTY_ELEMENTDATA) {
           minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
       }

       ensureExplicitCapacity(minCapacity);
   }

   private void ensureExplicitCapacity(int minCapacity) {
       modCount++;

       // 若申请的容量minCapacity大于现在元素的个数,则表示需要进行扩容
       // overflow-conscious code
       if (minCapacity - elementData.length > 0)
           // 扩容操作
           grow(minCapacity);
   }

   /**
    * The maximum size of array to allocate.
    * Some VMs reserve some header words in an array.
    * Attempts to allocate larger arrays may result in
    * OutOfMemoryError: Requested array size exceeds VM limit
    */
   private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

   /**
    * 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;
       // 扩容后的容量,即旧的容量的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();
       // 选出minCapacity大于MAX_ARRAY_SIZE则将容量设置为Integer.MAX_VALUE,否则设置为MAX_ARRAY_SIZE
       return (minCapacity > MAX_ARRAY_SIZE) ?
           Integer.MAX_VALUE :
           MAX_ARRAY_SIZE;
   }    

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    // 检查是否越界
    rangeCheckForAdd(index);
    // 检查是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将index极其之后的元素往后挪一位,则index的位置就空出来了
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 将元素插入到index的位置
    elementData[index] = element;
    // 元素个数增加1
    size++;
}

/**
 * A version of rangeCheck used by add and addAll.
 */
private void rangeCheckForAdd(int index) {
    // 若要插入的位置小于0或大于元素容量则抛出异常
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
   * Appends all of the elements in the specified collection to the end of
   * this list, in the order that they are returned by the
   * specified collection's Iterator.  The behavior of this operation is
   * undefined if the specified collection is modified while the operation
   * is in progress.  (This implies that the behavior of this call is
   * undefined if the specified collection is this list, and this
   * list is nonempty.)
   *
   * @param c collection containing elements to be added to this list
   * @return <tt>true</tt> if this list changed as a result of the call
   * @throws NullPointerException if the specified collection is null
   */
  public boolean addAll(Collection<? extends E> c) {
      // 将集合转为数组
      Object[] a = c.toArray();
      // 要新增的元素个数
      int numNew = a.length;
      // 检查是否需要扩容
      ensureCapacityInternal(size + numNew);  // Increments modCount
      // 将c中元素全部拷贝到数组的最后
      System.arraycopy(a, 0, elementData, size, numNew);
      // 大小增加c的个数
      size += numNew;
      // 若c不为空就返回true,否则返回false
      return numNew != 0;
  }

获取元素

/**
   * Returns the element at the specified position in this list.
   *
   * @param  index index of the element to return
   * @return the element at the specified position in this list
   * @throws IndexOutOfBoundsException {@inheritDoc}
   */
  public E get(int index) {
      // 检查是否越界
      rangeCheck(index);
      // 返回数组index位置的元素
      return elementData(index);
  }
  @SuppressWarnings("unchecked")
  E elementData(int index) {
      return (E) elementData[index];
  }

删除元素

/**
  * Removes the element at the specified position in this list.
  * Shifts any subsequent elements to the left (subtracts one from their
  * indices).
  *
  * @param index the index of the element to be removed
  * @return the element that was removed from the list
  * @throws IndexOutOfBoundsException {@inheritDoc}
  */
 public E remove(int index) {
     // 检查是否越界
     rangeCheck(index);

     modCount++;
     // 获取index位置的元素
     E oldValue = elementData(index);

     
     int numMoved = size - index - 1;
     if (numMoved > 0)
         // 若index不是最后一位,则将index之后的元素往前挪一位
         System.arraycopy(elementData, index+1, elementData, index,
                          numMoved);
     // 将最后一个元素删除,帮助GC
     elementData[--size] = null; // clear to let GC do its work

     // 返回删除的元素的值
     return oldValue;
 }

/**
     * Removes the first occurrence of the specified element from this list,
     * if it is present.  If the list does not contain the element, it is
     * unchanged.  More formally, removes the element with the lowest index
     * <tt>i</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
     * (if such an element exists).  Returns <tt>true</tt> if this list
     * contained the specified element (or equivalently, if this list
     * changed as a result of the call).
     *
     * @param o element to be removed from this list, if present
     * @return <tt>true</tt> if this list contained the specified element
     */
    public boolean remove(Object o) {
        if (o == null) {
            // 遍历整个数组,找到元素第一次出现的位置,并将其快速删除
            for (int index = 0; index < size; index++)
                // 若要删除的元素为null
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            // 遍历整个数组,找到元素第一次出现的位置,并将其快速删除
            for (int index = 0; index < size; index++)
                // 若要删除的元素不为null,与要删除的元素进行比较,相同则快速删除
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

    /*
     * Private remove method that skips bounds checking and does not
     * return the value removed.
     */
    private void fastRemove(int index) {
        // fastRemove(int index)相对于remove(int index)少了检查索引越界的操作
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            // 如果index不是最后一位,则将index之后的元素往前挪一位
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 将最后一个元素删除,帮助GC
        elementData[--size] = null; // clear to let GC do its work
    }

序列化

/**
  * Save the state of the <tt>ArrayList</tt> instance to a stream (that
  * is, serialize it).
  *
  * @serialData The length of the array backing the <tt>ArrayList</tt>
  *             instance is emitted (int), followed by all of its elements
  *             (each an <tt>Object</tt>) in the proper order.
  */
 private void writeObject(java.io.ObjectOutputStream s)
     throws java.io.IOException{
     // 防止序列化期间有修改
     // Write out element count, and any hidden stuff
     int expectedModCount = modCount;
     // 写出非transient非static属性(会写出size属性)
     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();
     }
 }

 /**
  * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
  * deserialize it).
  */
 private void readObject(java.io.ObjectInputStream s)
     throws java.io.IOException, ClassNotFoundException {
     // 声明为空数组
     elementData = EMPTY_ELEMENTDATA;

     // 读入非transient非static属性(会读取size属性)
     // 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
         // 检查容量
         ensureCapacityInternal(size);

         Object[] a = elementData;
         // 依次读取元素到数组中
         // Read in all elements in the proper order.
         for (int i=0; i<size; i++) {
             a[i] = s.readObject();
         }
     }
 }

Fail-Fast机制

• ArrayList也采用了快速失败的机制,通过记录modCount参数来实现.在面对并发的修改时,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险.

ArrayList中的elementData为什么被修饰transient

• 在Java中,ArrayList 是一个动态数组,用来存储一组对象.在ArrayList 的实现中,有一个成员变量elementData 用来存储实际的元素数据.这个变量被声明为transient ,原因是ArrayList 类实现了Serializable接口,需要将对象序列化并保存到磁盘或网络中,而elementData 不需要被序列化,因此需要将其标记为transient .

• 当一个ArrayList 对象被序列化时,Java会将其所有的非transient 成员变量都保存到序列化流中,以便在反序列化时重新构造对象.而被transient 修饰的变量不会被保存到序列化流中,因此在反序列化时,这些变量的值将被初始化为默认值（如0、false、null等）.对于ArrayList 来说,如果不将elementData 标记为transient ,那么序列化时会将整个数组保存到序列化流中,占用大量的存储空间,而在反序列化时,需要重新构造这个数组,增加了反序列化的时间和存储开销.

• 需要注意的是,elementData 被声明为private,因此只有ArrayList 类内部才能访问它.当ArrayList 对象被序列化时,Java会调用ArrayList 的writeObject()方法,该方法会将elementData 数组的内容写入序列化流中.在反序列化时,Java会调用ArrayList 的readObject()方法,该方法会从序列化流中读取elementData 数组的内容,并重新构造ArrayList 对象.

• 综上所述,将elementData标记为transient 可以减少序列化和反序列化时的存储空间和时间开销,提高程序的性能和效率.

有哪几种实现ArrayList线程安全的方法

• 使用Collection.synchronizedList包装ArrayList,然后操作包装后的list
• 使用CopyOnWriteArrayList代替ArrayList
• 使用ArrayList时,应用程序通过同步机制去控制ArrayList的读写