生命不息，学习不止，对一切都要维持敬畏之心。
若有不正之处，请谅解和批评指正，不胜感激。

1.集合关系图

图片说明

1.1 为什么要有集合

数组长度不可变,浪费资源,不方便

1.2 什么是集合

Java 所有的集合类都位于 java.util 包下，提供了一个表示和操作对象集合的统一构架，包含大量集合接口，以及这些接口的实现类和操作它们的算法。java中的集合主要分为Collection和Map两种

2.迭代器

2.1 为什么要有迭代器

对不同集合遍历的前提是必须了解各个集合的底层实现，这使得集合与其遍历方式存在很强的耦合关系,为了解决这种耦合关系,设计了迭代器,为遍历不同的集合结构提供一个统一的接口,这样既可以做到不暴露集合的内部结构，又可让外部代码透明地访问集合内部的数据.

2.2 迭代器模式

Iterable:抽象容器,接口,提供一个Iterator抽象方法.
ArrayList/LinkedList/HashSet/TreeSet/:具体容器,抽象容器的实现类,
Iterator:抽象迭代器,接口,提供需要实现的方法
迭代器实现：实现迭代器接口中定义的方法，完成集合的迭代。
参考资料传送门

2.3 为什么每个具体容器要重写自己的抽象迭代器里面的方法

为了防止被破坏结构而且容器实现原理不同

ArrayList的父类AbstractList已经实现了Iterator接口，为什么ArrayList还要自己实现Iterator接口呢？
ArrayList是线程不安全的,不允许在迭代过程中修改容器的结构,比如add,remove,clear,会触发fail-fast机制.
参考资料传送门
关于fast-fail机制

3.Collection

图片说明

java.util.Collection
单列集合的顶层接口,根接口,
继承Iterable
重复,有序/无序
可插入null
public boolean add(E e)：把给定的对象添加到当前集合中。
public void clear() :清空集合中所有的元素。
public boolean remove(E e): 把给定的对象在当前集合中删除。
public boolean contains(Object obj): 判断当前集合中是否包含给定的对象。
public boolean isEmpty(): 判断当前集合是否为空。
public int size(): 返回集合中元素的个数。
public Object[] toArray(): 把集合中的元素，存储到数组中

4.List

图片说明

java.util.List
有序,有索引,元素可重复
可插入null
特有方法
public void add(int index, E element): 将指定的元素，添加到该集合中的指定位置上。
public E get(int index):返回集合中指定位置的元素。
public E remove(int index): 移除列表中指定位置的元素, 返回的是被移除的元素。
public E set(int index, E element):用指定元素替换集合中指定位置的元素,返回值的更新前的元素
public int indexOf(Object o):返回此列表中第一次出现的指定元素的索引；如果此列表不包含该元素，则返回 -1。
List<e> subList(int fromIndex,int toIndex):返回列表中指定的 fromIndex（包括）和 toIndex（不包括）之间的部分视图</e>
ListIterator<e> listIterator(int index):返回列表中元素的列表迭代器（按适当顺序），从列表的指定位置开始</e>
ListIterator<e> listIterator():返回此列表元素的列表迭代器（按适当顺序）。</e>

4.1 ArrayList

图片说明

java.util.ArrayList
有序,有索引,可重,可null,可序列化,可快速查找,可复制
线程不安全
由于底层是数组实现,所以查询快,增删慢
长度可变集合
无特有功能
增删改查转数组遍历

4.1.1 AstractList

虽然是抽象类,但是只有一个抽象方法
如果想使用add,set,remove操作,实现类必须重写这三个方法,应为虽然AstractList实现了这三个方法,但是默认都是不支持的

实现了俩个迭代器,listIterator比Iterator因为有索引的关系,扩展了几个方法,允许向前遍历.

4.1.2 几个重要的成员

图片说明

modCount:这个不允许序列化的成员主要是为了尽最大可能的检测出现不同步并发修改.当对集合进行add,remove,clear等长度结构变化操作时候,会进行自加,在fail-fast机制下,抛出ConcurrentModificationException异常.

