Java集合

1.集合

1.1.概念

• 集合是java中提供的一种长度可变的存储任意引用类型的容器，可以用来存储多个数据。
• 集合按照其存储结构可以分为两大类，分别是单列集合 java.util.Collection 和双列集合java.util.Map

1.2.Collection单列集合

1.2.1.关于Collection

• Collection：单列集合类的根接口，用于存储一系列符合某种规则的元素，它有两个重要的子接口，分别是 java.util.List 和 java.util.Set 。其中， List 的特点是元素有序、元素可重复。 Set 的特点是元素无序，而且不可重复。 List 接口的主要实现类有 java.util.ArrayList和 java.util.LinkedList ， Set 接口的主要实现类有 java.util.HashSet 和java.util.TreeSet 。
• Collection的继承关系：
  • Collection接口
    • List接口
      • Vector(线程安全)
        • Stack(线程安全)
      • ArrayList
      • LinkedList
    • Queue接口
      • Deque接口
        • ArrayDeque
        • BlockingDeque接口
          • LinkedBlockingDeque
      • BlockingQueue接口
    • BlockingDeque
      • LinkedBlockingDeque(线程安全)
        • ArrayBlockingQueue(线程安全)
        • LinkedBlockingQueue(线程安全)
    • Set接口
      • HashSet
        • LinkedHashSet
      • SortedSet接口
        • NavingableSet接口
          • TreeSet
• Collection常用功能
  • Collection是所有单列集合的父接口，因此在Collection中定义了单列集合(List和Set)通用的一些方法，这些方法可用于操作所有的单列集合。方法如下：
    • public boolean add(E e) ：把给定的对象添加到当前集合中 。
    • public void clear() :清空集合中所有的元素。
    • public boolean remove(E e) : 把给定的对象在当前集合中删除。
    • public boolean contains(E e) : 判断当前集合中是否包含给定的对象。
    • public boolean isEmpty() : 判断当前集合是否为空。
    • public int size() : 返回集合中元素的个数。
    • public Object[] toArray()：把集合中的元素，存储到数组中。
    • public T[] toArray(T[] a)：返回包含此 collection 中所有元素的数组；返回数组的运行时类型与指定数组
      • 如果我们提供一个数组，并且这个数组足够长，它会返回一个和给定长度相等长度的数组，剩余空间用null填充，当做参数的数组和返回的数组会变成和返回的数组一样的
      • 如果不足够长, 返回的数组等价于集合类中存储的元素数目, 原来当做参数的数组, 会维持原来的长度，并且内容全是null

1.2.2.迭代器

• 迭代器：JDK提供了一个接口java.util.Iterator 用于遍历集合元素。 Iterator 接口也是Java集合中的一员，但它与 Collection 、 Map 接口有所不同， Collection 接口与 Map 接口主要用于存储元素，而 Iterator 主要用于迭代访问（即遍历）Collection 中的元素，因此 Iterator 对象也被称为迭代器。
  • public Iterator iterator()：是Collection集合里的方法，获取某集合对应的迭代器，用来遍历集合中的元素的。返回值为一个Interator的实例对象。
  • public E next()：返回迭代的下一个元素。
  • public boolean hasNext()：如果仍有元素可以迭代，则返回 true。
  • public void remove()：删除上一次遍历过的元素(不能连续删除)

    public class IteratorDemo {
    public static void main(String[] args) {
        // 使用多态方式 创建对象
        Collection<String> coll = new ArrayList<String>();
        // 添加元素到集合
        coll.add("串串星人");
        coll.add("吐槽星人");
        coll.add("汪星人");
        //遍历
        //使用迭代器 遍历 每个集合对象都有自己的迭代器
        //在这里it仅仅作为一个引用来接收iterator的具体实例，方便使用而已。
        Iterator<String> it = coll.iterator();
        // 泛型指的是 迭代出 元素的数据类型
        while(it.hasNext()){ //判断是否有迭代元素
            String s = it.next();//获取迭代出的元素
            System.out.println(s);
    	   	}
        }
    }
  
  

  • Iterator迭代器对象在遍历集合时，内部采用指针的方式来跟踪集合中的元素,在调用Iterator的next方法之前，迭代器的索引位于第一个元素之前，不指向任何元素，当第一次调用迭代器的next方法后，迭代器的索引会向后移动一位，指向第一个元素并将该元素返回，当再次调用next方法时，迭代器的索引会指向第二个元素并将该元素返回，依此类推，直到hasNext方法返回false，表示到达了集合的末尾，终止对元素的遍历。
  • 特别注意：

    Collection coll= new ArrayList();
    coll.add("zs");
    coll.add("ls");
    coll.add("wu");
    coll.add("zl");
  
    // zs  ls  wu  zl
    //collection1.remove("zs");  //放在迭代器创建之前不会抛出异常
    Iterator iterator = collection1.iterator();
    //collection1.remove("zs");  //放在迭代器刚刚创建的地方也会抛出异常
    iterator.next();
    collection1.remove("zs");  //会抛出异常，可以把这个语句放在最下边或者最上边
    iterator.next();
    //collection1.remove("zs");  //迭代完毕后再修改，放在最下边不会抛出异常
  
    // 抛出异常：ConcurrentModificationException并发修改异常
  

  • 解释：在iterator迭代中, 通过iterator返回的迭代对象, 会保存原集合数据的修改次数, 并且这个iterator再每次通过原集合类中的方法遍历的时候, 会重复检查, 保存修改次数, 和此时此刻的原集合类的修改次数是否还一样, 如果不一样, 意味着, 这个原集合类在迭代的过程中, 被别人修改了, 这个iterator就会抛出并发修改异常。比如list.add()方法和list.remove()方法(添加和删除操作)都会引发并发修改异常
  • 怎么避免抛出并发修改异常
    • 多线程, 没有办法避免。只能避免这个集合被两个线程持有。
    • 单线程, 避免迭代的过程还没有迭代结束, 就使用源集合类的方法修改了源集合类。可以使用迭代器提供的方法来修改，比如remove()方法。
  • Iterator为什么设计成一个接口？
    • 假设迭代器定义的是一个类，这样我们就可以创建该类的对象，调用该类的方法来实现集合的遍历。但是，Java提供了很多的集合类，这些集合类的数据结构是不同的。所以，存储的方式和遍历的方式应该是不同的。进而它们的遍历方式也应该不是一样的。最终，就没有定义迭代器类。
    • 无论哪种集合，都应该具备获取元素的操作，而且，最好在辅助于判断功能，这样，在获取前，先判断，更不容易出错。也就是说，判断功能和获取功能应该是一个集合遍历所具备的，而每种集合的方式又不太一样，所以我们把这两个功能给提取出来，并不提供具体实现，这种方式就是接口。

