调集概念的由来

调集是为了便利存储和操作一组方针而规划，例如在实际开发中，咱们常常需求处理一组数据，例如存储用户信息、商品信息等，而调集类提供了一种便利的办法来办理这些数据。

调集与数组比较不同之处

  1. 动态扩展：调集类能够依据需求动态扩展巨细，而数组的巨细是固定的。 当然数组也是能够完成主动扩容，但需求手动进行完成。数组的默许巨细是依据你创立数组时分进行，指定数组长度，例如int[] arr = new int[10]，能够存放10个整数，假如不指定数组长度是不可进行运用。
  1. 更多的功用：调集类提供了许多实用的功用，例如迭代器、排序、查找等，能够大大提高开发功率
  1. 更高效的内存运用：调集类能够依据实际需求分配内存，而数组需求一次性分配一切内存，可能会构成内存糟蹋。

调集全家福

Collection集合体系全景图（一）

调集家庭成员分类

Collection调集是指一组单个数据元素的调集，这些元素能够是任何类型的方针，例如字符串、数字、自界说方针等。Collection调集包括List、Set和Queue三种类型。

  • List：是一种有序的调集，能够存储重复的元素。List调集中的元素能够经过索引拜访和修正，例如ArrayList、LinkedList等。
  • Set：是一种不答应重复元素的调集，元素的次序是不确定的。Set调集中的元素不能够经过索引拜访和修正，例如HashSet、TreeSet等。
  • Queue：是一种先进先出（FIFO）的调集，一般用于完成队列。Queue调集中的元素不能够经过索引拜访和修正，例如LinkedList、PriorityQueue等。

Map调集是指一组键/值对映射联系的调集，每个键对应一个值。Map调集中的键是仅有的，可是值能够重复。Map调集包括HashMap、TreeMap、LinkedHashMap等类型。常用的完成有：

  • HashMap：根据哈希表完成，无序的，答应键和值。
  • TreeMap：根据红黑树完成，有序的，不答应键，但答应值。
  • LinkedHashMap：根据哈希表和双向链表完成，有序的，答应键和值。

本章只写关于Collection调集成员家庭，Map家庭能够在后续章节进行弥补

Collection调集家庭成员介绍

Iterable接口介绍：

Iterable接口是Java调集结构中的一个接口，它是一切调集类的父接口，界说了一种迭代器的行为，使得调集类能够被迭代。Iterable接口中只要一个办法iterator()，该办法返回一个Iterator方针，用于遍历调集中的元素。

简略运用小事例

List<String> list = new ArrayList<>();
list.add("Java");
list.add("Python");
list.add("C++");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    System.out.println(element);
}

上述代码中，经过List调集的iterator()办法获取一个Iterator方针，然后运用while循环和next()办法遍历调集中的元素并输出。

Iterable 源码解读

Java中的Iterable接口是一个调集结构中的根本接口，Iterable接口的作用是提供一种统一的遍历调集元素的办法，使得不同的调集类能够运用相同的遍历办法，从而便利程序员进行调集操作。

Iterable 接口包括一个办法 iterator()，该办法返回一个 Iterator 方针，该方针能够用于遍历调集中的元素。

forEach办法是用来对调集中的每个元素履行指定的操作，这个操作由传入的Consumer函数式接口完成。默许完成是经过迭代器遍历调集中的元素，然后对每个元素履行操作。

spliterator办法是用来创立一个Spliterator方针，该方针能够对调集中的元素进行切割、遍历和处理。

Collection集合体系全景图（一）

1. Collection调集

Collection集合体系全景图（一）

Collection调集规划解读

Collection 是 Java 中的一个接口，它是一个调集结构的根底接口，界说了一些通用的办法，用于操作调集中的元素。它界说了一些通用的对调集操作办法，如增加元素、删去元素、判别元素是否存在、获取调集巨细等。接口答应咱们操作调集时不必关注具体完成， 从而达到“多态”。在面向方针编程语言中，接口一般用来构成标准。其他调集接口和类（Map 除外）都扩展或完成了Collection interface。

List接口特色

  • 承继 Collection调集接口

