最常用聚集 - arraylist详解

ArrayList先容

ArrayList实现了List接口，是次序容器，即元素存放的数据与放进去的次序雷同，允许放入null元素，底层通过数组实现。除该类未实现同步外，其余跟Vector大抵雷同。每个ArrayList都有一个容量(capacity)，表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，假如容量不敷，容器会主动增大底层数组的大小。

ArrayList 在JDK1.8 前后的实现区别：

• JDK1.7：像饿汉式，直接创建一个初始容量为10的数组
  
• JDK1.8：像懒汉式，一开始创建一个长度为0的数组，当添加add第一个元素时再创建一个初始容量为10的数组
  

size(), isEmpty(), get(), set()方法均能在常数时间内完成，add()方法的时间开销跟插入位置有关，addAll()方法的时间开销跟添加元素的个数成正比。其余方法多数是线性时间。
为追求服从，ArrayList没有实现同步(synchronized)，假如需要多个线程并发访问，用户可以手动同步，也可使用Vector替代
底层原理先容

底层数据结构

1. //集合默认容量10；
2. private static final int DEFAULT_CAPACITY = 10;
4. //空数组
5. private static final Object[] EMPTY_ELEMENTDATA = {};
7. //默认容量的空的数组
8. private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
10. // 集合中真实存储数据的数组
11. transient Object[] elementData; // non-private to simplify nested class access
13. //集合中元素的个数，注意，这里不是数组的长度
14. private int size;

复制代码

构造方法

1. public ArrayList() {
2.     //将属性中默认的空的数组赋值给了 存储数据的变量
3.     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
4.    
5.     //等价于this.elementData = {}
6. }
8. //有参构造
9. public ArrayList(int initialCapacity) {
10.     //给定初始容量，就创建一个这个容量大小的数组
11.    if (initialCapacity > 0) {
12.         this.elementData = new Object[initialCapacity];
13.    } else if (initialCapacity == 0) {
14.         //如果传递的是0 就将{}赋值给elementData
15.         this.elementData = EMPTY_ELEMENTDATA;
16.         //等价于this.elementData = {}
17.    } else {
18.         //如果传递的是负数，就会抛异常
19.         //java.lang.IllegalArgumentException: Illegal Capacity: -20
20.         throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
21.    }
22. }

复制代码

主动扩容

每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，假如超出，数组将会进行扩容，以满足添加数据的需求。

1. private void grow(int minCapacity) {
2.     // overflow-conscious code
3.     int oldCapacity = elementData.length;
4.    
5.     //动态扩容，扩容为原来的1.5倍，右移一位即原来的一半
6.     int newCapacity = oldCapacity + (oldCapacity >> 1);
7.     if (newCapacity - minCapacity < 0)
8.         newCapacity = minCapacity;
9.         
10.     //判断新容量是否会超过最大限制
11.     if (newCapacity - MAX_ARRAY_SIZE > 0)
12.         newCapacity = hugeCapacity(minCapacity);
13.     // minCapacity is usually close to size, so this is a win:   
14.     elementData = Arrays.copyOf(elementData, newCapacity);//数组的复制操作
15. }

复制代码

扩容方法流程：

• 起首获取数组长度
  
• 将数组新容量扩容为原数组容量的1.5倍取整
  
• 将新容量和当前所需最小容量做对比，(最小容量是在add方法中得到的，minCapacity=size+1，即原数组中元素数量加1)，而newCapacity=elementData.length*1.5，一般来说肯定是1.5倍比+1的大。但是这里要思量当数组为空时的情况。数组为空又分为两种情况：①指定了数组容量为0 ②没有显式指定命组大小。
  
  
  
  • 当数组为空时进行插入操作，因为元素个数size为0，数组容量也为0，那么就会进行扩容操作，对于空数组，扩容1.5倍后你的容量还是为0，那么此时就会小于我所需的最小容量（也就是1）,此时会令 newCapacity = minCapacity;
    
  • 而对于①，传入到grow方法的minCapacity = 1 ，因此它扩容后的容量就是1
    
  • 对于②，在ensureCapacityInternal方法中，使minCapacity = DEFAULT_CAPACITY（10），因此扩容后的数组长度就是DEFAULT_CAPACITY，也就是10。
    
    
    
    • 缘故原由在于在有参构造方法中使this.elementData = EMPTY_ELEMENTDATA;（无参构造方法中this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;），此时在ensureCapacityInternal方法中会对this.elementData进行判断，因此对于①，传入到grow方法的minCapacity = 1；而对于②，minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity)，即minCapacity = 10
      
    
    
  
  

1. if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
2.     //比较大小，此时 minCapacity = 10
3.     minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
4. }

复制代码

• 最后判断新容量大小是否大于默认数组的最大值（Integer.MAX_VALUE-8），则赋予它整型的最大值
  
• 扩容之后，会调用Arrays.copyOf()方法对数组进行拷贝。
  

实际上，对数组的copy需要创建一个新数组，并对原数组进行复制的操作，这会造成资源消耗。因此在添加大量元素前，建议使用ensureCapacity操作先增加 ArrayList 实例的容量，先进行稍少量数组数据的copy，再添加元素

add(), addAll()

add 操作可能会导致capacity不敷，因此在添加元素之前，都需要进行剩余空间检查，假如需要则主动扩容。扩容操作终极是通过grow()方法完成的。
假设使用的是空参构造，第一次添加元素 add(1)

1. public boolean add(E e) {
2.     //确保内部容量 0 + 1
3.     ensureCapacityInternal(size + 1);  // Increments modCount!!
4.     //将要添加的元素添加到数组有数据的下一个位置
5.     elementData[size++] = e;
6.     return true;
7. }
9. private void ensureCapacityInternal(int minCapacity) {//第一次添加： minCapacity = 1
10.     //有参构造的情况：new Object[10] != {}，不会执行if内的语句。即使有参构造给的是0，也不会执行，因为此时elementData = EMPTY_ELEMENTDATA，不等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA
11.     // 无参构造的情况下：{} = {} 会执行Math.max语句
12.     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
13.     //比较大小，此时 minCapacity = 10
14.         minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
15.     }
16.     //明确数组的容量
17.     ensureExplicitCapacity(minCapacity);
18. }
20. private void ensureExplicitCapacity(int minCapacity) {
21.     modCount++;//记录当前集合操作的次数
22.     // overflow-conscious code
23.     if (minCapacity - elementData.length > 0)
24.         grow(minCapacity);//扩容操作
25. }

复制代码

addAll()方法能够一次添加多个元素，根据位置不同也有两个版本，
<ul>
在末尾添加的addAll(Collection