ArrayList源码解读

NullPointer 发表于 2016-11-15 11:26

public class ArrayList<E> extends AbstractList<E>
   implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;

/**
* ArrayList的元素的数组缓冲区存储（存放ArrayList集合的元素）
* transient：只能用来修饰字段，在对象序列化的过程中，带有此修饰符修饰的字段是不会被序列化的
* 例如：User类有userName和transient password，那么序列化User类的时候password是不会被序列化的，所以反序列化拿出password也是null
*/
private transient Object[] elementData;

/**
* 数组的长度
*
* @serial
*/
private int size;

/**
* 带参构造器：需要传入一个初始容量，默认构造器是10字节，此构造器可以自定义大小。
*
* @paraminitialCapacity初始容量
* @throws IllegalArgumentException 若初始容量小于0，则抛出异常
*/
public ArrayList(int initialCapacity) {
   //调用父类构造器
super();
//若初始容量小于0，则抛出异常。
   if (initialCapacity < 0)
         throw new IllegalArgumentException("Illegal Capacity: "+
                                          initialCapacity);
   //若初始容量大于等于0，则new一个容量为initialCapacity的Object数组，并赋给elementData数组
   this.elementData = new Object;
}

/**
* 空构造器，默认占用是个字节，意思就是：当我们new ArrayList();的时候其实new出来的集合是占用十字节的空间的
*/
public ArrayList() {
//调用带参构造器，并初始容量为10
   this(10);
}

/**
* 带参构造器：传入一个集合，然后将传入的集合赋给elementData，长度赋给size
*
* @param c 传入的集合
*/
public ArrayList(Collection<? extends E> c) {
//将传入的集合转化为数组，赋给elementData
   elementData = c.toArray();
   //将传入的集合的长度赋给size
   size = elementData.length;
   //c.toArray可能返回的不是Object数组，有时候会存在这个bug。(see 6260652)，所以加此判断
   if (elementData.getClass() != Object[].class)
      //若elementData（c.toArray()）不是数组类型，则进行数组的复制，复制的类型为Object数组
         elementData = Arrays.copyOf(elementData, size, Object[].class);
}

/**
* 将数组缓冲区大小调整到实际ArrayList存储元素的大小，释放掉add时候扩充1.5倍后产生的那些null
* 即：elementData = Arrays.copyOf(elementData, size);
* 该方法由用户手动调用，以减少空间资源浪费的目的。
*/
public void trimToSize() {
//modCount是AbstractList的属性，protected transient int modCount = 0;
//modCount好比计数器，每次对List进行增删操作modCount都会进行++操作
   modCount++;
   //将数组缓冲区大小(可能比size大，因为扩充1.5倍后用null占位，也可能如调用默认构造函数后，刚添加一个元素，此时 elementData.length = 10，而 size = 1)赋值给oldCapacity
   int oldCapacity = elementData.length;
   //如果实际大小小于数组缓冲区大小
   if (size < oldCapacity) {
      //通过这一步，可以使得空间得到有效利用，而不会出现资源浪费的情况
      //将数组缓冲区elementData变为实际存储大小。
         elementData = Arrays.copyOf(elementData, size);
   }
}

/**
* 检查数组是否需要进行扩容
* @param minCapacity：最小容量
*/
private void ensureCapacityInternal(int minCapacity) {
   modCount++;
   // 防止溢出代码：确保指定的最小容量大于数组缓冲区当前的长度
   //若最小容量大于当前数组缓冲区长度，则对数组进行1.5倍扩容，否则出现数组下标越界异常。
   if (minCapacity - elementData.length > 0)
      //1.5倍扩容
         grow(minCapacity);
}

/**
* 数组缓冲区（elementData）的最大存储容量
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
* 扩容，以确保ArrayList至少能存储minCapacity个元素
*/
private void grow(int minCapacity) {
   // 将缓冲区长度复制给oldCapacity
   int oldCapacity = elementData.length;
   //将原有缓冲区长度进行1.5倍扩容
   int newCapacity = oldCapacity + (oldCapacity >> 1);
   // 若 newCapacity 依旧小于 minCapacity
   if (newCapacity - minCapacity < 0)
         newCapacity = minCapacity;
   // 若 newCapacity 大于最大存储容量，则进行大容量分配
   if (newCapacity - MAX_ARRAY_SIZE > 0)
      //进行大容量分配
         newCapacity = hugeCapacity(minCapacity);
   // 对数组进行扩容
   elementData = Arrays.copyOf(elementData, newCapacity);
}

/**
* 大容量分配，最大分配Integer.MAX_VALUE
* @param minCapacity
* @return
*/
private static int hugeCapacity(int minCapacity) {
   if (minCapacity < 0) // overflow
         throw new OutOfMemoryError();
   return (minCapacity > MAX_ARRAY_SIZE) ?
         Integer.MAX_VALUE :
         MAX_ARRAY_SIZE;
}

/**
* 返回数组的长度
*/
public int size() {
   return size;
}

/**
* 判断集合是否为空
*
* @Return true：数组长度为0；false：数组长度不为0
*/
public boolean isEmpty() {
   return size == 0;
}

/**
* 判断集合中是否包含此元素
*
* @return true：包含；false：不包含
*/
public boolean contains(Object o) {
   return indexOf(o) >= 0;
}

/**
* 返回第一次出现的指定元素的索引,-1代表此元素不再集合内
*/
public int indexOf(Object o) {
//如果传入的数据是null
   if (o == null) { //判断null是为了防止空指针
      //遍历集合
         for (int i = 0; i < size; i++)
            //如果集合中存在null元素，则返回null在此集合中的位置
            if (elementData==null)
               return i;
   } else {//如果传入的数据不是null
      //遍历集合
         for (int i = 0; i < size; i++)
            //如果集合中存在传入的此元素，则返回此元素在集合中的位置
            if (o.equals(elementData))
               return i;
   }
   return -1;
}