4.1.3 扩容

三个构造函数,分别支持,初始化0的容器,指定容量容器,指定另一个集合容器
相对于1.7有个变化

定义了俩个常量作为初始化容器;

有参数的情况下,初始化会直接使用短一点的常量进行初始化

无参情况下,会使用长一些常量初始化
然而1.7中,有参构造函数如果发现传入容量为0,或传入集合的长度为零,就是新创建一个数组,1.8的改动应该是为了节约空间进行了优化.*
使用无参构造函数初始化容器情况下,默认Object类型空数组,在第一次add的时候将容量扩容到10;
如果发现需要的容量大于当前容器的容量,那么进行扩容,尝试扩容到当前容器长度的1.5倍,如果需要的容量依然大于1.5倍后的当前容量,那么直接扩容到需求的容量.

4.1.4 实现一个简易版的ArrayList

增改查,实现迭代器,遍历.

/**
* 简易ArrayList
*/
public class ArrayList_<E> implements Iterable<E> {
  /**
   *初始化容量
   */
  private final int DEFAULT_SIZE=10;

  /**
   * 带参构造函数参数长度为0是初始化数组;
   */
  private static final Object[] EMPTY_ELEMENT_DATA={};

  /**
   * 空参构造初始化数组长度
   */
  private static final Object[] DEFAULT_EMPTY_DATA={};

  /**
   * 存储元素的数组
   */
 transient Object[] elementData;

  /**
   * 容器元素个数
   */
  private int size;

  /**
   * 初始化一个空数组
   */
  public ArrayList_() {
      this.elementData=DEFAULT_EMPTY_DATA;
  }

  /**
   * 初始化带容量的数组
   * @param initCapacity
   */
  public ArrayList_(int initCapacity) {
      if(initCapacity==0){
          this.elementData=EMPTY_ELEMENT_DATA;
      }else if(initCapacity>0){
          this.elementData=new Object[initCapacity];
      }else{
          new IllegalArgumentException("参数异常:"+initCapacity);
      }
  }

  /**
   * 是否需要扩容
   * @param minCapacity 需要的容量
   */
  private void ensureCapacity(int minCapacity){
      if(this.elementData==DEFAULT_EMPTY_DATA){
          minCapacity=Math.max(DEFAULT_SI***Capacity);
      }
      if(minCapacity-this.elementData.length>0){
          grow(minCapacity);
      }
  }

  /**
   * 扩容
   * @param minCapacity 需要的容量
   */
  private void grow(int minCapacity){
      int oldLength=this.elementData.length;
      int newLength=oldLength+oldLength>>1;
      if (minCapacity-newLength>0){
          newLength=minCapacity;
      }
      this.elementData= Arrays.copyOf(this.elementData,newLength);

  }

  /**
   * 添加元素
   * @param e
   * @return
   */
  public boolean add(E e){
      ensureCapacity(size+1);
      elementData[size++]=e;
      return true;
  }

  /**
   * 指定索引位置添加元素
   * @param index
   * @param e
   * @return
   */
  public void add(int index,E e){
      //校验索引
      checkIndex(index);
      //扩容
      grow(size+1);
      //计算位移位置
      int moveNum=size-index;
      System.arraycopy(elementData,index,elementData,index+1,moveNum);
      elementData[index]=e;
      size++;
  }

  /**
   * 指定索引处更改容器内容
   * @param index
   * @param e
   * @return 被替换的值
   */
  public E set(int index,E e){
      //校验索引
      checkIndex(index);
      E oldValue=(E)elementData[index];
      elementData[index]=e;
      return oldValue;
  }

  /**
   * 根据索引获取元素
   * @param index
   * @return
   */
  public E get(int index){
      checkIndex(index);
      return (E)elementData[index];
  }

  /**
   * 校验索引是否越界
   * @param index 索引
   */
  private void checkIndex(int index){
      if(index>size||index<0){
          throw new IndexOutOfBoundsException("索引越界");
      }
  }

