关于java:集合数组

ArrayList是数组的代表

概念

数组就是一块间断的内存空间

内存中申请一块内存空间。申请的这个空间是间断的。

特色

就是间断的，而且是固定大小的，并且外面寄存的值是同一个类型的，这就是数组汇合的特色。

内存空间间断
内存空间大小固定
寄存内容为同一类型
- ArrayList
  - <>申明的类型是什么就寄存什么类型
  - 没有<>申明，默认寄存的是Object类型

一维数组

申明

Java中能够应用2种形式来申明数组
- dataType[] arrayRefVar
  - 类型[] 变量名
- dataTypa arrayRefVar[]
  - 类型变量名[]
- []是数组的特有特色
创立
Java中数组的创立形式同样有2种
- arrayRefVar = new dataType[arraySize]
  - 显示的通知程序，向JVM内存中申请了arraySize长度的间断的内存空间
  - 数组具体是多大，由dataType的类型来决定的
- dataType[] arrayRefVar = {value0, value1, value2,...,valuek}
  - 隐式的去创立，大括号外面有多少个元素，对应的长度就是多少

数组阐明

Java语言中提供的数组是用来存储固定大小的同类型元素

开始下标

数组下标从 0 开始
长度
数组长度为申明的arraySize
最初下标
数组最初的元素下标为数组长度 -1
- arraySize-1

获取元素

数组外面的下标叫索引
获取下标元素
获取数组下标为n的值，表达式就是arrayRefVar[n]
- 获取下标为3的值，arrayRefVar[3]

获取第几个元素

获取数组第m个的值，表达式就是arrayRefVar[m-1]
- 获取数组内第4个值，表达式就是arrayRefVar[3]

List数组

就是ArrayList
容许有反复的元素并且有先后放入秩序
ArrayList类的底层是采纳动静数组进行数据管理的，反对下标拜访，增删元素不不便。

1. 动静数组扩容2. 下标间接拜访3. 增删不不便

申明

ArrayList构造方法有2个：

一个是带参，申明时指定对应内存空间大小；
一个是无参，申明时还没有指定内存空间大小，在第一次增加元素的时候，会指定内存空间大小，默认大小为10。

指明长度

List arrList = new ArrayList(4);

对应有参构造方法源码：

