每周源码:如何实现ArrayList(分析ArrayList的源码)

Author Avatar
清水雅然君 06月 15,2020

Java集合(Collection)类是我们在工作中运用最多的、最频繁的类。并且集合可以动态扩容。方便开发需求。
集合类通常存在于java.util包中,主要由Collection和Map两个体系构成。

  • Collection主要有三个子接口,分别为List(列表)、Set(集)、Queue(队列)。其中,List、Queue中的元素有序可重复,而Set中的元素无序不可重复;
  • List中主要有ArrayList、LinkedList两个实现类;Set中则是有HashSet(底层HashMap),treeSet(底层TreeMap)实现类;
  • Map中都是以key-value的形式存在,其中key必须唯一,主要有HashMap、HashTable(线程安全)、TreeMap(红黑树)三个实现类。
  • set的底层是维护了map,只用了map的key,这便是为什么元素无序,并且不能重复,另一面也反应出了,map允许value的为null;反而List、Queue的底层是数组或者链表,可以允许元素的有序可重复。

有兴趣可以看一下LinkedList的源码,他实现了Queue接口,同时也实现了List,具有两者的特性。

A collection represents a group of objects
collection类型用来表示表示一组对象。

所以map不符合Collection类的要求,map没有继承Collection接口,而是重新定义了map接口,符合接口隔离原则。

List

在List集合中,我们常用到ArrayList和LinkedList这两个类。

其中,ArrayList底层通过数组实现,随着元素的增加而动态扩容。而LinkedList底层通过链表来实现,随着元素的增加不断向链表的后端增加节点。

这里可以看出,当数据量比较大的时候,ArrayList读取速度高于LinkedList,而写入的数据低于LinkedList的。

所以我们今天便要借鉴源码实现一个ArrayList。

List接口

可以看出源码继承了Collection接口

public interface List<E> extends Collection<E> {
}

我们先定义一个MyList类,将源码的方法提取放到类中

public interface MyList<E> {

    boolean add(E e);

    void add(int index,E e);

    int size();

    boolean isEmpty();

    boolean contains(E e);

    void clear();

    E remove(int index);
   //这个方法是list添加
    E get(int index);

}

其中 void add(int index,E e); E get(int index);属于list添加的方法

List实现类

定义一个MyArrayList类实现MyList接口,并且实现接口的方法

public class MyArrayList<E>  implements MyList<E> {
}

变量

在实现方法之前,我们先定义几个常量和构造方法

    transient Object[] elementData;

由于ArrayList底层是数组,先定义数组变量


private  int size;
//数组的默认大小
private static final int DEFAULT_CAPACITY = 10;
//数组的最多扩容大,一般达不到,会直接内存溢出
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

以上三个变量,用于list的容量上,定义了数组的大小和扩容的上限

private static final Object[] EMPTY_ELEMENTDATA = {};

定义默认的空对象

构造方法

    public MyArrayList(int initialCapacity) {
        if(initialCapacity<0){
            throw new IllegalArgumentException("初始化大小异常"+initialCapacity);
        }
        elementData=new Object[initialCapacity];
    }
    public MyArrayList() {
        this.elementData = new Object[DEFAULT_CAPACITY];
    }

从这里的源码可以看出,ArrayList默认数组大小为10,也可以自定义数组的大小,要求数组不能小于,不然会抛出初始化的异常,不过,如果能确定list的长度时,还是建议最好定义ArrayList的大小,避免数组的频繁扩容

实现方法

add

不指定数组的下标

 @Override
    public boolean add(Object e) {
        //扩容数组
        ensureCapacityInternal(size + 1); 
        elementData[size++] = e;
        return true;
    }

指定数组下标

   @Override
    public void add(int index, Object element) {
        //校验下标是否正常
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);
        //调用系统的方法进行复制,这里将index的位置后移,不过,存在浅拷贝的问题
        System.arraycopy(elementData, index, elementData, index + 1,
                size - index);
        elementData[index] = element;
        size++;
    }

