Java8的集合1：ArrayList的实现原理

1、ArrayList概述

　　ArrayList是一个动态数组，实现了List接口以及list相关的所有方法，它允许所有元素的插入，包括null。另外，ArrayList和Vector除了线程不同步之外，大致相等，此实现不同步。

2、属性

//默认容量的大小
private static final int DEFAULT_CAPACITY = 10;

//空数组常量
private static final Object[] EMPTY_ELEMENTDATA = {};

//默认的空数组常量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存放元素的数组，从这可以发现ArrayList的底层实现就是一个Object数组
transientObject[] elementData;

//数组中包含的元素个数
private int size;

//数组的最大上限
private static final intMAX_ARRAY_SIZE = Integer.MAX_VALUE -8;

3、构造方法：

　　ArrayList()构造一个初始容量为0的空列表。

　　ArrayList(Collection<? extends E> c)构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。

　　ArrayList(int initialCapacity)构造具有指定初始容量的空列表

4、方法

　add(E e)：

　　ArrayList的扩容机制就在这里体现。在插入元素之前，它会先检查是否需要扩容，然后再把元素添加到数组中最后一个元素的后面。在ensureCapacityInternal方法中，我们可以看见，如果当elementData为空数组时，它会使用默认的大小去扩容。所以说，通过无参构造方法来创建ArrayList时，它的大小其实是为0的，只有在使用到的时候，才会通过grow方法去创建一个大小为10的数组。时间复杂度度为O(1)。

set(int index,E element)

　　set方法的作用是把下标为index的元素替换成element，跟get非常类似，时间复杂度度为O(1)。

remove(int index)

　 remove方法与add带指定下标的方法非常类似，也是调用系统的arraycopy方法来移动元素，时间复杂度为O(n)。

grow(int minCapacity)

　　grow方法是在数组进行扩容的时候用到的，ArrayList每次扩容都是扩1.5倍，然后调用Arrays类的copyOf方法，把元素重新拷贝到一个新的数组中去。

size()

　　size方法非常简单，它是直接返回size的值，也就是返回数组中元素的个数，时间复杂度为O(1)。这里要注意一下，返回的并不是数组的实际大小。

indexOf(Object o)和lastIndexOf(Object o)

　　indexOf方法的作用是返回第一个等于给定元素的值的下标。它是通过遍历比较数组中每个元素的值来查找的，所以它的时间复杂度是O(n)。lastIndexOf的原理跟indexOf一样，而它仅仅是从后往前找起罢了

Vector

　　Vector很多方法都跟ArrayList一样，只是多加了个synchronized来保证线程安全。Vector与ArrayList的不同点:

　　Vector比ArrayList多了一个属性：

protected int capacityIncrement;

　　这个属性是在扩容的时候用到的，它表示每次扩容只扩capacityIncrement个空间就足够了。该属性可以通过构造方法给它赋值。先来看一下构造方法：

　　从构造方法中，我们可以看出Vector的默认大小也是10，而且它在初始化的时候就已经创建了数组了，这点跟ArrayList不一样。

再来看一下grow方法：

　　从grow方法中我们可以发现，newCapacity默认情况下是两倍的oldCapacity，而当指定了capacityIncrement的值之后，newCapacity变成了oldCapacity+capacityIncrement。

还有些方法放在最后的代码里面来体现。

5、总结

　　1、ArrayList创建时的大小为0；当加入第一个元素时，进行第一次扩容时，默认容量大小为10。

　　2、ArrayList每次扩容都以当前数组大小的1.5倍去扩容。

　　3、Vector创建时的默认大小为10。

　　4、Vector每次扩容都以当前数组大小的2倍去扩容。当指定了capacityIncrement之后，每次扩容仅在原先基础上增加capacityIncrement个单位空间。5、ArrayList和Vector的add、get、size方法的复杂度都为O(1)，remove方法的复杂度为O(n)。6、ArrayList是非线程安全的，Vector是线程安全的。

package util;

import java.util.ArrayList;
import java.util.Arrays;

public class ArrayListMethod {

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        
        //add(E e) add(int index, E e)
        list.add(1);
        list.add(2);
        list.add(0,0);//下标为0的数值设置为0；
        list.add(0);
        System.out.println("添加数据是否成功\t"+list.add(3));//添加数据成功返回true
        
        //set(int index,E element)
        int oldValue = list.set(1,8);//将下标为1的数据改为8，并返回修改前的数据的值
        System.out.println("修改下标为1的值为8之后原来的数据：\t"+oldValue);
        
        System.out.println("打印:\t"+list);
        
        //remove(int index)
        //删除下标为2的数据，并返回删除的数据的值
        int removeData = list.remove(2);
        System.out.println("删除的数据是:\t"+removeData);
        
        System.out.println("打印:\t"+list);
        
        //size(),isEmpty(),contains()
        System.out.println("大小:\t"+list.size());
        System.out.println("是否为空:\t"+list.isEmpty());
        System.out.println("包含数据2吗:\t"+list.contains(2));//包含数据2吗
        
        //indexOf(Object o),lastIndex(Object o)
        System.out.println("数据8的下标:\t"+list.indexOf(8));//寻找8的下标
        System.out.println("数据0的最后一位的下标:\t"+list.lastIndexOf(0));
        System.out.println("数据0的第一位下标:\t"+list.indexOf(0));
        System.out.println("下标为1的数据是:\t"+list.get(1));//寻找下标为1的数
    
        //clone()
        Object listClone = list.clone();//克隆
        System.out.println("克隆的数据:\t"+listClone);
        
        //toArray()
        //转换为Object类型数组
       Object listArray[] = list.toArray();
       System.out.print("打印转化为Object类型的数组:\t");
        for(Object l:listArray) {
            System.out.print(l+" ");
            
        }
        System.out.println();
        
        //转换为Integer类型的数组
        //Integer[] a = new Integer[list.size()];
           Integer[] list1 = list.toArray(new Integer[list.size()]);//转换为数组
           System.out.print("打印转化为Integer类型的数组:\t");
           for(int l:list1) {
                System.out.print(l+" ");
            }
           System.out.println();
           
           //addAll()
           //添加一个集合
//        boolean flag = list.addAll(list);
//        System.out.println(flag);
//        System.out.println(list);
//        
//        //指定位置加入一个集合
//        boolean flag1 = list.addAll(1, list);
//        System.out.println(flag1);
//        System.out.println(list);
        
           //clear(),removeAll()
            list.clear();
            list.removeAll(list);
          System.out.println("清空\t"+list);
           
           
    }
    

}

运行结果

Java8的集合1：ArrayList的实现原理

推荐阅读