public class ArrayList<E> extends AbstractList<E>        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{    //03、空集合创立    private static final Object[] EMPTY_ELEMENTDATA = {};     //初始化创立list    public ArrayList(int initialCapacity) {        if (initialCapacity > 0) {            //01、element初始化创立长度为initialCapacity的一个object类型的数组            this.elementData = new Object[initialCapacity];        } else if (initialCapacity  0) {            //02、如果长度是0 就创立默认的空集合            this.elementData = EMPTY_ELEMENTDATA;        } else {            //04、否则的话就抛异样            throw new IllegalArgumentException("Illegal Capacity: "+                    initialCapacity);        }    }    //Collection是参数;List接口和HashSet接口通通属于Collection，Map不属于Collection接口    //HashSet接口传入也能够转为ArrayList    public ArrayList(Collection<? extends E> c) {        //        Object[] a = c.toArray();        if ((size = a.length) != 0) {            if (c.getClass()  ArrayList.class) {                elementData = a;            } else {                elementData = Arrays.copyOf(a, size, Object[].class);            }        } else {            // replace with empty array.            elementData = EMPTY_ELEMENTDATA;        }    }}

申明的int大小，就是在内存中占用的空间大小

未知长度

//多态申明List arrList = new ArrayList();

对应无参构造方法源码：

public class ArrayList<E> extends AbstractList<E>        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{    //ArrayList 的大小，就是蕴含的元素数量    private int size;        //2、默认实现：就是object的一个数组  Object的一维空数组    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};    //数组缓冲区，Object[]数组类型的一个缓冲区    //验证了对应的 ArrayList 底层是一个数组类型的缓冲区    //3、把这object数组赋值给整个的成员变量    //transient 序列化「不是程序内序列化的概念」，实现：当初运行一个在jvm内存中运行，当初想把在jvm内运行的放在磁盘上，下次间接应用这个去弄    transient Object[] elementData;    public ArrayList() {        //1、汇合底层的数组给它一个默认的实现        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;    }    }

无参申明的状况下，只是在堆外面申明了一个地址及名称，没有真正的在栈外面申请内存空间的大小
只是申明了一个空数组，对应size值为0
为何2个构造方法？

场景：
想要存入的数组大小已知为7，

有参

已知数组长度，申明list的时候就申明大小
- 这样内存空间不会有节约

比方想要数组大小是7，曾经晓得数组长度，
如果申明list的时候不申明大小，
那么默认在内存中list占用的空间是10个的大小空间，
这样对应有3个大小的空间其实是被节约掉的，
所以这个时候咱们就要用int参数的去申明。
如果想要存入的数据长度大小是30的list数组，
不申明大小，那第一次10，第二次15，第三次22，第四次33，同样外面会有3个大小是被节约的

无参

无参申明数组时不会占用内存空间
在第一次增加元素时，申明内存空间占用10个

总结

数组自定义时，要思考以下几个因素：
- 数组名「name」
- 数组容量「capacity」
- 数组长度「size」
arrayList底层是一个数组
- 有2个成员变量组成，一个是[]，一个是size
arrayList数组的初始容量是10
如果数组不够用，会进行扩容，会1.5大小的进行扩容
构造函数在1.8版本有bug，在1.9版本解决掉了
size作用
- 第一个作用就是指明数组以后有多少个元素，初始化没有给值的时候size指向的是0，阐明是0个
- 第二个作用，咱们向数组中增加元素的时候，对应增加元素的下标地位是什么，能够用size示意

size初始值是0，对应默认的数组创立后要增加元素时，第一个size指针的地位也是0

面试题一

6260652

public class ArrayList<E> extends AbstractList<E>        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{    //空集合创立    private static final Object[] EMPTY_ELEMENTDATA = {};        //把这object数组赋值给整个的成员变量    //transient 序列化「不是程序内序列化的概念」，实现：当初运行一个在jvm内存中运行，当初想把在jvm内运行的放在磁盘上，下次间接应用这个去弄    transient Object[] elementData;    //Collection是参数;List接口和HashSet接口通通属于Collection，Map不属于Collection接口    //HashSet接口传入也能够转为ArrayList    public ArrayList(Collection<? extends E> c) {        //        Object[] a = c.toArray();        if ((size = a.length) != 0) {            if (c.getClass()  ArrayList.class) {                elementData = a;            } else {                elementData = Arrays.copyOf(a, size, Object[].class);            }        } else {            // replace with empty array.            elementData = EMPTY_ELEMENTDATA;        }    }}

public class ArrayListDemo {    public static void main(String[] args) {        //Integer数组申明，隐士初始化        Integer[] array = {1,2};        //Integer数组转换为List        List<Integer> integerList = Arrays.asList(array);        //Object[] toArray();        Object[] objectArray = integerList.toArray();        System.out.println(objectArray.getClass()  Object[].class);        //jdk8:false 有bug，不会去返回导致的，所以用jdk11已解决        // jdk11:true        //Object[] toArray();        List<Integer> list = new ArrayList<>();        System.out.println(list.toArray().getClass()  Object[].class);//true    }}

增加元素

向数组内程序增加元素，复杂度是O(1)级别的，指向这个地位，间接增加就能够
数组往指定地位上增加的时候，工夫复杂度O(n)，数组的特点就是增加比拟耗时
间接数组开端追加
add(E e)
add()
- e：要增加的元素对象，比方66
modCount++
- modCount：列表在结构上被批改的次数
- 数组内增加元素，会扭转原有数组
add(e, elementData, size);
- 增加元素之前看下数组的内存空间是否还有中央
  - elementData：初始化时申明的数组
  - s：size，初始化的值为0
  - elementData = grow()：进行扩容

间接增加元素

如果数组的内存空间有空余，则间接数组元素数量「size」加 1，数组长度「elementData.length」不变
- elementData[s] = e;
  - s就是数组元素数量size
  - e要增加的元素，不须要扩容，间接赋值
- size = s + 1;
  - 数组元素数量多1️

数组长度为3，第2次增加元素 object，在add之前，size=1，add增加间接 elementData[1] = object; size=2

public class ArrayList<E> extends AbstractList<E>        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {    //列表在结构上被批改的次数    protected transient int modCount = 0;    //ArrayList 蕴含的元素数量 严格来说不是长度大小    private int size;    public boolean add(E e) {        //增加会批改数组        modCount++;        //01、首先确保有容量        add(e, elementData, size);        return true;    }    private void add(E e, Object[] elementData, int s) {        //ArrayList 的大小  初始化以后数组的长度        if (s  elementData.length)            //扩容操作            elementData = grow();        elementData[s] = e;        size = s + 1;    }}

指定地位增加

add(int index, E element)

想要在一个曾经创立好的数组内插入元素，首先咱们须要把对应插入元素的下标的内容空进去，须要进行一个元素转移，把88而后放进去，而后size指针指到下一个要增加元素的地位，并且阐明以后元素大小是多少，对应动态图如下：

rangeCheckForAdd(index);
- 先查看传入的数组下标是否有越界
- 超出则抛异样：IndexOutOfBoundsException{数组越界异样}
modCount++
- modCount：列表在结构上被批改的次数
- 数组内增加元素，会扭转原有数组
如果数组的内存空间有空余
arraycopy
- 数组要插入元素后的元素通过copy来进行向后挪动，要插入元素的地位空进去
elementData[index] = element;
- 间接赋值要插入的元素到以后地位
间接数组元素数量「size」加 1，数组长度「elementData.length」不变

public void add(int index, E element) {    rangeCheckForAdd(index);    modCount++;    final int s;    Object[] elementData;    if ((s = size)  (elementData = this.elementData).length)        elementData = grow();    System.arraycopy(elementData, index,                     elementData, index + 1,                     s - index);    elementData[index] = element;    size = s + 1;}

扩容操作

扩容怎么操作呢？
先申请一个新的内存空间，这个时候数组想扩多大就扩多大，
而后将原来的数组内容挪动到一个新的数组中，动静数组的一个动静扩容叫做一个伪扩容。
栈中援用的内容只认data，所以data进行一个从新指向就能够了，对应newData援用就没用了。
对于咱们来说看到的还是data，只不过对应的data指向了新的援用空间。
老的内存空间就干掉了，数组对应的物理地址援用，指向了新的内存空间。

s elementData.length
- s就是数组元素数量size
- elementData.length是数组长度
- 此时阐明数组占用的内存空间里没有闲暇空间，最初一个数组元素就在 数组长度-1 的地位上
- 这时要增加元素的话，因为原始申请的内存空间没有了，须要扩容持续申请内存空间
grow(size + 1)
- 扩容
- 底层就是数组的复制

Arrays.copyOf(elementData, newCapacity(minCapacity));

把原有数组所在的内存空间的元素，复制到新扩容的内容空间外面

public class ArrayList<E> extends AbstractList<E>      implements List<E>, RandomAccess, Cloneable, java.io.Serializable {  //间接数组最初元素增加的扩容  private void add(E e, Object[] elementData, int s) {      //ArrayList 的大小  初始化以后数组的长度      if (s  elementData.length)          //扩容操作          elementData = grow();      elementData[s] = e;      size = s + 1;  }  //指定元素地位增加的扩容  public void add(int index, E element) {      //...      final int s;      Object[] elementData;      if ((s = size)  (elementData = this.elementData).length)          elementData = grow();      //...  }    private Object[] grow() {      return grow(size + 1);  }  //减少容量以确保它至多能够包容最小容量参数指定的元素数量。  //参数：minCapacity – 所需的最小容量  private Object[] grow(int minCapacity) {      //数组 = 复制一个新数组，对应要复制的数组elementData，返回的正本的长度      return elementData = Arrays.copyOf(elementData,              newCapacity(minCapacity));  }}

grow(int minCapacity)：
- 数组拷贝到新数组中

具体扩容逻辑

newCapacity(minCapacity)
- minCapacity：size + 1
  - 扩容的最小容量是原来数组长度+1
int oldCapacity = elementData.length;
- 扩容前数组长度
int newCapacity = oldCapacity + (oldCapacity >> 1);
- 扩容后数组长度
- 旧数组长度 + 0.5倍的旧数组长度
- 每次扩容为原数组的1.5倍

<< : 左移运算符，num << 1,相当于num乘以2>> : 右移运算符，num >> 1,相当于num除以2

newCapacity - minCapacity <= 0
- 新容量 <= 最小容量
- 场景1：
  - return minCapacity;
  - 间接返回最小容量
    原来数组容量为1，则按动静扩容规定新数组容量为1.5；间接扩容的最小容量是2；那就间接返回最小容量
- 场景2：
  - elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    - 初始化数组，无参结构初始化数组
  - Math.max(DEFAULT_CAPACITY, minCapacity) 比拟最大的值为最新数组的容量
    - 如果增加元素对应数组大小小于10的时候，间接创立一个长度为10的数组。
  - ArrayList 都将扩大为 DEFAULT_CAPACITY「默认数组空间间接扩容大小为10」
- 场景3：
  - minCapacity < 0
    - 最小容量<0
    - 抛异样：内存不足异样
      - OutOfMemoryError

public class ArrayList<E> extends AbstractList<E>        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {        private int newCapacity(int minCapacity) {        // 旧容量  数组创立初始化的时候的容量        int oldCapacity = elementData.length;        //新容量是1.5倍旧容量  oldCapacity >> 1    oldCapacity除以2          int newCapacity = oldCapacity + (oldCapacity >> 1);        //新容量 <= 最小容量        if (newCapacity - minCapacity <= 0) {            //            if (elementData  DEFAULTCAPACITY_EMPTY_ELEMENTDATA)                //DEFAULT_CAPACITY = 10 默认初始容量                return Math.max(DEFAULT_CAPACITY, minCapacity);            //如果最小容量<0 内存不足异样            if (minCapacity < 0) // overflow                throw new OutOfMemoryError();            //新容量 <= 最小容量  间接返回 最小容量            return minCapacity;        }        return (newCapacity - MAX_ARRAY_SIZE <= 0)                ? newCapacity                : hugeCapacity(minCapacity);    }}

总结：

动静扩容数组1.5倍在数组长度大于10当前才真正失效。

删除元素

对应的删除，删除完对应下标元素后，须要把其它元素从后往前挪动。

把数组中索引为1的地位进行删除，对应咱们间接删除数据就能够。
然而数组是一个间断的内存空间，如果把1删除了对应的内存空间就不间断了，
所以要持续，把前面的数组元素往前挪动，进行一个元素的转移，
所以数组删除也不快，工夫复杂度也是O(n)级别的。

Objects.checkIndex(index, size);
- 先查看下对应传入的下标是否数组越界
fastRemove
- 疾速删除

oldValue

返回要删除的元素

public class ArrayList<E> extends AbstractList<E>    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {public E remove(int index) {    Objects.checkIndex(index, size);    final Object[] es = elementData;    @SuppressWarnings("unchecked") E oldValue = (E) es[index];    fastRemove(es, index);    return oldValue;}private void fastRemove(Object[] es, int i) {    modCount++;    //新数组长度    final int newSize;    //有点相似循环操作    if ((newSize = size - 1) > i)        //源数组：es；源数组中的起始地位：i + 1；指标数组：es；        //指标数据中的起始地位：i；要复制的数组元素的数量：newSize - i        //将指定源数组中的数组从指定地位开始复制到指标数组的指定地位        System.arraycopy(es, i + 1, es, i, newSize - i);    es[size = newSize] = null;}}

fastRemove(Object[] es, int i)
modCount
- 数组变动，所以自增
newSize
- 删除元素后新数组长度
- size - 1
i
- 要删除的元素下标
newSize > i
- 阐明删除的不是最初一个元素，须要进行数组拷贝
- 拷贝长度为newSize - i
  数组长度是6，删除下标为3的元素，则newSize=5，数组拷贝往前挪动2个（5-3）
最初更新数组长度

总结：

数组删，工夫复杂度也是O(n)级别的

获取元素/批改元素

public class ArrayList<E> extends AbstractList<E>        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {    public E get(int index) {        Objects.checkIndex(index, size);        return elementData(index);    }    public E set(int index, E element) {        Objects.checkIndex(index, size);        E oldValue = elementData(index);        elementData[index] = element;        return oldValue;    }}

get()办法去校验一下下标是否超出长度，超出就抛异样，没有超出就间接返回
set()办法同样也是先校验一下对应下标是否超出长度，如果超出就抛异样。如果没有就间接拿到这个下标内容，间接用传入的参数值替换掉

异样抛出状况

rangeCheckForAdd(index);

add()办法指定index增加元素应用：add(int index, E element)
传入下标和数组元素个数做比拟，下标只有大于数组个数抛数组越界异样，下标等于数组长度不抛异样
```
  private void rangeCheckForAdd(int index) {      if (index > size || index < 0)          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  }
```
Objects.checkIndex(index, size);
remove()，get()，set() 应用

传入下标和数组元素个数做比拟，下标等于元素个数也抛数组越界异样

public staticint checkIndex(int index, int length) {  return Preconditions.checkIndex(index, length, null);}

public static <X extends RuntimeException>  int checkIndex(int index, int length,BiFunction<String, List<Integer>, X> oobef) {      if (index < 0 || index >= length)          throw outOfBoundsCheckIndex(oobef, index, length);      return index;}

概念

特色