可以看出无论那种方法的添加元素,list都会先进行扩容ensureCapacityInternal然后再插入,这里就会出现一个问题了?会不会频繁扩容导致资源的消耗?
答案是不会 ,可以看一下源码中ensureCapacityInternal的实现,可以看到源码中一共4个方法完成了数组的扩容。

    private void ensureCapacityInternal(int minCapacity) {
    
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
  • 如果数组为一个空对象,则默认从当前的需要扩容的大小和默认大小比较,取其中大的一个值,进行扩容,所以数组的默认大小是10,除非进行了数组的大小定义。
      private void ensureExplicitCapacity(int minCapacity) {
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
  • 只要当扩容大小大于当前的数据大小才能进行扩容,这里边可以看出数组,并不是每次都进行扩容的,假设当前数组大小是15,我存入第13个元素,数组还有空余位置,先存入,并不进行扩容
  • elementData.length的扩容大小默认为elementData.length的1.5倍,假设数组当前大小为10,当存入第11个元素时,触发扩容的添加大小,会变成15
    这是源码的写法int newCapacity = oldCapacity + (oldCapacity >> 1);

位运算a>> 1。右移1一位,相当于a/2,如果a>> 2,类似a/4,相当于后面的移动的n,a/2^n;
如果左移动就是相乘。
1<< a=22;2<<2=24

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;
        //扩容到 Integer.MAX_VALUE - 8 大小
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
            //数组扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

超大的扩容判断,这里可以看出,list并不是无限,最大扩容大小为 Integer.MAX_VALUE, 不过一般不会有一个list的大小能达到这个,首先内存就可能会溢出
在这里插入图片描述
其次,一个list的个数达到Integer.MAX_VALUE,它的读取和存入可以想象

可以认为list是一个无限大,虽然存在一个无法达到的边界

  private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) 
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }
size/isEmpty

这两个方法实现比较简单

   @Override
    public int size() {
        return size;
    }

返回当前的size即可,虽然全文并没有初始化size,如果是int变量定义的全局变量或者静态变量,未初始化的话就是0.

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

判断当前的list是否为空,只要判断size是否大于0即可

contains

判断是否包含某元素,由于list是允许重复的,在源码执行的时候,会遍历整个数组,然后equals数组的值,存在返回下标,然后判断下标是否大于0

@Override
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                //list 可以空值
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

1.从源码看,list允许存入null值
2.如果list存在重复值的话,默认返回第一个元素的下标

clear
  @Override
    public void clear() {
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

遍历将数组的每个元素清空,同时将size归零,但是数组并没有进行清空,这里避免了数组的再次添加元素后再次扩容,如果后期不进行操作add操作,还是存在资源的浪费,所以如果list只用一次,那么可以在调用clear之后把list也设置为null来释放全部的内存。便于gc进行回收

list.clear();
list = null;
remove

对list元素的remove,从底层来看还是对数组的操作,即将数组下标的后一个元素,往前移动一位到需要移除的数组下标位置,同时数组的最后一位的元素清空。
在这里插入图片描述

 @Override
    public E remove(int index) {
        rangeCheck(index);
        E oldValue = elementData(index);
        int numMoved = size - index - 1;
        if (numMoved > 0)
        //复制数组
            System.arraycopy(elementData, index+1, elementData, index,
                    numMoved);
        //移除最后一位
        elementData[--size] = null;
        return oldValue;
    }
    E elementData(int index) {
        return (E) elementData[index];
    }
    //检查下标
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
get

get方法就比较简单了,返回相应的数组下标的元素就可以了

@Override
    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }

测试
    public static void main(String[] args) {
        MyList<Integer> list=new MyArrayList<>();
        for (int i = 0; i <10 ; i++) {
            list.add(i);
        }
        list.add(11);
        System.out.println("读取");
        System.out.println("i="+list.contains(50));
        System.out.println("i="+list.remove(1));
        //由于移除了一位,会抛出下标越界的异常
        for (int i = 0; i <10 ; i++) {
            System.out.println("i="+list.get(i));
        }
    }

在这里插入图片描述

扩展

1.fail-fast

在用迭代器遍历一个集合对象时,如果遍历过程中对集合对象的内容进行了修改(增加、删除、修改),则会抛出Concurrent Modification Exception。

那怎么知道在遍历过程中了出现了修改操作?
modCount记录了使用ArrayList的添加、修改、删除的更改次数

The number of times this list has been structurally modified.

expectedModCount 在源码可以看到如下代码

int expectedModCount = ArrayList.this.modCount;

当迭代器在遍历对象的时候,会将存储的expectedModCount和当前的modCount进行对比,出现不等于的时候,便抛出异常。

 final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}