Collection集合体系全景图（一）

  • 有序：有序（元素存入调集的次序和取出的次序共同）。List中每个元素都有索引符号。能够依据元素的索引符号（在List中的方位）拜访元素。
  • 可重复：List答应参加重复的元素。更确切地讲，List一般答应满足条件的元素重复参加容器

List接口具体完成

Collection集合体系全景图（一）

ArrayList

Collection集合体系全景图（一）

ArrayList实际上是一个动态数组，容量能够动态的增长，其承继了AbstractList，完成了List, RandomAccess（随机拜访）, Cloneable, java.io.Serializable这些接口。

RandomAccess的作用是答应在数据结构中随机拜访元素，而不需求依照次序遍历整个数据结构。这种随机拜访能够大大提高数据结构的拜访功率，特别是关于大型数据结构来说。RandomAccess一般用于数组、列表等数据结构中，能够经过索引或下标来拜访元素。在Java中，完成了RandomAccess接口的数据结构能够运用快速随机拜访的算法，而没有完成该接口的数据结构则需求运用迭代器等办法来遍历元素。

简略说便是，假如完成RandomAccess接口就下标遍历，反之迭代器遍历 完成了Cloneable, java.io.Serializable意味着能够被克隆和序列化，LinkedList由于底层采用数据结构时双向链表（内存空间不接连)）所以就不支撑快速随机拜访的能力，有必要依次进行遍历。

Cloneable 接口是 Java 中的一个符号接口，用于指示一个类能够被克隆。完成 Cloneable 接口的类能够运用 Object 类中的 clone() 办法来创立一个新的方针，该方针与原始方针具有相同的状态。Cloneable 接口的作用是提供一种简略的办法来完成方针的仿制，而不需求重新创立一个新的方针并将其初始化为原始方针的副本。这在某些情况下能够提高程序的功能和功率。可是需求留意的是，clone() 办法是浅仿制，即只仿制方针的根本类型和引证类型的地址，而不会仿制引证类型所指向的方针。因此，在运用 clone() 办法时需求特别当心，避免出现意外的过错。

浅仿制和深仿制区别

浅仿制只仿制方针的引证，而不是方针本身。也便是说，新方针和原方针共享同一个引证类型的特点，修正其间一个方针的特点会影响另一个方针的特点。

Array.prototype.concat()：返回一个新数组，包括原数组和其他数组或值的仿制

深仿制则是将方针及其引证类型的特点悉数仿制一份，新方针和原方针互不影响。

JSON.parseObject(result) 办法属于深仿制

需求留意的是，深仿制可能会由于方针的循环引证而导致栈溢出或死循环

Serializable是Java中的一个接口，用于完成方针的序列化和反序列化。一个类完成了Serializable接口后，就能够将该类的方针转换成字节序列，以便在网络上传输或者保存到本地文件中。一起，也能够将字节序列反序列化成方针，以便在程序中运用。

ArrayList 运用办法

// 初始化一个 String 类型的数组 
String[] stringArr = new String[]{"hello", "world", "!"}; 
// 修正数组元素的值
stringArr[0] = "goodbye"; System.out.println(Arrays.toString(stringArr));
// [goodbye, world, !] 
// 删去数组中的元素，需求手动移动后边的元素 
for (int i = 0; i < stringArr.length - 1; i++) { 
stringArr[i] = stringArr[i + 1]; 
} 
stringArr[stringArr.length - 1] = null;
System.out.println(Arrays.toString(stringArr));

ArrayList优缺陷：

优点：

  1. 能够动态地增加和删去元素，不需求预先指定数组的巨细；
  2. 能够存储任何类型的方针，包括根本数据类型的包装类；
  3. 能够经过索引快速拜访元素；
  4. 能够运用迭代器遍历调集中的元素；
  5. 能够运用泛型来确保调集中元素的类型安全。

缺陷：

  1. 在刺进或删去元素时，需求移动其他元素，功率较低；
  2. 在很多元素的情况下，可能会占用较大的内存空间；
  3. 不支撑多线程并发拜访，需求手动进行同步处理；
  4. 在进行元素查找时，功率较低，由于需求遍历整个调集。

