java集合系列(一）——ArrayList

2019-01-21 本文已影响0人 Kino_7abb

今天看了下ArrayList作为自己读源码的第一步。ArrayList从名字可以知道底层是由数组实现的。而作为Collection的大家庭一员，可以说是很基础的集合了。

1.什么是ArrayList

ArrayList 底层是一个动态数组，大小是可变的。它实现了List接口，允许null添加进来。有以下几点注意：

每个ArrayList实例都会有一个容量capacity用来存储元素数组的大小。默认是10
同时会有一个size属性，来记录当前ArrayList中的个数。
随着元素增加，容量也不断增长，需要检查是否需要，当size == capacity 就需要扩容啦
扩容操作就是将原来数组中的内容进行拷贝。
所以我们知道具体数量的话，应赋给一个默认值，减少拷贝的，因为拷贝是需要消耗资源的

2.我们来看看ArrayList的源码

2.1.底层使用数组

 private transient Object[] elementData;

由此可以看出底层是一个数组 transient 关键字：

当对象存储时，它的值不需要维持。Java的serialization提供了一种持久化对象实例的机制。当持久化对象时，可能有一个特殊的对象数据成员，我们不想用serialization机制来保存它。为了在一个特定对象的一个域上关闭serialization，可以在这个域前加上关键字transient。当一个对象被序列化的时候，transient型变量的值不包括在序列化的表示中，然而非transient型的变量是被包括进去的。(可以参考)

2.2构造

    /**
     * 构造一个具有指定初始容量的空列表。
     */
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        this.elementData = new Object[initialCapacity];
    }
 /**
     * 构造一个初始容量为 10 的空列表
     */
    public ArrayList() {
        this(10);
    }

构造基本上是对ArrayList进行初始化操作，默认是10

2.3新增 add操作

 public boolean add(E e) {
    //检测扩容
    ensureCapacity(size + 1);  
    elementData[size++] = e;
    return true;
 }

新增元素也就是在数组的末尾新增元素。这里ensureCapacity()方法是对ArrayList集合进行扩容操作

public void add(int index, E element) {
        //判断索引位置是否正确
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(
            "Index: "+index+", Size: "+size);
        //扩容检测
        ensureCapacity(size+1);  
        /*
         * 对源数组进行复制处理（位移），从index + 1开始，长度为size - index
         * 主要目的就是空出index位置供数据插入，
         * 即向右移动当前位于该位置的元素以及所有后续元素。
         */
        System.arraycopy(elementData, index, elementData, index + 1,
                 size - index);
        //在指定位置赋值
        elementData[index] = element;
        size++;
 }

add方法本质上是，arraycopy()这个复制数组的方法。

这是非常麻烦和耗时的，

所以如果指定的数据集合需要进行大量插入（中间插入）操作，推荐使用LinkedList。

2.4删除操作

remove(int index)

public E remove(int index) {
        //位置验证
        RangeCheck(index);

        modCount++;
        //需要删除的元素
        E oldValue = (E) elementData[index];   
        //向左移的位数
        int numMoved = size - index - 1;
        //若需要移动，则想左移动numMoved位
        if (numMoved > 0)
            System.arraycopy(elementData, index + 1, elementData, index,
                    numMoved);
        //置空最后一个元素
        elementData[--size] = null; // Let gc do its work

        return oldValue;
    }

由源码可以知道删除的操作本质上还是index+1开始长度为 size - index -1 到，然后复制到新的数组里，然后最后一个元素置空，由GC处理掉

remove(Object o)移除此列表中首次出现的指定元素（如果存在）。

public boolean remove(Object o) {
        //因为ArrayList中允许存在null，所以需要进行null判断
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    //移除这个位置的元素
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

ArrayList是可以存null，因此需要null判断，其余的只要用equals进行匹配即可其中

其中fastRemove()方法用于移除指定位置的元素。如下：

private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // Let gc do its work
    }

modCount 表示的是修改次数，根据线程不安全的话可以判断其他线程是否修改了该集合的元素，如果modCount和存储的mcount不一样那就抛异常。因此推荐迭代器遍历

2.5查找

public E get(int index) {
        RangeCheck(index);
        return (E) elementData[index];
    }
}

由此可以看出来ArrayList 查找元素是很快的，只需要把索引赋值进去就可以啦，时间复杂度为O（1）

2.6关键的地方：扩容

在上面的新增方法的源码中我们发现每个方法中都存在这个方法：ensureCapacity()，

若新增元素后元素的个数会超过ArrayList的容量，就会进行扩容操作来满足新增元素的需求。

所以当我们清楚知道业务数据量或者需要插入大量元素前，我可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。

public void ensureCapacity(int minCapacity) {
        //修改计时器
        modCount++;
        //ArrayList容量大小
        int oldCapacity = elementData.length;
        /*
         * 若当前需要的长度大于当前数组的长度时，进行扩容操作
         */
        if (minCapacity > oldCapacity) {
            Object oldData[] = elementData;
            //计算新的容量大小，为当前容量的1.5倍
            int newCapacity = (oldCapacity * 3) / 2 + 1;
            if (newCapacity < minCapacity)
                newCapacity = minCapacity;
            //数组拷贝，生成新的数组
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }
}

1.5倍考虑到资源的分配不会浪费很多资源也不会，也能够满足性能的需求

java集合系列(一）——ArrayList

1.什么是ArrayList

2.我们来看看ArrayList的源码

2.1.底层使用数组

2.2构造

2.3新增 add操作

2.4删除操作

2.5查找

2.6关键的地方：扩容

猜你喜欢

热点阅读