【Java】ArrayList实现原理浅析

为什么要写这篇文章，还真不是我好奇，就是因为团队技术分享了，我也要搞一个分享的内容，我满脸写着期待（绝望）和开心（难过）。

一.ArrayList的底层数据结构

ArrayList底层的数据结构是数组，它是一个Object元素类型的数组，所有操作操作底层都是基于数组的。（我甚至一度在想，我需不需要解释数组是个什么东西，春困使我放弃这个操作）

二.ArrayList的扩容机制

这个算是比较有讲头的一个东西了，我整个的技术分享就是用这个来保饭碗的。

2.1三种构造函数分析

要讲扩容机制，就要先说ArrayList的三种构造函数：

transient Object[] elementData;

复制代码

注：elementData是ArrayList的底层数据结构，是一个对象数组，存放实际元素，用transient标记，代表序列化时不会被序列化；

2.1.1 空参构造函数

给elementData设置一个空对象数组

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};


public ArrayList() {

        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

复制代码

2.1.2 指定数组容量大小参数的构造函数

指定容量>0，直接new一个指定大小的对象数组；
=0，指定一个空对象数组
<0，抛异常

private static final Object[] EMPTY_ELEMENTDATA = {};


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);

        }

}

复制代码

2.1.3 集合参数的构造函数

a.将集合转化成数组
b.判断数组的长度，length!=0；true，判断数组类型是否为Object类型数组？->否，拷贝elementData的数据，拷贝为Object数组，赋值给elementData
false:设置elementData为空对象数组

private static final Object[] 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;

        }

}

复制代码

2.1.4 什么是数组的深拷贝和浅拷贝？

深拷贝：不单单是引用拷贝，还开辟一块新的内存空间

浅拷贝： 引用拷贝

Q：这里的Arrays.copyOf深拷贝还是浅拷贝？
A：浅拷贝，只复制了对象的引用，即内存地址，并没有为每个元素新创建对象。
原因就不过多解释了，具体去查看这篇博客吧。blog.csdn.net/abysscarry/…

2.2.扩容机制发生的时间

add()的时候调用

1.add(E e) ；添加具体某个元素
代码操作释义：检测是否需要扩容操作；将集合中实际元素个数+1；

public boolean add(E e) {

        ensureCapacityInternal(size + 1);  // Increments modCount!!

        elementData[size++] = e;

        return true;

}

复制代码

2.add(int index, E element) ；根据下标去添加某个元素

public void add(int index, E element) {

        if (index > size || index < 0)

            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));


        ensureCapacityInternal(size + 1);  // Increments modCount!!

        //原数组；源数组要复制的起始位置；目标数组；目标数组复制的起始位置；要copy的数组的长度

        System.arraycopy(elementData, index, elementData, index + 1,

                         size - index);

        elementData[index] = element;

        size++;

}

复制代码

这里的System.arraycopy()是深拷贝还是浅拷贝？

答：只有数组为一维数组，并且元素为基本类型或String类型时，才是深复制，其它都属于浅复制；
System.arraycopy()常用作数组的扩容，如ArrayList底层数组的扩容

2.3插入数据时，ArrayList和LinkedList的区别

2.3.1 ArrayList如何插入数据？

曾几何时，你麻木的记住，ArrayList.add（index，e）效率<LinkedList的add，时至今日，打工人顿悟了。来，让我们一层一层的剥开他的衣服...呸，代码！
System.arraycopy(elementData, index, elementData, index + 1,size - index);你看看这句代码都干了些什么事儿。

为了在指定的下标插入一个数据，我们要把目标index的位置到size-index的数据全都进行复制，紧紧是为了给某个add的数据让位。

倘若数组长度是100，然后add(0,element)，也就意味，为了给他让位，我们需要拷贝移动1-99的数据位置。

2.3.2 LinkedList是如何插入数据？

public void add(int index, E element) {

        checkPositionIndex(index);

        if (index == size)

            linkLast(element);

        else

            linkBefore(element, node(index));

}


void linkBefore(E e, Node<E> succ) {

        // assert succ != null;

        final Node<E> pred = succ.prev;

        final Node<E> newNode = new Node<>(pred, e, succ);

        succ.prev = newNode;

        if (pred == null)

            first = newNode;

        else

            pred.next = newNode;

        size++;

        modCount++;

    }