ArrayList源码阅读

List list = new ArrayList<>(); 创立一个 ArrayList一个履行流程是

// 经过结构办法进行初始化
    /**  
    *默许无参结构函数  
     *DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10，
      也便是说初始其实是空数组 当增加第一个元素的时分数组容量才变成10  
    */
    public ArrayList() {  
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  
    }
    /**  
* 带初始容量参数的结构函数（用户能够在创立ArrayList方针时自己指定调集的初始巨细）  
*/  
public ArrayList(int initialCapacity) {  
  if (initialCapacity > 0) {  
   this.elementData = new Object[initialCapacity];  
} else if (initialCapacity == 0) {  
   this.elementData = EMPTY_ELEMENTDATA;  
} else {  
   throw new IllegalArgumentException("Illegal Capacity: "+  
   initialCapacity);  
}  
}

elementData和DEFAULTCAPACITY_EMPTY_ELEMENTDATA解读

    private static final long serialVersionUID = 8683452581122892189L;
    /**  
    * 默许初始容量巨细  
    */  
    private static final int DEFAULT_CAPACITY = 10;  
    /**  
    * 空数组（用于空实例）。  
    */  
    private static final Object[] EMPTY_ELEMENTDATA = {};  
    /**  
    * 空数组（用于空实例）。  
    */  
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  
    /**  
    * 保存ArrayList数据的数组  
    */  
    transient Object[] elementData;  
    /**  
    * 保存ArrayList数据的数组  
    */  
    private int size;
    //在这里能够看到咱们不解的 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    //实际上是一个空的方针数组，当增加第一个元素的时分数组容量才变成10
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

