从源码深入底层解析Java的数组列表ArrayList

滴一盘技术
2020-06-19 10:00:30
技术资源分享

在数据结构中有学习到数字列表就是对数组的各种操作，其实Java的ArrayList类也是这样的，说白点就是对数组的get,add,set,remove,和遍历这几种操作。

读ArrayList的源码前，我要说几个方法:
在System类里有这个方法:

public static native void arraycopy(Object src, int srcPos, Object dest, int destPos,int length);
这个方法只有定义，却没有实现，方法用了一个native来修饰。native的方法，是由其它语言来实现的，一般是(C或C++)，所以这儿没有实现代码。这是一个数组拷贝方法，我们只要记得这个方法就是用来将src数组里的元素的值赋值给dest数组的元素，其实srcPos指定从src数组的第几个元素开始赋值，而length是指定src数组将来赋值几个元素给dest，destPos指定赋值到dest的第几个元素开始。

Arrays的几个方法，其实这几个方法于是封装System类的arraycopy


 public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }
public static <T,U> T[] copyOf(U[] original, int newLength, Class extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

这2个方法就是会把原数组original赋值成新的一个数组，其中newLength是新数组的长度。

ArrayList一直维护transient Object[] elementData这个数组。


/**
 * 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

我们知道要知道数组大小，我们就要用length这个属性就行，但是我们要知道数组保存了多少元素，就只能遍历了，于是ArrayList保存了一个size，用来记录当前数组保存了多少元素。


/**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;

创建ArrayList

其中ArrayList给了我们3种构造函数，分别是


public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    public ArrayList(Collection extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

当你没有传入参数时，会默认给我创建的数组大小是10
当你传入初始化大小时，对其判断，如果大于1就创建数组你指定的数组，如果是0，就创建空数组，或抛出异常。
当你用其他ArrayList初始化时，用了Arrays.copyOf()进行数组的重新赋值，把传入进来的赋值成新的elementData数组。
ArrayList的get方法
这个最简单了，数组列表相比于链表，获取元素最简单，根据索引就行。用E对其进行强制转换，从这我们可以看出ArrayList保存的都是Object。


 E elementData(int index) {
        return (E) elementData[index];
    }
 public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }
其中 rangeCheck(index);是判断索引是否大于size。

  private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
ArrayList的set方法
这个也是简单，先判断索引是否大于size，然后保存旧的值，再重新赋值，返回旧的值。

 public E set(int index, E element) {
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

ArrayList的add方法
这个方法有点复杂，因为我们初始化时，数组是有大小的，当你再添加新元素之前，要先判断是否数组已经满了，如果满了，就要对其进行扩容。
add(E e)


 public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 对其进扩容判断
        elementData[size++] = e;
        return true;
 }
 private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
private void ensureExplicitCapacity(int minCapacity) {
        modCount++; //记录数组结构改变的次数，包括增加，删除操作都会记录
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
 private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length; //获取旧数组的长度
        int newCapacity = oldCapacity + (oldCapacity >> 1);//相当于int newCapacity = oldCapacity + (oldCapacity/2)
        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);
    }

在这里有个变量modCount，记录数组结构改变的次数，在增加，删除方法操作里都有，都会记录

 protected transient int modCount = 0;

在扩容判断这个阶段，先判断当前元素数量+1是否大于数组的长度，如果是就要扩容，扩容方法是grow()。从 int newCapacity = oldCapacity + (oldCapacity >> 1);可以看出扩容的大小是之前的1.5倍。使用Arrays.copyOf重新赋值到长度为newCapacity的 elementData数组。
add(int index, E element)
其中还有一个add(int index, E element)方法，这个add方法是将指定元素插入其中的指定位置，将当前位于该位置(如果有)的元素移动，并移动右边的任何后续元素(将一个元素添加到它们的索引中)。


  public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

先判断是否要扩容，然后用System.arraycopy的方法对elementData其重新赋值，它的意思是把从elementData的第index的元素向elementData的第index+1的元素开始赋值，也就是index后(包括index)的元素都向后移动一位了。
addAll(Collection c)
这个方法是用来向现有的ArrayList后面添加传入的ArrayList。


    public boolean addAll(Collection extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

主要是先获取传入进来ArrayList中的数组，然后获取它的长度，再对其扩容判断，再用 System.arraycopy把a数组向elementData数组后面进行赋值。

ArrayList的remove方法
remove(int index)


public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

这个也简单，就是保存要删除索引的元素的值，然后计算要移动的元素数量，就是index后面的元素都要向前移动一位。然后最后面的 elementData[—size] = null。

ArrayList的遍历
forEach
在JDK7之前，ArrayList的遍历主要用到是Iterable接口的Iterator iterator();而JDK8后Iterable接口也增加了forEach这个默认方法。


 default void forEach(Consumer super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

ArrayList重载了这个方法


@Override
public void forEach(Consumer super E> action) {
    Objects.requireNonNull(action);
    final int expectedModCount = modCount;
    @SuppressWarnings("unchecked")
    final E[] elementData = (E[]) this.elementData;
    final int size = this.size;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        action.accept(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

forEach这个默认方法，也是对这个列表进行for循环，然后调用Consumer这个接口的accept的方法，所以我们的逻辑可以写在Consumer接口的这个accept方法里，又因为Consumer接口只有一个抽象方法accept，所以我们可以用lombda表达式，如:


List list  =new ArrayList();
list.add(1);
list.add(2);
list.add(3);
list.forEach(System.out::print);

更多的lombda表达式使用方法可以看这篇文章:从Java匿名内部类深入到JDK8的Lombda表达式
当然也可以用匿名内部类


List list  =new ArrayList();
list.add(1);
list.add(2);
list.add(3);
list.forEach(new Consumer() {
    @Override
   public void accept(Object o) {
        System.out.print(o);
       }
});

其他方法

这些方法很简单，看源码就懂，其实最关键的方法就是


public static native void arraycopy(Object src,  int  srcPos, Object dest, int destPos,int length);
    public int size() {
         return size;
    }
    public boolean isEmpty() {
         return size == 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 {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
 public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

原创来源：滴一盘技术

上一篇：从Java匿名内部类深入到JDK8的Lombda表达式
下一篇：开发自己IoC容器

网站简介

第一盘搜索_让网盘资源搜索更简单
第一盘搜索，争做网盘搜索第一盘。专注于百度云网盘、微盘、阿里云盘、文库、在线视频网站的资源嗅探和搜索，让资源搜索查找变得更简单

友情链接

爱推站网站地图

从源码深入底层解析Java的数组列表ArrayList

网站简介

热门标签

最新评论

友情链接

从源码深入底层解析Java的数组列表ArrayList

网站简介

热门标签

置顶推荐

最新评论

友情链接