复制代码

分析：linkBefore（element，node（index）），传入的参数是：1.目标元素；2.目标元素的当前节点对象。

LinkedList插入数据过程：

1. 
   
2. 获取当前的目标节点的pre=pred；
   
3. new一个新的结节点newNode，3个参数代表着:a.当前操作节点的pre=pred；b.元素e=e；c.下一个节点next=succ；
   
4. 把new的新节点，设置给当前操作节点的pre。（将操作节点的pre设置为新插入的元素节点）
   
5. 判断当前插入的元素位置是否为LinkedList的头节点；若不是的话，则将当前操作元素节点的next指为new的要插入进来的那个节点。（将操作节点的next指向新插入的元素的节点）
   

在某个位置插入某个元素的大概流程如图所示：

也就是说，我们通过LinkedList向某个位置插入一个数据，我们只需要改变两个数据节点的pre和next指向就完成了。

ArrayList和LinkedList的插入效率比较

ArrayList的add是尾部：效率ArrayList>LinkedList；
ArrayList的add是头部：效率ArrayList<LinkedList

原因：ArrayList的内存空间连续，且不需要复制数组。LinkedList需要创建一个新的节点，前后引用进行重新排列。

我不知道你们有没有恍然大悟，但是我恍然大悟了。

接下来就是揭开扩容的真面目了，扩容和构造器有什么关系？

2.4 触发扩容以及扩容大小

上面说扩容机制是在add(e)时触发的，来看看add(e)的源码：

add(E e)

public boolean add(E e) {

        ensureCapacityInternal(size + 1);  // Increments modCount!!

        elementData[size++] = e;

        return true;

}

复制代码

ensureCapacityInternal(int minCapacity) :确保插入元素容器最小的值；
minCapacity：当前数组的长度+1

构造函数为空参数构造函数，则给minCapacity设置默认的值为minCapacity=DEFAULT_CAPACITY=10；
若不为空参数构造函数，则minCapacity=数组已存在数据size+1

private static final int DEFAULT_CAPACITY = 10;

private void ensureCapacityInternal(int minCapacity) {

        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

        }

        ensureExplicitCapacity(minCapacity);

}

复制代码

ensureExplicitCapacity(int minCapacity) :判断是否需要扩容
elementData.length是现有数据的长度。

private void ensureExplicitCapacity(int minCapacity) {

        modCount++;


        // overflow-conscious code

        if (minCapacity - elementData.length > 0)

            grow(minCapacity);

}

复制代码

grow(int minCapacity) :实现扩容

1. 
   
2. 获取旧容量
   
3. 现将原元素数组的长度增大1.5倍，随后和newCapacity比较。
   
4. 新容量小于参数指定容量，修改新容量：newCapacity（新增容量）<minnewCapacity：newCapacity=minCapacity
   
5. 新容量大于最大容量：newCapacity>minnewCapacity：newCapacity:将就数组拷贝到扩容后的新数组中。
   

private void grow(int minCapacity) {

    int oldCapacity = elementData.length; //旧容量

    int newCapacity = oldCapacity + (oldCapacity >> 1); //新容量为旧容量的1.5倍

    if (newCapacity - minCapacity < 0) //新容量小于参数指定容量，修改新容量

        newCapacity = minCapacity;

    if (newCapacity - MAX_ARRAY_SIZE > 0) //新容量大于最大容量

        newCapacity = hugeCapacity(minCapacity); //指定新容量

    //拷贝扩容

    elementData = Arrays.copyOf(elementData, newCapacity);

}

复制代码

第一次调用添加元素的add和addAll，size=0，则minCapacity=1
如果ArrayList给了特定的初始值，则需要根据数组实际长度和数组容量差来判断是否调用扩容；如果没有指定初始容量，第一次调用add则一定需要调用grow()

三.ArrayList的线程安全性

在多线程下，ArrayList不能保证原子性(即同一时刻只能有一个线程来对它进行操作)。

举个栗子：线程A对ArrayList进行++处理，期待100；线程B对ArrayList进行--处理，期待98。多线程进行时，可能本应该为100，因为又有--操作，可能++后，结果仍然为99.

多线程环境下，ArrayList线程是不安全的。

保证线程安全性的方法：

1.使用synchronized关键字；