/**
* 返回最后一次出现的指定元素的索引,-1代表此元素不再集合内
*/
public int lastIndexOf(Object o) {
//如果传入的数据是null
   if (o == null) { //判断null是为了防止空指针
      //遍历集合，从最后一个往前面遍历，目的是找到最后一次出现的指定元素的位置
         for (int i = size-1; i >= 0; i--)
            //如果集合中存在null元素，则返回null在此集合中的位置
            if (elementData==null)
               return i;
   } else {//如果传入的数据不是null
      //遍历集合，从最后一个往前面遍历，目的是找到最后一次出现的指定元素的位置
         for (int i = size-1; i >= 0; i--)
            //如果集合中存在传入的此元素，则返回此元素在集合中的位置
            if (o.equals(elementData))
               return i;
   }
   return -1;
}

/**
* 返回一个浅拷贝的ArrayList
*
*/
public Object clone() {
   try {
         @SuppressWarnings("unchecked")
            ArrayList<E> v = (ArrayList<E>) super.clone();
         //复制数组elementData到v.elementData
         v.elementData = Arrays.copyOf(elementData, size);
         //数组变化的次数设置为0
         v.modCount = 0;
         return v;
   } catch (CloneNotSupportedException e) {
         // this shouldn't happen, since we are Cloneable
         throw new InternalError();
   }
}

/**
* 将集合转化为Object数组
*/
public Object[] toArray() {
   return Arrays.copyOf(elementData, size);
}

/**
* 根据下标从集合中取出元素
*/
public E get(int index) {
//检查是否会发生异常
   rangeCheck(index);
   //直接返回数组中第index个位置的元素值
   return elementData(index);
}

/**
* 在第index位置插入element元素
*
* @param index 集合中第index位置
* @param element 插入的新元素
* @return 插入新元素之前的集合中第index位置元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
//检查是否会发生异常
   rangeCheck(index);
   //先从集合中取出下标为index的的元素值，赋值给oldValue
   E oldValue = elementData(index);
   //将新元素重新赋值给elementData
   elementData = element;
   //返回插入新元素之前的集合中第index位置元素（旧数据）
   return oldValue;
}

/**
* 将元素添加到集合
*
* @param e 元素
*/
public boolean add(E e) {
//数组扩容
   ensureCapacityInternal(size + 1);// Increments modCount!!
   //有了上一步的操作，此步骤就不会出现数组下标越界的情况
   elementData = e;
   return true;
}

/**
* 在指定位置插入指定元素
*
* @param 指定位置
* @param 元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
//检查异常
   rangeCheckForAdd(index);
//数组扩容
   ensureCapacityInternal(size + 1);// Increments modCount!!
   //System.arraycopy(src, srcPos, dest, destPos, length);
   //第一个是要复制的数组，第二个是从要复制的数组的第几个开始，第三个是复制到那，四个是复制到的数组第几个开始，最后一个是复制长度
   System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
   elementData = element;
   size++;
}

/**
* 从集合中移除下标为index的元素
*
* @param 自定义下标
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
   //检查异常
rangeCheck(index);

   modCount++;
   //找到index的元素值
   E oldValue = elementData(index);

   int numMoved = size - index - 1;
   if (numMoved > 0)
         System.arraycopy(elementData, index+1, elementData, index,
                        numMoved);
   //将最后一个元素设置为null
   elementData[--size] = null; // Let gc do its work
   //返回被移除的值
   return oldValue;
}

/**
* 清空数组
*/
public void clear() {
   modCount++;

   //循环当前数组
   for (int i = 0; i < size; i++)
      //将数组的每一个元素都设置为null
         elementData = null;
   //长度设置为0
   size = 0;
}

/**
* 安全措施：检查是否会发生数组下标越界异常
*/
private void rangeCheck(int index) {
//如果传入的长度大于数组的长度，则抛出异常
   if (index >= size)
         throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
* 安全措施：检查是否会发生数组下标越界异常
*/
private void rangeCheckForAdd(int index) {
//如果传入的长度大于数组的长度，或小于0则抛出异常
   if (index > size || index < 0)
         throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}

InvictusLee 发表于 2016-11-15 11:48

厉害了我的哥！

NullPointer 发表于 2016-11-15 11:50

InvictusLee 发表于 2016-11-15 11:48
厉害了我的哥！

以后我会定期发送源代码解读或者读书知识总结，共同学习:handshake

liujm23 发表于 2016-11-15 11:54

学习了谢谢楼主分享

kydi.y 发表于 2016-11-15 12:03

总结的很好，谢谢分享！

NullPointer 发表于 2016-11-15 12:04

kydi.y 发表于 2016-11-15 12:03
总结的很好，谢谢分享！

:handshake共同学习

NullPointer 发表于 2016-11-15 12:07

liujm23 发表于 2016-11-15 11:54
学习了谢谢楼主分享

共同学习

wwwmaopu1201 发表于 2016-11-15 17:38

大神膜拜一下热心值必须都给你{:1_918:}

tiancaizaizuo 发表于 2016-11-15 17:40

必须支持

NullPointer 发表于 2016-11-16 10:02

psx1lin 发表于 2016-11-15 22:53
学习了谢谢楼主分享

共同学习

页: [1]

吾爱破解 - 52pojie.cn's Archiver

ArrayList源码解读