2.线程不安全
ArrayList是线程不安全,从源码便可以看到,没有加锁的操作,也没有任何原子操作,当多线程操作类的时候,可能会出现下标越界的问题或者覆盖的原来的值的问题
我们可以进行测试

 public static void main(String[] args) {
        List<Integer> list=new ArrayList<>();
        Thread A= new Thread(()-> {
                for (int i = 0; i < 1000 ; i++) {
                    list.add(i);

                    try {
                        Thread.sleep(1);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
        });

        // 线程B将1000-2000添加到列表
        Thread B=new Thread(()->{
                for (int i = 1000; i < 2000 ; i++) {
                    list.add(i);

                    try {
                        Thread.sleep(1);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }

        });
        A.start();
        B.start();
        try {
            A.join();
            B.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("赋值结束");
        System.out.println("list的大小"+list.size());
        // 打印所有结果
      /*  for (int i = 0; i < list.size(); i++) {
            System.out.println("第" + (i + 1) + "个元素为:" + list.get(i));
        }*/
    }

运行结果
在这里插入图片描述
换成线程安全的Vector和CopyOnWriteArrayList进行测试

  //List<Integer> list=new Vector<>();
List<Integer> list=new CopyOnWriteArrayList<>();

在这里插入图片描述

源码

public class MyArrayList<E>  implements MyList<E> {
    private static final Object[] EMPTY_ELEMENTDATA = {};

    
    transient Object[] elementData;

    private  int size;

    private static final int DEFAULT_CAPACITY = 10;

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    public MyArrayList(int initialCapacity) {
        if(initialCapacity<0){
            throw new IllegalArgumentException("初始化大小异常"+initialCapacity);
        }
        elementData=new Object[initialCapacity];
    }


    public MyArrayList() {
        this.elementData = new Object[DEFAULT_CAPACITY];;
    }


    @Override
    public boolean add(Object e) {
        //扩容数组
        ensureCapacityInternal(size + 1); 
        elementData[size++] = e;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //扩容大小在之前的数组大小的1/2
        int newCapacity = oldCapacity + (oldCapacity >> 1);

        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //扩容到 Integer.MAX_VALUE - 8 大小
        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;
    }
    @Override
    public void add(int index, Object element) {
        //校验下标是否正常
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);
        System.arraycopy(elementData, index, elementData, index + 1,
                size - index);
        elementData[index] = element;
        size++;
    }
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }
    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                //list 可以空值
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
    @Override
    public void clear() {
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);
        E oldValue = elementData(index);
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                    numMoved);
        elementData[--size] = null;
        return oldValue;
    }

    E elementData(int index) {
        return (E) elementData[index];
    }
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    @Override
    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }




}

结尾(解决线程安全问题)

目前,笔者在看JUC这块的源码,拖了两周才写了这篇源码的读书笔记,其实ArrayList的源码整体上去掉Iterator这块的代码,其实并不是很复杂,在抽取出关键代码后,大概200行不到,
从源码中,可以看出,
1.当数据量很大的情况下,ArrayList存在很大的性能问题,比如当数组的grow、remove方法,当数据量比较大的时候,在数组的复制上比较占用时间;
2.取值快,由于底层是维护了一个数组,只要下标就可以获取到值,反观LinkedList的取值需要遍历链表,查询的速度比ArrayList慢
3.线程不安全,这是Vector源码add方法的操作,使用synchronized 保证了方法的独占

  public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

CopyOnWriteArrayList使用了lock 方法

  public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

Collections.synchronizedList,使用了synchronized锁对象

 public void add(int index, E element) {
            synchronized (mutex) {list.add(index, element);}
        }

实现CAS

其实也可以使用CAS的方式实现一个无锁线程安全的list(其实和直接使用lock差不多),贴上基于unsafe类实现CAS锁的代码,这里是一个独占锁的写法,也可以考虑基于AQS,使用LockSupport实现线程的阻塞和唤醒,但是都无法脱离unsafe类这个基石,希望在某一天,可以自己写一个unsafe类,接下来,我想查看AQS源码,然后基于它实现lock

   private static final Unsafe unsafe;

    private static final long valueOffset;

    private volatile int value;

    static {
        try {
            Field f = Unsafe.class.getDeclaredField("theUnsafe");
            f.setAccessible(true);
            unsafe = (Unsafe) f.get(null);
            valueOffset = unsafe.objectFieldOffset
                    (MySafeArrayList.class.getDeclaredField("value"));
        } catch (Exception ex) {
            throw new Error(ex);
        }
    }
//尝试获取许可
    void tryAcquire() {
        for (; ; ) {
            if (value == 1) {
            //当发现其他线程获取到锁,线程释放掉当前的cpu时间,继续等待
                Thread.yield();
            } else if (compareAndSet(value, 1))
                break;
        }

    }


    private boolean compareAndSet(int expect, int update) {
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);

    }

//释放资源
    void tryRelease() {
        compareAndSet(value, 0);
    }

调用的时候类似lock

 @Override
    public boolean add(Object e) {
        tryAcquire();
        //扩容数组
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        tryRelease();
        return true;

    }

然后测试一下,我们的锁,测试方法和上面的测试代码一样,使用两个线程进行插入
在这里插入图片描述