菜粥

发布于 2021-02-25 22:32

ArrayList源码解析精

实现的接口

本文基于Oracle JDK1.8展开讨论
ArrayList位于java.util包下

ArrayList类的声明：

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

ArrayList继承了AbstractList，看AbstractList源码，实现了List接口

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>

而ArrayList再次实现了List接口，不觉得多余吗？实际上，这么设计是有原因的：
List接口里面包含了很多方法，实现了List接口的类要重新全部的方法，而且各自的实现类具体的方法实现是不一样的，比如ArrayList和LinkedList对于add的具体实现肯定是不一样的。
但是ArrayList和LinkedList对于某些方法的实现是一模一样的，比如size()方法
这时候，如果每增加一个List的实现类，都要重复的写一些方法体一模一样的方法，无法复用代码
这时候就利用了设计模式里的模板方法模式，把List的实现类的共有方法抽象到AbstractList里，并提供默认的实现，这样下层的实现类继承了AbstractList，直接继承共有的方法，而不需要重复的写一些代码

RandomAccess
此接口为一个空接口，目的是加快ArrayList随机访问的速度
```
public interface RandomAccess {}
```
Cloneable
此接口为一个空接口，实现了后可以重写clone方法实现深拷贝
```
public interface Cloneable {}
```
java.io.Serializable

此接口为一个空接口，目的是方便序列化

public interface Serializable {}

成员变量

  /**
   * 序列化ID
   */
  private static final long serialVersionUID = 8683452581122892189L;

  /**
   * 默认初始化容量
   */
  private static final int DEFAULT_CAPACITY = 10;

  /**
   * 创建一个空ArrayList时，赋值使用
   */
  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;

构造函数

共三个构造函数

无参构造函数

public ArrayList() {
      this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  }
//elementData 为存放数据的数组
transient Object[] elementData;    
//无参初始化时，赋值为一个空的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

根据容量初始化构造函数

public ArrayList(int initialCapacity) {
      if (initialCapacity > 0) {
          //根据容量生成一个Object数组
          this.elementData = new Object[initialCapacity];
      } else if (initialCapacity == 0) {
          //参数等于0 则赋值一个空数组
          this.elementData = EMPTY_ELEMENTDATA;
      } else {
          throw new IllegalArgumentException("Illegal Capacity: "+
                                             initialCapacity);
      }
  }

根据现有List初始化构造函数

public ArrayList(Collection<? extends E> c) {
      elementData = c.toArray();
      if ((size = elementData.length) != 0) {
          //如果返回的不是Object[]类型 则进行复制操作，Arrays.copyOf底层调用的System.arraycopy()
          if (elementData.getClass() != Object[].class)
              elementData = Arrays.copyOf(elementData, size, Object[].class);
      } else {
          // replace with empty array.
          this.elementData = EMPTY_ELEMENTDATA;
      }
  }

clone方法

public Object clone() {
      try {
          //先调用父类的clone克隆
          ArrayList<?> v = (ArrayList<?>) super.clone();
          //底层还是调用System.arraycopy();
          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(e);
      }
  }

get方法

```java
public E get(int index) {

  //首先检查index是否合法
  rangeCheck(index);

  return elementData(index);

}
/**

检查index是否合法

/
private void rangeCheck(int index) {

   if (index >= size)
       throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}

/**
*返回index 位置的元素
*/
E elementData(int index) {
return (E) elementData[index];
}

### set方法
```java
public E set(int index, E element) {
        //检查index是否合法
        rangeCheck(index);
        //取出旧元素
        E oldValue = elementData(index);
        //把index位置的元素替换为新元素
        elementData[index] = element;
        return oldValue;
}

add方法：此处会产生扩容

public boolean add(E e) {
        //确定容量是否足够 不够则扩容
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
}

private void ensureCapacityInternal(int minCapacity) {
        //如果数组为空数组 即第一次add元素 取一个最大的Capacity 
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

private void ensureExplicitCapacity(int minCapacity) {
        //修改次数+1
        modCount++;

        //如果需要的Capacity 大于当前elementData的长度 则需要扩容
        if (minCapacity - elementData.length > 0)
            //扩容
            grow(minCapacity);
}

扩容机制 grow(minCapacity);

private void grow(int minCapacity) {
        // 记录旧容量
        int oldCapacity = elementData.length;
        //新容量为  旧容量+ 旧容量的1/2
        //这里使用了移位运算 右移一位相当于除以2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //取一个最大值
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果新容量超过Integer.MAX_VALUE - 8 则把newCapacity赋值为Integer.MAX_VALUE
        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;
    }

remove方法

public E remove(int index) {
        //检查下标是否合法
        rangeCheck(index);

        //修改次数+1
        modCount++;
        //保存旧值
        E oldValue = elementData(index);

        //删除元素后 数组需要移动的元素数量
        int numMoved = size - index - 1;
        if (numMoved > 0)
            //移动数组
            System.arraycopy(elementData, index + 1, elementData, index,
                    numMoved);
        //置为null 方便gc
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

clear方法

public void clear() {
        //修改次数+1
        modCount++;

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

        size = 0;
    }

addAll方法

public boolean addAll(int index, Collection<? extends E> c) {
        //检查下标是否合法
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        //判断是否需要扩容
        ensureCapacityInternal(size + numNew);  // Increments modCount

        //计算需要移动的元素数量
        int numMoved = size - index;
        //此处的移动是把index之后的元素后移numMoved个 目的是给下面插入的元素腾出位置
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                    numMoved);
        //把数据插入index处
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
}

迭代器

public Iterator<E> iterator() {
        //平时使用的迭代器 实际上是ArrayList的一个内部类Itr
        return new Itr();
}

迭代器解析

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
      //此处注意！！！  在获取迭代器的时候，expectedModCount只会被赋值一次
      // 所以当外部的modCount改变之后，内部类的expectedModCount并不会改变
      int expectedModCount = modCount;

      /**
       *判断是否有下一个元素
       */
      public boolean hasNext() {
          //直接判断游标是否==size
          return cursor != size;
      }

      @SuppressWarnings("unchecked")
      public E next() {
          //判断修改版本是否一致
          checkForComodification();
          int i = cursor;
          //下标大于size 抛出异常
          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();
      }
  }

其他方法

    /**
     * 获取元素数量
     */
    public int size() {
        return size;
    }

    /**
     * 判断是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
    * 判断是否包含元素o 这里就是调用indexOf 看一下元素的索引是不是>0
     */
    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 {
            //不为空 则遍历数组 使用equals判断
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

2025最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

已采纳

采纳

精彩回帖

精彩

全部评论

(1) 回帖

加载中...

话题同步到我的动态回帖

ArrayList源码解析精

实现的接口

RandomAccess

Cloneable

java.io.Serializable

成员变量

构造函数

clone方法

get方法

add方法：此处会产生扩容

扩容机制 grow(minCapacity);

remove方法

clear方法

addAll方法

迭代器

其他方法

已采纳

精彩回帖

全部评论

推荐话题

近期热帖

热门推荐

ArrayList源码解析 精

实现的接口

RandomAccess

Cloneable

java.io.Serializable

成员变量

构造函数

clone方法

get方法

add方法：此处会产生扩容

扩容机制 grow(minCapacity);

remove方法

clear方法

addAll方法

迭代器

其他方法

已采纳

精彩回帖

全部评论

推荐话题

相关热帖

近期热帖

热门推荐

ArrayList源码解析精