首页 > 技术交流 > ArrayList源码解析

ArrayList源码解析

头像
菜粥 #java#
发布于 2021-02-25 22:32:47 APP内打开
赞 2 | 收藏 6 | 回复1 | 浏览1215

实现的接口

  • 本文基于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;
    }

1条回帖

回帖
加载中...
话题 回帖

推荐话题

相关热帖

技术交流近期热帖

近期精华帖

热门推荐