增加办法add

    ```
  /**
     * 将指定的元素追加到此列表的结尾。
     */
    public boolean add(E e) {  
      ensureCapacityInternal(size + 1); // Increments modCount!!  
      elementData[size++] = e;  
      return true;  
     }
    /** 在此列表中的指定方位刺进指定的元素。
    *先调用 rangeCheckForAdd 对index进行界限查看然后调用 ensureCapacityInternal 办法确保capacity足够大；
    *再将从index开端之后的一切成员后移一个方位；将element刺进index方位；最终size加1。
    */ 
    public void add(int index, E element) { 
    rangeCheckForAdd(index); 
    ensureCapacityInternal(size + 1); 
    // Increments modCount!! 
    //arraycopy()这个完成数组之间仿制的办法必定要看一下，
    //下面就用到了arraycopy()办法完成数组自己仿制自己 
    //System.arraycopy 是 Java 中的一个办法，
    //用于将一个数组的一部分仿制到另一个数组中的指定方位。
    //它的作用是快速地将一个数组的部分内容仿制到另一个数组中，
    //能够用于数组的仿制、合并、排序等操作，
    //其间，src 表明源数组，srcPos 表明源数组的开始方位，
    //dest 表明方针数组，destPos 表明方针数组的开始方位，
    //length 表明要仿制的元素个数。该办法是一个静态办法，能够直接经过类名调用
    System.arraycopy(elementData, index, elementData, index + 1, size - index); 
    elementData[index] = element;
    size++; }

这个办法便是将一个元素增加到数组的size++方位上。ensureCapacityInternal，它是用来扩容的，准确说是用来进行扩容查看的

    private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));  
    }
    private void ensureExplicitCapacity(int minCapacity) {  
    modCount++;  
    if (minCapacity - elementData.length > 0)  
    grow(minCapacity);  
    }
    private static int calculateCapacity(Object[] elementData, int minCapacity) {  
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  
    return Math.max(DEFAULT_CAPACITY, minCapacity);  
    }  
    return minCapacity;
    private void grow(int minCapacity) {  
    int oldCapacity = elementData.length;  
    int newCapacity = oldCapacity + (oldCapacity >> 1);  
    if (newCapacity - minCapacity < 0)  
    newCapacity = minCapacity;  
    if (newCapacity - MAX_ARRAY_SIZE > 0)  
    newCapacity = hugeCapacity(minCapacity);  
    elementData = Arrays.copyOf(elementData, newCapacity);  
}
    private static int hugeCapacity(int minCapacity) {  
    if (minCapacity < 0) // overflow  
    throw new OutOfMemoryError();  
    return (minCapacity > MAX_ARRAY_SIZE) ?  
    Integer.MAX_VALUE :  
    MAX_ARRAY_SIZE;  
}
    }

  • 参数 minCapacity 表明需求存储的元素数量的最小值。

  • calculateCapacity(elementData, minCapacity) 是一个内部办法，用于计算实际需求的容量巨细。

  • ensureExplicitCapacity() 是另一个内部办法，用于查看当时容量是否足够，假如不够则进行扩容。

  • 因此，ensureCapacityInternal() 的作用便是先计算需求的容量巨细，然后查看当时容量是否足够，假如不够则进行扩容，以确保 ArrayList 内部的容量足够存储指定的元素数量。

  • grow办法具体完成是先将原数组的容量（oldCapacity）右移一位（相当于除以2），然后将得到的结果加上原数组的容量，得到新的容量（newCapacity）。假如新容量依然小于指定的最小容量，则将新容量设置为指定的最小容量。

  • 假如新容量超过了数组的最大容量（Integer最大值-8），则调用另一个办法（hugeCapacity）来获取一个合适的容量值。这个办法呢判别当时值大于Arrary最大值（Integer最大值-8 ）返回Integer最大值否则返回Arrary最大值（Integer-8）

  • 最终，运用Arrays.copyOf办法将原数组的元素仿制到新数组中，并将新数组赋值给原数组变量elementData。

ArrayList支撑两种删去

  1. remove(int index) 依照下标删去 常用
  2. remove(Object o) 依照元素删去 会删去和参数匹配的第一个元素
    /** 移除list中指定方位的元素 一切后续元素左移 下标减1
    *参数是要移除元素的下标
    返回值是被移除的元素 
    */
    public E remove(int index) {
    //下标越界查看 rangeCheck(index); 
    //修正次数统计 modCount++; 
    //获取这个下标上的值 
    E oldValue = elementData(index); 
    //计算出需求移动的元素个数 （由于需求将后续元素左移一位 此处计算出来的是后续元素的位数） 
    int numMoved = size - index - 1; 
    //假如这个值大于0 阐明后续有元素需求左移 是0阐明被移除的方针便是最终一位元素 
    if (numMoved > 0)
    //索引index只要的一切元素左移一位 覆盖掉index方位上的元素 
    System.arraycopy(elementData, index+1, elementData, index,numMoved); 
    // 将最终一个元素赋值为null 这样就能够被gc回收了
    elementData[--size] = null; 
    //返回index方位上的元素 return oldValue; } 
    //移除特定元素 public boolean remove(Object o) { 
    //假如元素是null 遍历数组移除第一个null 
    if (o == null) { 
    for (int index = 0; index < size; index++) 
    if (elementData[index] == null) {
   //遍历找到第一个null元素的下标 调用下标移除元素的办法 
    fastRemove(index); 
     return true;
    } 
    } else { 
    //找到元素对应的下标 调用下标移除元素的办法
    for (int index = 0; 
     index < size; index++) 
    if (o.equals(elementData[index])) { 
    fastRemove(index); return true; 
    } 
    } 
    return false;
    } 
    //依照下标移除元素
    private void fastRemove(int index)    { 
    modCount++; int numMoved = size - index - 1; 
    if (numMoved > 0) 
    System.arraycopy(elementData, index+1, elementData, index, numMoved); 
    elementData[--size] = null;
    }

ArrayList总结

  1. 底层数组完成，运用默许结构办法初始化容量是10
  2. 扩容的长度是在原长度根底上加二分之一
  3. 完成了RandomAccess接口，底层又是数组,读取元素功能很好
  4. 线程不安全，一切的办法均不是同步办法也没有加锁，因此多线程下慎用
  5. 次序增加快删去和刺进需求仿制数组 功能很差

赠送一张总结收拾

Collection集合体系全景图（一）