Java – 集合ArrayList

为什么有集合

集合跟数组一样，也可以存储成员数据，但是数组一旦生成，就不能更改，而集合是可变的数组，跟据数量自动扩容，删除后就会自动删除容量。

集合存储特点

集合不能存储基础数据类型，如果要存储基础数据类型，则需要把数据转为包装类类型。

ArrayList

创建实例

JDK7 以前的写法
ArrayList<String> list = new ArrayList<String>()

JDK7 以后的写法，可以省略后面的泛型定义
ArrayList<String> list = new ArrayList<>()

创建自定义类
ArrayList<Person> list = new ArrayList<>()

成员方法

ArrayList<String> list = new ArrayList<>()
list.add("aaa");  // => add 永远都能加进去，所以永远都为 true

list.remove("aaa");  // 删除元素
list.remove(0);  // 删除第一个元素,返回被删除的元素

list.set(0,"bbb"); // 修改第一个元素为“bbb”

list.get(0); // 获取第一个元素数据

存储基础类型

集合本身是不支持存储基础数据类型的，但是可以把基础数据类型包装成包装类数据。

包装类分别如下

byte  =>  Byte
short  =>  Short
char  =>  Character
int  =>  Integer
long  =>  Long
float  =>  Float
double  =>  Double
boolean  =>  Boolean

定义

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
// 在JDK5以后，int Integer 之间是可以互相转化的，cahr类推，所以可以直接add()

底层原理

1.利用空参创建的集合，在底层创建一个默认长度为0的数组

2.添加第一个元素时，底层会创建一个新的长度为10的数组

3.存满时，会扩容1.5倍

4.如果一次添加多个元素，1.5倍还放不下，则新创建数组的长度以实际为准

源码解析

DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是一个空的 Object[] 数组

elementData 是 ArrayList 保存数据的数组

// ArrayList 空参构造
public ArrayList() {
 // 先让 elementData 为空数组
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

总结：在最初没有赋成员时，ArrayList 集合为空。

size 是 ArrayList 私有的成员，用于记录现时数组成员个数，同时也能表示接下来保存数据在数组中的索引位置

// 当ArrayList被 add 成员时
public boolean add(E e) {
    modCount++;
    // 会调用私有的 add 方法，分别传入 成员数据，保存的私有数组，和记录的数组位置
    add(e, elementData, size);
    return true;
}

接下来我们来看看私有 add方法

// 私有 add方法
private void add(E e, Object[] elementData, int s) {
  // 判断 当前的 size 是否和 elementData 是否一样
  if (s == elementData.length)
      // 如果一样，说明 elementData 已经装满，需要扩容
      elementData = grow();
  elementData[s] = e;
  size = s + 1;
}

私有add方法会对当前的 elementData 数组判断，是否和现时的size位置相同，如果一样了，elementData 的容量已经用完，需要扩容

调用 grow() 会执行另一个私有的 grow() 方法，并且把现有的容量+1

private Object[] grow() {
  // 传入现在容量+1
  return grow(size + 1);
}

传入现有容量+1是指，目前至少需要的容量至少为 size + 1个

接下来调用 私有的 grow() 方法

private Object[] grow(int minCapacity) {
    // 保存 旧的 size 大小
    int oldCapacity = elementData.length;
    // 如果 旧的 size 大小大于0,且 elementData 不为空
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
      // 调用一个扩容函数，传入旧容量大小，至少要扩容多少个容量大小，旧容量大少右移1(即旧容量大小 / 2 的数量)
      int newCapacity = ArraysSupport.newLength(oldCapacity,
          minCapacity - oldCapacity, /* minimum growth */
          oldCapacity >> 1      /* preferred growth */);
       // 再把旧数据用 copyOf 进行复制到新的数组中，并保逐步
      return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {

      // 如果 旧的 size 大小小于0,且 elementData 为空
      // 则新建一个新的数组，当添加数少于10时，DEFAULT_CAPACITY 为 10,minCapacity为1,取最大值10
      // 如果 添加数不止10时，minCapacity 为添加数，则创建一个成员数为 minCapacity 的数组
      return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
  }

总结：grow() 方法会先检查你是add 一个，还是add 多个，

1.如果add一个，发现现时elementData为空，则会创建一个数量为 DEFAULT_CAPACITY =10 的数组

2.如果add一个，发现现时elementData不为空，且已装满，则会创建一个数量为 1.5倍 elementData.length 的新数组，并把旧数据传给新数组返回

3.如果add多个且大于10时，发现现时elementData为空，则会创建一个数量为实际大小的数组

4.如果add多个且大于10时，发现现时elementData不为空，且已装满，则会取实际长度的大小创建一个新的数组，并返回

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
    // 如果1.5倍扩容够存，则取1.5倍扩容，如果不够，那就以实际大小为准
    int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
    if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
      return prefLength;
    } else {
      // put code cold in a separate method
      return hugeLength(oldLength, minGrowth);
    }
  }