1.2.3.增强for循环

• 增强for循环(也称for each循环)是JDK1.5以后出来的一个高级for循环，专门用来遍历数组和集合的。它的内部原理其实是个Iterator迭代器，所以在遍历的过程中，不能对集合中的元素进行增删操作。本质上就是一个Interator迭代器。

for(元素的数据类型 变量 : Collection集合or数组){
  	//写操作代码
  }

注：

• 用于遍历Collection和数组。通常只进行遍历元素，不在遍历的过程中对集合元素进行增删操作。
• 新for循环必须有被遍历的目标。目标只能是Collection或者是数组。新式for仅仅作为遍历操作出现。
• 只有实现了Interator方法的集合类，才可以使用增强for循环。
• 因为其本质是Interator迭代器，所以不能在增强for循环中调用原集合类的方法修改原集合类的数据，会报出并发修改异常。即仅仅遍历用。
• 数组是增强for循环的唯一特殊之处，数组可以使用且可以修改内容

• Example

  public class EnhanceFor{
      public static void main(String[] args) {
          
          //遍历数组
          int[] arr = {3,5,6,87};
          //使用增强for遍历数组
          for(int a : arr){//a代表数组中的每个元素
          	System.out.println(a);
          }
          
          //遍历集合
          Collection<String> coll = new ArrayList<String>();
          coll.add("小河神");
          coll.add("老河神");
          coll.add("神婆");
          //使用增强for遍历
          for(String s :coll){//接收变量s代表 代表被遍历到的集合元素
          	System.out.println(s);
      }
  }

1.3.List接口

1.3.1.关于List

• java.util.List 接口继承自 Collection 接口，是单列集合的一个重要分支，习惯性地将实现了 List 接口的对象称为List集合。在List集合中允许出现重复的元素，所有的元素是以一种线性方式进行存储的，且允许null元素存在，在程序中可以通过索引来访问集合中的指定元素。另外，List集合还有一个特点就是元素有序，即元素的存入顺序和取出顺序一致。
• List接口特点：
  1. 它是一个元素存取有序的集合。(例如，存元素的顺序是11、22、33。那么集合中，元素的存储就是按照11、22、33的顺序完成的）。
  2. 它是一个带有索引的集合，通过索引就可以精确的操作集合中的元素（与数组的索引是一个道理）。
  3. 集合中可以有重复的元素，通过元素的equals方法，来比较是否为重复的元素。

1.3.2.常用方法

• List作为Collection集合的子接口，不但继承了Collection接口中的全部方法，而且还增加了一些根据元素索引来操作集合的特有方法
  • public void add(int index, E element) : 将指定的元素，添加到该集合中的指定位置上。
  • public boolean addAll(int index, Collection<? extends E> c)：将指定 collection 中的所有元素都插入到列表中的指定位置（可选操作）。
• public E get(int index) :返回集合中指定位置的元素。
  • public E remove(int index) : 移除列表中指定位置的元素, 返回的是被移除的元素。
• public E set(int index, E element) :用指定元素替换集合中指定位置的元素,返回值的更新前的元素。
  • public int indexOf(Object o)：返回此列表中第一次出现的指定元素的索引；如果此列表不包含该元素，则返回 -1。
  • public int lastIndexOf(Object o)：返回此列表中最后出现的指定元素的索引；如果列表不包含此元素，则返回 -1。
  • public List subList(int fromIndex, int toIndex) ：返回列表中指定的 fromIndex（包括 ）和 toIndex（不包括）之间的部分视图。
    

    视图相当于一个指针，修改视图内容也会导致原集合被修改。

1.3.3.List的子类

1. ArrayList集合
   • java.util.ArrayList 集合数据存储的结构是数组结构。初始容量为10，扩容机制为每次容量不够就扩容为原来容量的1.5倍，元素增删慢，查找快，非线程安全的，由于日常开发中使用最多的功能为查询数据、遍历数据，所以 ArrayList 是最常用的集合。
   • ArrayList的clone()方法，是原集合的一个浅表副本，不是深拷贝，也不是视图方法。

    //ArrayList源码分析(默认初始容量与扩容方法)
        ArrayList<Integer> list = new ArrayList();
        list.add(1);
    
    
    //对于以上方法，实现过程为：
    public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {
        //记录修改次数，继承于AbstractList
        protected transient int modCount = 0;
        
        //数组的容量，默认初始值为0。
        private int size;
        
        //初始容量大小
        private static final int DEFAULT_CAPACITY = 10;
        
        //类中定义的最大值
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
        
    	//ArrayList底层所维护的数组，用于存储元素，使用transient关键字不可被序列化。
    	transient Object[] elementData;
        
        //两个空数组，一个用于比较或赋值，一个用于默认初始化相关
        private static final Object[] EMPTY_ELEMENTDATA = {};
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
        
        //构造方法，只是为了创建一个空数组，所以默认的构造方法并不能直接给我们创建一个容量为10的数组
        //既然构造方法不能创建一个容量为10的数组，那么肯定在添加方法中创建了一个容量为10的数组
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    
        public boolean add(E e) {
            //TODO：参数检查以及扩容
            //一般来说，在初始情况下，创建一个容量为10的默认长度的数组，如果这个数组满了，那么就扩容
            //这个时候初始状态传入的参数只是 0 + 1 = 1;
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
        //初始状态传入参数为1
        private void ensureCapacityInternal(int minCapacity) {
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }
        //扩容之前先检查，计算一下容量
        private static int calculateCapacity(Object[] elementData, int minCapacity) {
            //构造方法刚刚赋值过，所以第一次检查肯定是相等
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                //minCapacity是传入的1，方法结束后必定返回10
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
        }
        private void ensureExplicitCapacity(int minCapacity) {
            //记录这个对象被修改的次数。
            modCount++;
            // 检测，此时 10 - 0 > 0 ，为真
            // 如果是第二次添加，此时 已经变为 2 - 10 ，不会扩容
            if (minCapacity - elementData.length > 0)
                //调用扩容方法
                grow(minCapacity);
        }
        // 传入参数minCapacity为10
        private void grow(int minCapacity) {
            // 空数组，旧的长度是0
            int oldCapacity = elementData.length;
            // 新长度为原来的1.5倍，还是0
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            // 如果新长度减去旧长度小于0
            if (newCapacity - minCapacity < 0)
                // 新容量为10
                newCapacity = minCapacity;
            // 新长度减去 Integer.MAX_VALUE - 8 必定是假;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // Arrays.copyOf 复制elementData本身，复制的长度为10，并赋值给其本身，不够的使用null填充
            // static <T> T[] copyOf(T[] original, int newLength) 复制指定的数组，截取或用null填充（如有必要），以使副本具有指定的长度。 
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }
    
    
    //ArrayList源码分析(其他的构造器)
    	ArrayList<Integer> list = new ArrayList<>(100);
    
    	// ArrayList(Collection<? extends E> c)
    	// 当做参数传进来的集合类里面存储的参数类型应与当前集合类对象存储参数类型相同或者是其子类
    	ArrayList<Integer> list1 = new ArrayList<>(list);
    
    public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {
        //构造方法
        public ArrayList(int initialCapacity) {
            //如果给定的长度大于0，那么直接创建一个数组
            if (initialCapacity > 0) {
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
                throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
            }
        }
        
        //补充：一个API，手动确认容量和扩容，因为ArrayList可以自动扩容，所以应用几乎为0
        public void ensureCapacity(int minCapacity) {
            int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                // any size if not default element table
                ? 0
                // larger than default for default empty table. It's already
                // supposed to be at default size.
                : DEFAULT_CAPACITY; // 默认值10
    
            if (minCapacity > minExpand) {
                ensureExplicitCapacity(minCapacity);
            }
        }
        
        //构造方法
        public ArrayList(Collection<? extends E> c) {
            // 把c这个Collection集合类转化为数组
            Object[] a = c.toArray();
            // 如果这个数组的大小不为0
            if ((size = a.length) != 0) {
                // 如果这个集合确实是ArrayList集合
                if (c.getClass() == ArrayList.class) {
                    // 直接将其赋值给底层维护的数组
                    elementData = a;
                } else {
                    // 否则只拷贝该数组的内容给底层维护数组
                    elementData = Arrays.copyOf(a, size, Object[].class);
                }
            } else {
                // 如果数组大小为0，直接赋值为初始的空数组
                elementData = EMPTY_ELEMENTDATA;
            }
        }
    }
    
    
    //ArrayList源码分析(内部迭代器)
        ArrayList<String> list = new ArrayList<>();
        list.add("zs");
        list.add("ls");
        list.add("wu");
        list.add("zl");
    
    	Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    
    	
    //对于以上代码，分析其内部的迭代器
    public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {
        //首先调用其内部函数，返回一个Iterator的迭代器的实现类
        //不能return一个接口，但是接口可以作为方法声明时的返回类型，返回其实现类即可
        public Iterator<E> iterator() {
            return new Itr();
        }
    	//ArrayList内部类，实现了Iterator接口。
        private class Itr implements Iterator<E> {
            int cursor;       // 初始值0  :  指向下一个要遍历的位置
            int lastRet = -1; // 初始值-1 :  上一次遍历的元素
    
            // 把迭代器的expectedModCount和原集合类同步
            int expectedModCount = modCount;
            
            //构造方法
    		Itr() {}
            
            // 判断集合里是否有下一个值
            public boolean hasNext() {
                return cursor != size();
            }
    		
            // 向下遍历
            public E next() {
                // 检查modCount是否被修改
                checkForComodification();
                try {
                    int i = cursor;
                    E next = get(i);
                    lastRet = i;
                    cursor = i + 1;
                    return next;
                } catch (IndexOutOfBoundsException e) {
                    checkForComodification();
                    throw new NoSuchElementException();
                }
            }
    		//移除上一次遍历的元素
            public void remove() {
                // 检验lastRet的值，也是不能连续删除的根本原因
                if (lastRet < 0)  throw new IllegalStateException();
                checkForComodification();
                try {
                    //调用父类的方法来删除元素
                    AbstractList.this.remove(lastRet);
                    /*
                    父类的方法如下：
                    public E remove(int index) {
                        
                        rangeCheck(index);
                        
                        // 检查下标索引
                        //private void rangeCheck(int index) {
                        //   if (index >= size)
                        //      throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
                        //}
    					
    					// 修改次数 +1
                        modCount++;
                        // 旧元素为被删除的元素
                        E oldValue = elementData(index);
    
                        int numMoved = size - index - 1;
                        if (numMoved > 0)
                            System.arraycopy(elementData, index+1, elementData, index,
                                             numMoved);
                        elementData[--size] = null; // clear to let GC do its work
    
                        return oldValue;
                    }
                    */
                    // 继续参数检验，检验后前移
                    if (lastRet < cursor)
                        cursor--;
                    // 因为删除一个元素后lastRet修改为-1了，所以不能连续删除
                    lastRet = -1;
                    // 同步修改次数
                    expectedModCount = modCount;
                } catch (IndexOutOfBoundsException e) {
                    throw new ConcurrentModificationException();
                }
            }
    		
            // 检查modCount是否被修改
            final void checkForComodification() {
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
            }
        }
    }
    
    //ArrayList源码分析(List特有的ListIterator迭代器)
    public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {
        
        //ListIterator迭代器继承了Iterator迭代器
        //public interface ListIterator<E> extends Iterator<E> {}
        
        //创建ListIterator迭代器的方法，返回的是ListIterator迭代器的实现类
        public ListIterator<E> listIterator() {
            return new ListItr(0);
        }
        //方法重载，带参数
        public ListIterator<E> listIterator(int index) {
            if (index < 0 || index > size)
                throw new IndexOutOfBoundsException("Index: "+index);
            return new ListItr(index);
        }
        
        //ArrayList的内部类，实现了ListIterator接口。
        private class ListItr extends Itr implements ListIterator<E> {
            //构造方法，传入的参数相当于给cursor赋值
            ListItr(int index) {
                super();
                cursor = index;
            }
    		//检查是否有前一个元素
            public boolean hasPrevious() {
                return cursor != 0;
            }
    		
            //返回下一个元素的索引
            public int nextIndex() {
                return cursor;
            }
    		
            //返回上一个元素的索引
            public int previousIndex() {
                return cursor - 1;
            }
    		
            //遍历到前一个元素
            @SuppressWarnings("unchecked")
            public E previous() {
                checkForComodification();
                int i = cursor - 1;
                if (i < 0)
                    throw new NoSuchElementException();
                Object[] elementData = ArrayList.this.elementData;
                if (i >= elementData.length)
                    throw new ConcurrentModificationException();
                //向前遍历一个元素，光标位置相同
                cursor = i;
                return (E) elementData[lastRet = i];
            }
    		
            //修改的是刚刚遍历过的位置，可以连续的修改, 进行遍历之前是不可修改的
            public void set(E e) {
                if (lastRet < 0)
                    throw new IllegalStateException();
                checkForComodification();
    
                try {
                    //调用原集合类的修改方法，并把需要修改的位置和新元素传递过去
                    ArrayList.this.set(lastRet, e);
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }
    
             // 添加的位置是光标所在的位置，因为lastRet置为-1，因此添加元素之后, 不可以删除，不可以修改，但是仍然可以继续添加
            public void add(E e) {
                checkForComodification();
                try {
                    int i = cursor;
                    ArrayList.this.add(i, e);
                    cursor = i + 1;
                    lastRet = -1;
                    expectedModCount = modCount;
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }
        }
    }
    
    /* 
        关于ArrayList源码，最后有一些个人的补充，就是ArrayList的sort排序函数
        public void sort(Comparator<? super E> c) {
            final int expectedModCount = modCount;
            Arrays.sort((E[]) elementData, 0, size, c);
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            modCount++;
        }
        需要传入一个Comparator比较器，本质上还是经过一番判断以后，调用了Arrays.sort函数，并且把比较器传入。
    */
   

2. Vector集合
   • 具有List集合的特点，底层是数据实现的，默认的初始容量为10，默认的扩容方式为每次扩容两倍，不同的是，Vector可以自己定义每次扩容的容量，允许重复元素，允许null元素，有序，有索引，因为底层普遍是synchronized修饰的方法，所以是线程安全的。
   • 因为Vector是线程安全的，原子操作太细小，速度太慢，所以不常用。
   • 同理，Stack继承了Vector类，同时继承了所有Vector的方法，但是不建议用Vector的方法，比如Vector的remove，因为这样就失去了原本栈的后入先出的作用和随意删除了栈中或栈底的数据。而且也只有一个空参的构造方法，不能设置初始容量，因为它线程安全，原子操作太细小，同样很少用到。

    //Vector源码分析
       	Vector<String> vector = new Vector<>();
          vector.add("zs");
      	Vector<String> vector1 = new Vector<>(10, 100);
      
      //对于以上代码，做出如下分析
      public class Vector<E>
          extends AbstractList<E>
          implements List<E>, RandomAccess, Cloneable, java.io.Serializable
      {
          //Vector底层维护的数组，用于存放元素
          protected Object[] elementData;
          
          //Vector的元素数量，相当于ArrayList的size参数
          protected int elementCount;
          
          //每次扩容的容量
          protected int capacityIncrement;
          
          //构造方法，链式调用
          public Vector() {
              this(10);
          }
          //可以看出，没有传入参数的话，默认容量是10
          public Vector(int initialCapacity) {
              this(initialCapacity, 0);
          }
      	//实际上所有重载的构造方法，最后调用的都是这个构造方法
      	public Vector(int initialCapacity, int capacityIncrement) {
              super();
              if (initialCapacity < 0)
                  throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
              this.elementData = new Object[initialCapacity];
              this.capacityIncrement = capacityIncrement;
          }
          
          //与ArrayList源码非常相似
          public synchronized void addElement(E obj) {
              modCount++;
              ensureCapacityHelper(elementCount + 1);
              elementData[elementCount++] = obj;
          }
          private void ensureCapacityHelper(int minCapacity) {
              // overflow-conscious code
              if (minCapacity - elementData.length > 0)
                  grow(minCapacity);
          }
          private void grow(int minCapacity) {
              // overflow-conscious code
              int oldCapacity = elementData.length;
              // 如果每次扩容的容量不是0，那就增加扩容的容量数，如果是0，那么就增加一倍
              int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
              if (newCapacity - minCapacity < 0)
                  newCapacity = minCapacity;
              if (newCapacity - MAX_ARRAY_SIZE > 0)
                  newCapacity = hugeCapacity(minCapacity);
              elementData = Arrays.copyOf(elementData, newCapacity);
          }
      }
   

3. LinkedList集合
   • java.util.LinkedList 集合数据存储的结构是双向链表结构。方便元素添加、删除的集合，默认初始容量为0，无扩容机制，允许重复元素，允许null元素，有序。因为没有做同步机制，所以线程不安全。开发中对一个集合元素的添加与删除经常涉及到首尾操作。
   • LinkedList是List的子类，List不仅是List接口的链表实现，同时也是Deque的链表实现，
     • LinkedList作为线性表的方法：
       • public void addFirst(E e) ：将指定元素插入此列表的开头。
       • public void addLast(E e) ：将指定元素添加到此列表的结尾。
       • public boolean contains(Object o) ：如果此列表包含指定元素，则返回 true。
       • public E element() ：获取但不移除此列表的头（第一个元素）。
       • public E getFirst() ：返回此列表的第一个元素。
       • public E getLast() ：返回此列表的最后一个元素。
       • public E remove() ：获取并移除此列表的头（第一个元素）。
       • public E removeFirst() ：移除并返回此列表的第一个元素。
       • public E removeLast() ：移除并返回此列表的最后一个元素。
     • LinkedList作为普通队列的方法
       • public boolean offer(E e)：将指定元素添加到此列表的末尾（最后一个元素）。
       • public E peek()：获取但不移除此列表的头（第一个元素）。
       • public E poll() ：获取并移除此列表的头（第一个元素）
     • LinkedList作为双端队列的方法
       • public boolean offerFirst(E e)：在此列表的开头插入指定的元素。
       • public boolean offerLast(E e) ：在此列表末尾插入指定的元素。
       • public E pollFirst()：获取并移除此列表的第一个元素；如果此列表为空，则返回 null。
       • public E pollLast()：获取并移除此列表的最后一个元素；如果此列表为空，则返回 null。
       • public E peekFirst()：获取但不移除此列表的第一个元素；如果此列表为空，则返回 null。
       • public E peekLast()：获取但不移除此列表的最后一个元素；如果此列表为空，则返回 null。
     • LinkedList作为栈的方法
       • public E pop()：从此列表所表示的堆栈处弹出一个元素。
       • public void push(E e)：将元素推入此列表所表示的堆栈。
     • LinkedList其它方法
       • public ListIterator descendingIterator()：返回以逆向顺序在此双端队列的元素上进行迭代的迭代器。
       • public ListIterator listIterator(int index)：返回此列表中的元素的列表迭代器（按适当顺序），从列表中指定位置开始。
       • public boolean removeFirstOccurrence(Object o)：从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表时）。
       • public boolean removeLastOccurrence(Object o)：从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表时）

   //LinkedList源码分析(没啥干货，就一个双向链表)
        public class LinkedList<E>
            extends AbstractSequentialList<E>
            implements List<E>, Deque<E>, Cloneable, java.io.Serializable
        {
            //链表大小
            transient int size = 0;
            //头结点
            transient Node<E> first;
            //尾结点
            transient Node<E> last;
            //构造方法
            public LinkedList() {}
            //把一个集合类改为链表
            public LinkedList(Collection<? extends E> c) {
                this();
                addAll(c);
            }
            //套娃
            public boolean addAll(Collection<? extends E> c) {
                return addAll(size, c);
            }
            //把所有数据添加为链表节点
            public boolean addAll(int index, Collection<? extends E> c) {
                checkPositionIndex(index);
        
                Object[] a = c.toArray();
                int numNew = a.length;
                if (numNew == 0)
                    return false;
        
                Node<E> pred, succ;
                if (index == size) {
                    succ = null;
                    pred = last;
                } else {
                    succ = node(index);
                    pred = succ.prev;
                }
        
                for (Object o : a) {
                    @SuppressWarnings("unchecked") E e = (E) o;
                    Node<E> newNode = new Node<>(pred, e, null);
                    if (pred == null)
                        first = newNode;
                    else
                        pred.next = newNode;
                    pred = newNode;
                }
        
                if (succ == null) {
                    last = pred;
                } else {
                    pred.next = succ;
                    succ.prev = pred;
                }
        
                size += numNew;
                modCount++;
                return true;
            }
            //内部类，链表的结点
            private static class Node<E> {
                E item;
                Node<E> next;
                Node<E> prev;
        
                Node(Node<E> prev, E element, Node<E> next) {
                    this.item = element;
                    this.next = next;
                    this.prev = prev;
                }
            }
            //头插法
            private void linkFirst(E e) {
                final Node<E> f = first;
                final Node<E> newNode = new Node<>(null, e, f);
                first = newNode;
                if (f == null)
                    last = newNode;
                else
                    f.prev = newNode;
                size++;
                modCount++;
            }
            //尾插法
            void linkLast(E e) {
                final Node<E> l = last;
                final Node<E> newNode = new Node<>(l, e, null);
                last = newNode;
                if (l == null)
                    first = newNode;
                else
                    l.next = newNode;
                size++;
                modCount++;
            }
        }
   

4. ListIterator迭代器(Iterator的子接口)
   • 位于List接口里，是Iterator的增强版
   • 获取ListIterator迭代器：
     • public ListIterator<E> listIterator()：返回此列表元素的列表迭代器（按适当顺序）。
     • public ListIterator<E> listIterator(int index)：返回列表中元素的列表迭代器（按适当顺序），从列表的指定位置开始。
   • ListIterator常用方法：
     • public void add(E e)：将指定的元素插入列表（可选操作）。
     • public boolean hasNext()：以正向遍历列表时，如果列表迭代器有多个元素，则返回 true。
     • public boolean hasPrevious()：如果以逆向遍历列表，列表迭代器有多个元素，则返回 true。
     • public int next()：返回列表中的下一个元素。
     • public int nextIndex()：返回对 next 的后续调用所返回元素的索引。
     • pubic E previous()：返回列表中的前一个元素。
     • pubic E previousIndex()：返回对 previous 的后续调用所返回元素的索引。
     • pubic void remove()：从列表中移除由 next 或 previous 返回的最后一个元素（可选操作）。
     • pubic void set(E e)：用指定元素替换 next 或 previous 返回的最后一个元素（可选操作）。

     ListIterator 和 Iterator 一样，在迭代过程中调用原集合的方法修改集合，会抛出并发修改异常。

1.4.Queue接口

1.4.1. Deque

• 特点：
  • queue的一个子接口, 它是双端队列子接口
  • 不仅可以作为双端队列使用, 还可以充当一个普通队列和栈
  • 不允许存储null
• 常用方法：
  • 双端队列：
    • public void add(E e)：将指定元素插入此双端队列所表示的队列（换句话说，此双端队列的尾部），如果可以直接这样做而不违反容量限制的话；如果成功，则返回 true，如果当前没有可用空间，则抛出 IllegalStateException。
    • public void addFirst(E e)：将指定元素插入此双端队列的开头（如果可以直接这样做而不违反容量限制）。
    • public void addLast(E e)：将指定元素插入此双端队列的末尾（如果可以直接这样做而不违反容量限制）。
    • public boolean offer(E e)：将指定元素插入此双端队列所表示的队列（换句话说，此双端队列的尾部），如果可以直接这样做而不违反容量限制的话；如果成功，则返回 true，如果当前没有可用的空间，则返回 false。
    • public boolean offerFirst(E e)：在不违反容量限制的情况下，将指定的元素插入此双端队列的开头
    • public boolean offerLast(E e)：在不违反容量限制的情况下，将指定的元素插入此双端队列的末尾
    • public void remove(E e)：获取并移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素）。
    • public void removeFirst(E e)：获取并移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。
    • public void removeLast(E e)：获取并移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。
    • public E poll(E e)： 获取并移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素）；如果此双端队列为空，则返回 null。
    • public E pollFirst(E e)：获取并移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。
    • public E pollLast(E e)：获取并移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。
    • public void getFirst(E e)：获取，但不移除此双端队列的第一个元素。
    • public void getLast(E e)：获取，但不移除此双端队列的最后一个元素。
    • public E peek(E e)：获取，但不移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素)，如果此双端队列为空，则返回 null。
    • public E peekFirst(E e)：获取，但不移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。
    • public E peekLast(E e)：获取，但不移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。
  • 堆栈：
    • public void push(E e)：将一个元素推入此双端队列所表示的堆栈（换句话说，此双端队列的头部），如果可以直接这样做而不违反容量限制的话；如果成功，则返回 true，如果当前没有可用空间，则抛出 IllegalStateException。
    • public E pop(E e)： 从此双端队列所表示的堆栈中弹出一个元素。
• ArrayDeque
  1. 它是双端队列的数组实现,
  2. 底层是个数组, 是一个循环存储的数组
  3. 默认初始容量(16), 扩容机制: 2倍
  4. 位序有序，允许重复元素, 不允许null(poll无元素可删除的时候, 返回值是null, 为了避免混淆)
  5. 线程不安全

      //ArrayDeque源码分析
        class ArrayDeque{
            
            transient Object[] elements;// ArrayDeque 的底层数组
            
            public ArrayDeque() {
                elements = new Object[16];
            }
            
             public boolean add(E e) {
                addLast(e);
                return true;
            }
            
            public void addLast(E e) {
                if (e == null) throw new NullPointerException();
                
                elements[tail] = e;
                if ( (tail = (tail + 1) & (elements.length - 1)) == head)
                    doubleCapacity();// 扩容方法
            }
            
            private void doubleCapacity() {
                assert head == tail;
                int p = head;
                int n = elements.length;
                int r = n - p; // number of elements to the right of p
                int newCapacity = n << 1;
                if (newCapacity < 0)
                    throw new IllegalStateException("Sorry, deque too big");
                Object[] a = new Object[newCapacity];
                System.arraycopy(elements, p, a, 0, r);
                System.arraycopy(elements, 0, a, r, p);
                elements = a;
                head = 0;
                tail = n;
            }
        }
  

• BlockingQueue
  1. queue接口的阻塞队列接口
  2. 阻塞队列: 限定容量队列, 如果队列满了, 阻塞添加线程, 如果队列空了阻塞删除线程
  3. 不允许null
  4. 阻塞方法:
     • public void put(E e): 将指定的元素插入此双端队列表示的队列中（即此双端队列的尾部），必要时将一直等待可用空间。
     • public E take(): 删除方法，阻塞
     • public boolean offer(E e，long timeout，TimeUnit unit)：将指定的元素插入此双端队列表示的队列中（即此双端队列的尾部），必要时将在指定的等待时间内一直等待可用空间。参数，添加元素，等待时长，时间单位
     • public E poll(long timeout,TimeUnit unit)：获取并移除此双端队列表示的队列的头部（即此双端队列的第一个元素），如有必要将在指定的等待时间内等待可用元素。

1.5.Set接口

1.5.1.关于Set

• java.util.Set 接口和 java.util.List 接口一样，同样继承自 Collection 接口，它与 Collection 接口中的方法基本一致，并没有对 Collection 接口进行功能上的扩充，只是比 Collection 接口更加严格了。与 List 接口不同的是， Set 接口中元素无序且没有索引，并且都会以某种规则保证存入的元素不出现key的重复。
• Set 集合有多个子类，常用的有 java.util.HashSet 、 java.util.LinkedHashSet ，Set集合取出元素的方式可以采用：迭代器、增强for。
• 基本特点
  1. 不允许出现重复:
     • key的重复
       • HashSet
       • LinkedHashSet
       • HasMap
       • LinkedHashMap
     • 自然顺序重复
       • TreeSet
       • TreeMap
  2. 有些子实现是可以存储null, 有些子实现不可以存储null
     • HashSet底层是HashMap，允许存储null(null散列到0的位置)
     • LinkedHashSet底层是LinkedHashMap，允许存储null
     • TreeSet底层是TreeMap，不允许存储null
  3. 有些子实现是有序的, 有些子实现是无序的
• 一个比较重要的方法
  • public boolean retainAll(Collection<?> c)：仅保留 set 中那些包含在指定 collection 中的元素（可选操作）。换句话说，移除此 set 中所有未包含在指定 collection 中的元素。如果指定的 collection 也是一个 set，则此操作会实际修改此 set，这样其值是两个 set 的一个交集。

1.5.2.HashSet集合

• java.util.HashSet 是 Set 接口的一个实现类，它所存储的元素是不可重复的，并且元素都是无序的(即存取顺序不一致)。 java.util.HashSet 底层的实现其实是一个 java.util.HashMap 支持。Map在下面介绍。
• HashSet 是根据对象的哈希值来确定元素在集合中的存储位置，具有良好的存取和查找性能。保证元素唯一性的方式依赖于：hashCode 与 equals 方法。
• 一些特点：
  1. 底层持有了一个HashMap对象 , 近似的认为(HashSet的底层机构是: 数组 +链表+ 红黑树)
  2. 初始长度, 扩容机制, 加载因子的特点都遵从于HashMap
  3. HashSet存储元素的特点, 完全上遵照HashMap的key的特点
  4. 线程不安全
• HashSet集合存储数据的结构(哈希表)
  • 在JDK1.8之前，哈希表底层采用数组+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，哈希表存储采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。简单的来说，哈希表是由数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的
  • JDK1.8引入红黑树大程度优化了HashSet的性能，保证HashSet集合元素的唯一，其实就是根据对象的hashCode和equals方法来决定的。如果我们往集合中存放自定义的对象，那么保证其唯一，就必须复写hashCode和equals方法建立属于当前对象的比较方式。

  HashSet存储自定义类型元素，可以是对象，同理对象的成员变量值不能相同。

• HashSet部分源码分析

public class HashSet<E>
            extends AbstractSet<E>
            implements Set<E>, Cloneable, java.io.Serializable
        {
            //底层维护的数组
            private transient HashMap<E,Object> map;
            
            //构造方法其实是调用了HashMap的构造方法
            public HashSet() {
                map = new HashMap<>();
            }
            
            //HashSet的独有的add方法
            public boolean add(E e) {
                //map添加成功的时候，返回的是null值，该add函数返回true，
                //如果不成功，新值覆盖旧值，返回的是已存在的旧值，旧值!=null，则该add函数返回false
                return map.put(e, PRESENT)==null;
            }
        }

1.5.3.LinkedHashSet集合

• HashSet保证元素唯一，可是元素存放进去是没有顺序的，我们要保证有序，可以使用LinkedHashSet。
• 在HashSet下面有一个子类 java.util.LinkedHashSet ，它是链表和哈希表组合的一个数据存储结构。
• 该集合输出元素的时候会按着添加的顺序输出，且没有重复值，因为Set接口没有索引，所以LinkedHashSet集合也不存在索引。
• 基本特点：
  1. 底层持有的是一个LinkedHashMap对象(LinkedHashMap又是基本复用了HashMap的底层结构, 只不过多加了一个双向链表)
  2. LinkedHashSet: 有序(底层的LinkedHashMap有一个双向链表)
  3. ListedHashSet : 他的基本特点遵从于LinkedHashMap的key的特点, 基本遵从于HashMapdkey的特点
  4. 有序, 允许null, 不允许重复
• LinkedHashSet部分源码分析

public class LinkedHashSet<E>
            extends HashSet<E>
            implements Set<E>, Cloneable, java.io.Serializable {
        
            //父类的构造方法
        	public LinkedHashSet() {
                super(16, .75f, true);
            }
        }
        
        public class HashSet<E>
            extends AbstractSet<E>
            implements Set<E>, Cloneable, java.io.Serializable
        {
            //底层维护的数组
            private transient HashMap<E,Object> map;
            
            //调用的是此方法
            HashSet(int initialCapacity, float loadFactor, boolean dummy) {
                map = new LinkedHashMap<>(initialCapacity, loadFactor);
            }
        }

1.5.4.TreeSet集合

• 基本特点：
  1. 底层持有了一个TreeMap对象(底层是 红黑树)
  2. 存储的元素, 要求实现自然顺序, 如果存储的元素没有实现自然顺序, 那么TreeSet要提供比较器
  3. 他不允许存储null(没办法比较大小)
  4. 大小有序
  5. 不能存储重复元素( 自然顺序比较结果 或者 比较器比较结果, 认为重复的数据)
  6. 如果已经存储到TreeSet (HashSet, LinkedhashSet)中的元素, 不要通过引用修改它
  7. 线程不安全

  基本复用了TreeMap

1.6.Collections工具类

• java.utils.Collections 是集合工具类，用来对集合进行操作，存在大量静态方法
• 部分静态方法：
  • public static boolean addAll(Collection c, T… elements)：往集合中添加一些元素。
  • public static void shuffle(List<?> list)：打乱集合顺序。
  • public static void sort(List list)：将集合中元素按照默认规则排序。
  • public static void sort(List list，Comparator<? super T> )：将集合中元素按照指定规则排序，下面介绍
• Comparator比较器
  • JAVA中对于排序提供了两种比较实现的方式，一种是比较死板的采用 java.lang.Comparable 接口去实现，一种是灵活的当需要做排序的时候在去选择的java.util.Comparator 接口完成。
  • Comparator这个接口，位于位于java.util包下，排序是comparator能实现的功能之一,该接口代表一个比较器
    • public int compare(String o1, String o2)：比较其两个参数的顺序。
    • 两个对象比较的结果有三种：大于，等于，小于。
      • 如果要按照升序排序，则 o1 小于 o2，返回（负数），相等返回0，o1 大于 o2 返回（正数）
      • 如果要按照降序排序，则 o1 小于 o2，返回（正数），相等返回0，o1 大于 o2 返回（负数）
• Comparable和Comparator两个接口的区别。
  • Comparable：强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序，类的compareTo方法被称为它的自然比较方法。只能在类中实现compareTo()一次，不能经常修改类的代码实现自己想要的排序。实现此接口的对象列表（和数组）可以通过Collections.sort（和Arrays.sort）进行自动排序，对象可以用作有序映射中的键或有序集合中的元素，无需指定比较器。
  • Comparator 强行对某个对象进行整体排序。可以将Comparator 传递给sort方法（如Collections.sort或Arrays.sort），从而允许在排序顺序上实现精确控制。还可以使用Comparator来控制某些数据结构（如有序set或有序映射）的顺序，或者为那些没有自然顺序的对象collection提供排序。
  • Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。
  • 如果待排序的列表中是数字或者字符，可以直接使用Collections.sort(list);当需要排序的集合或数组不是单纯的数字型时，需要自己定义排序规则，实现一个Comparator比较器。
• 一个关于排序的例子：

  //该类型必须实现Comparable接口才能调用 public static <T> void sort(List<T> list)方法
  public class Student implements Comparable<Student>{
      private String name;
      private int age;
      public Student() {}
      public Student(String name, int age) {
          this.name = name;
          this.age = age;
      }
      public String getName() {
          return name;
      }
      public void setName(String name) {
          this.name = name;
      }
      public int getAge() {
          return age;
      }
      public void setAge(int age) {
          this.age = age;
      }
      @Override
      public String toString() {
          return "Student{" +
          "name='" + name + '\'' +
          ", age=" + age +
          '}';
      }
      
      @Override
      public int compareTo(Student o) {
          return this.age - o.age;//升序
      }
  }
  
  
  public class Demo {
      public static void main(String[] args) {
          // 创建四个学生对象 存储到集合中
          ArrayList<Student> list = new ArrayList<Student>();
          list.add(new Student("rose",18));
          list.add(new Student("jack",16));
          list.add(new Student("abc",16));
          list.add(new Student("ace",17));
          list.add(new Student("mark",16));
          /*
          让学生 按照年龄排序 升序
          */
          Collections.sort(list);//要求：该list中的元素类型，如Student类型的对象，类声明中必须实现比较器Comparable接口
          for (Student student : list) {
              System.out.println(student);
          }
      }
  }    
  //输出结果：
  Student{name='jack', age=16}
  Student{name='abc', age=16}
  Student{name='mark', age=16}
  Student{name='ace', age=17}
  Student{name='rose', age=18}
  
  
  //如果在使用的时候，想要独立的定义规则去使用 可以采用Collections.sort(List list,Comparetor c)方式，自己定义规则
  
  Collections.sort(list, new Comparator<Student>() {//使用该方式不需要实现Comprarable接口
      @Override
      public int compare(Student o1, Student o2) {
          return o2.getAge() - o1.getAge();//以学生的年龄降序
      }
  });
  //输出结果：
  Student{name='rose', age=18}
  Student{name='ace', age=17}
  Student{name='jack', age=16}
  Student{name='abc', age=16}
  Student{name='mark', age=16}
  
  
  //如果想要规则更多一些，可以自己定义
  Collections.sort(list, new Comparator<Student>() {//使用该方式不需要实现Comprarable接口
      @Override
      public int compare(Student o1, Student o2) {
          // 年龄降序
          int result = o2.getAge()‐o1.getAge();//年龄降序
          if(result==0){//第一个规则判断完了 下一个规则 姓名的首字母 升序
              result = o1.getName().charAt(0)‐o2.getName().charAt(0);
          }
          return result;
      }
  });
  
  //输出结果：
  Student{name='rose', age=18}
  Student{name='ace', age=17}
  Student{name='abc', age=16}
  Student{name='jack', age=16}
  Student{name='mark', age=16}