2.用Collection类中的静态方法synchronizedList()，对Arraylist进行调用

四.ArrayList常用方法介绍

arrayList.get(position)：根据数组下标进行取值,set同理

arrayList.add(postion)：判断是否扩容，根据数组下标进行赋值

arrayList.remove(index)步骤：
1.在目标元素的位置设置赋值的起始位置；
2.将目标位置开始到数组最后一位的数组进行复制；
3.然后覆盖拷贝到要移除的位置上，将要移除的位置进行覆盖；
4.再将最后一个位置的数据进行null设置，等待回收。

remove(index)源码：

public E remove(int index) {

        //第一步先判断是否有越界，如果越界直接IndexOutOfBoundsException

        rangeCheck(index);

        modCount++;

        //把该元素从数组中提出

        E oldValue = elementData(index);

        //需要复制的长度

        int numMoved = size - index - 1;

        if (numMoved > 0)

        //原数组，从哪开始复制，目标数组，复制起始位置，长度。过程如下图：

            System.arraycopy(elementData, index+1, elementData, index,numMoved);

        //赋值null等待回收

        elementData[--size] = null; 

        return oldValue;

    }

复制代码

五.ArrayList的去重处理

1.循环list中所有的元素然后删除

    public static ArrayList removeDuplicate_1(ArrayList list){

        for(int i =0;i<list.size()-1;i++){

            for(int j=list.size()-1;j>i;j--){

                if(list.get(i).equals(list.get(j)))

                    list.remove(j);

            }

        }


        return list;        

    }

复制代码

2.利用hashSet剔除重复元素,无序

public static ArrayList removeDuplicate_2(ArrayList list){

        HashSet set = new HashSet(list);

        //使用LinkedHashSet可以保证输入的顺序

        //LinkedHashSet<String> set2 = new LinkedHashSet<String>(list); 

        list.clear();        

        list.addAll(set);

        return list;        

    }

复制代码

3.利用list的contains方法去重

public static ArrayList removeDuplicate_3(ArrayList list){

        ArrayList tempList = new ArrayList(list.size());

        for(int i=0;i<list.size();i++){

            if(!tempList.contains(list.get(i)))

                tempList.add(list.get(i));

        }

        return tempList;        

    }

复制代码

contains是根据什么原理来进行比较的呢？
可以看出contains其实也是用equals来比较的，而equals是比较的地址

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;

    }

复制代码

六.什么时候选择ArrayList？

6.1 ArrayList的for和Iterator遍历效率差别

ArrayList实现了RandomAccess接口，这个接口是个标志接口，可以随机访问，使得ArrayList的for循环遍历的效率高于Iterator遍历；而LinkedList则是Iterator遍历效率更高。

for()和Iterator的抉择？

for循环遍历，基于计数器的：
顺序存储：读取性能比较高。适用于遍历顺序存储集合。
链式存储：时间复杂度太大，不适用于遍历链式存储的集合。

迭代器遍历，Iterator：
顺序存储：如果不是太在意时间，推荐选择此方式，毕竟代码更加简洁，也防止了Off-By-One的问题。
链式存储：平均时间复杂度降为O(n)，推荐此遍历方式。

6.1.2 for和Iterator()的remove()不同之处

对ArrayList遍历：

1.迭代器进行遍历的时候不可以对迭代的对象，所以不能在使用Iterator遍历的同时list一处这个元素，但是可以使用iterator的remove()；

2.而for循环是不可以在for循环的时候调用list的remove()方法，会报错。

6.3 集合里各位实现类的优缺点比较

对于数据的操作，一般是增删改查，排序，数据重复，是否可存空，线程安全性来看的。
将根据以上操作对相应的集合进行优缺点的比较整理。如下：

List：有序，元素可重复

实现类：
线程安全：Vector，
线程不安全：ArrayList，LinkedList
插入和删除效率高：LinkedList
查询速度高：ArrayList

Set：元素不能重复

查询速度：LinkedHashSet=HashSet
查询，查找速度：HashSet>TreeSet
查询，删除，增加元素的效率都很高

Map

线程安全：HashTable，key和value都不能为空
线程不安全：HashMap，key和value都能为空
迭代访问速度快：LinkedHashMap，迭代遍历时，取出的键值对的顺序是其插入顺序；遍历速度<HashMap