  /**
   * 实现抽象容器(Iterable)方法
   * @return
   */
  @Override
  public Iterator<E> iterator() {
      return new itr();
  }

  /**
   * 具体容器中使用私有内部类实现抽象容器功能
   */
  private class itr implements Iterator<E>{
      private int cursor;

      @Override
      public boolean hasNext() {
          return cursor!=size;
      }

      @Override
      public E next() {
          if(cursor>size)
              throw new NoSuchElementException("无元素");
          return (E)elementData[cursor++];
      }
  }

  @Override
  public String toString() {
      StringBuilder sb=new StringBuilder("[");
      for (int i = 0; i <size; i++) {
          if(i!=0){
              sb.append(",");
          }
          sb.append(elementData[i]);
      }
      sb.append("]");
      return sb.toString();
  }
}

4.2 LinkedList

继承体系

java.uti.LinkedList
底层双向链表实现,所以查询慢,增删快
线程不安全,效率高
有序,有索引,可存null
特有方法
public void addFirst(E e):将指定元素插入此列表的开头。
public void addLast(E e):将指定元素添加到此列表的结尾。
public E getFirst():返回此列表的第一个元素。
public E getLast():返回此列表的最后一个元素。
public E removeFirst():移除并返回此列表的第一个元素。
public E removeLast():移除并返回此列表的最后一个元素。
public E pop():从此列表所表示的堆栈处弹出一个元素。
public void push(E e):将元素推入此列表所表示的堆栈。

4.2.1 LinkedList和ArrayList都说有索引,有序,为什么会出现ArrayList查询快而LinkedList慢呢?

ArrayList集合中的索引是标示出来的，而LinkedList集合中的索引是隐式的,链表中节点是有索引的,但是节点并不知道自己索引是多少,所以必须从头节点遍历一下,才可以知道节点的索引.

5.Set

图片说明

元素唯一
有序/无序
允许null
底层实现为HashMap
迭代器也是在HashMap中KeySet最终内部类实现的
线程不安全

5.1 HashSet如何确保不重复的

什么是hash码值？
在java中存在一种hash表结构，它通过一个算法，计算出的结果就是hash码值；这个算法叫hash算法；
hash算法是怎么计算的呢？
是通过对象中的成员来计算出来的结果；
如果成员变量是基本数据类型的值，那么用这个值直接参与计算；
如果成员变量是引用数据类型的值，那么获取到这个成员变量的哈希码值后，再参数计算

如果hash码值不相同，说明是一个新元素，存；
如果没有元素和传入对象（也就是add的元素）的hash值相等，那么就认为这个元素在table中不存在，将其添加进table；
如果hash码值相同，且equles判断相等，说明元素已经存在，不存；
如果hash码值相同，且equles判断不相等，说明元素不存在，存；
所以,自定义引用类型想要按照属性来决定是否重复.就要重写hashCode和equels俩个方法;*

5.2 TreeSet

java.util.TreeSet
排序元素唯一
线程不安全
集合中存储的对象必须实现Comparable接口/TreeSet构造函数传入匿名内部类Comparator<自定义类>
不需要重写hashCode和equals方法来保证唯一性
便于插入查找删除
基于TreeMap

查缺补漏-JAVA基础-集合

1.集合关系图

1.1 为什么要有集合

1.2 什么是集合

2.迭代器

2.1 为什么要有迭代器

2.2 迭代器模式

2.3 为什么每个具体容器要重写自己的抽象迭代器里面的方法

3.Collection

4.List

4.1 ArrayList

4.1.1 AstractList

4.1.2 几个重要的成员

4.1.3 扩容

4.1.4 实现一个简易版的ArrayList

4.2 LinkedList

4.2.1 LinkedList和ArrayList都说有索引,有序,为什么会出现ArrayList查询快而LinkedList慢呢?

5.Set

5.1 HashSet如何确保不重复的

5.2 TreeSet