关于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 static
  int 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;
  }