1、Java-容器-简介

  1. 1、容器-概念：
  2.     1-1、Java使用容器来解决：程序总是在运行时才能确定要创建对象的数量，甚至是对象的类型。 需要在任意时刻位置创建任意数量的对象。
  3.     1-2、[!!!]在Java当中，有一个类专门用来存放其它类的对象，这个类就叫做容器，它就是将若干性质相同或相近的类对象组合在一起而形成的一个整体，
  4.     1-3、[!!!]容器，即使可以容纳其他Java对象的对象，Java Collections Framework(JCF)为Java开发者提供了通用的容器，其始于JDK 1.2。
  5.     1-4、[!!!]Java容器里只能放对象，对于基本类型(int, long, float, double等)，需要将其包装成对象类型后(Integer, Long, Float, Double等)才能放到容器里。很多时候拆包装和解包装能够自动完成。
  6.     1-5、容器也称集合类，基本的类型是 List,Set,Queue，Map,但由于Java 类库中使用了 Collection 关键字作接口。 所以一般用容器来称呼这些集合类。
  7.     1-6、[!!!]容器主要包括Collection和Map两种，Collection 存储着对象的集合，而 Map 存储着键值对(两个对象)的映射表。
  8.     1-7、java容器工具的jar包是java.util.*。
  10. 2、容器与数组的关系
  11.     2-1、之所以需要容器：
  12.         2-1-1、数组的长度难以扩充。
  13.         2-1-2、数组中数据的类型必须相同。
  14.     2-2、容器与数组的区别与联系：
  15.         2-2-1、容器不是数组，不能通过下标的方式访问容器中的元素。
  16.         2-2-2、数组的所有功能通过Arraylist容器都可以实现，只是实现的方式不同。
  17.         2-2-3、如果非要将容器当做一个数组来使用，通过toArraylist方法返回的就是一个数组。
  18.         2-2-4、[!!!]数组基本类型和引用类型都可以，但集合只能是引用类型(???)
  19.             2-2-4-1、集合只能是引用类型解释：指的是集合中存放的可都是对象的引用，实际内容都在堆上面或者方法区里面，但是基本数据类型是在栈上分配空间的。随时就被收回的。但是通过自动包装类就可以把基本类型转为对象类型，存放引用就解决了这个问题。想把基本数据类型存入集合中，直接存就可以了，系统会自动将其装箱成封装类,然后加入集合当中。
  20.         2-2-5、数组只能存储同一种类型，但集合可以存储不同类型的数据【存放相同类型的元素】。
  22. 3、Java 容器，主要可以划分为5个部分：
  23.     3-1、List,
  24.     3-2、Set，
  25.     3-3、Map,
  26.     3-4、Iterator，
  27.     3-5、Enumeration枚举类、
  28.     3-6、Arrays、
  29.     3-7、Collections。

1-1、Java-容器-知识体系结构-示意图

image.png

1-2、Java-容器-总纲-介绍

  1. 1、Set ：
  2.     1-1、概念：
  3.         1-1-1、存储的是无序的，不重复的数据。
  4.         1-1-2、Set检索效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
  5.         1-1-3、Set不能根据索引获取元素.(HashSet是HashMap实现，需要对元素进行hash找到位置再存储，不存在直接索引获取的方式)
  6.         1-1-3、Set判断两个对象相同不是使用==运算符，而是根据equals方法。
  7.     1-2、分类：
  8.         1-2-1、TreeSet 基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。 
  9.             1-2-1-1、根据构造方法不同，分为自然排序（无参构造）和比较器排序（有参构造），自然排序要求元素必须实现Compareable接口，并重写里面的compareTo()方法，元素通过比较返回的int值来判断排序序列，返回0说明两个对象相同，不需要存储；比较器排需要在TreeSet初始化是时候传入一个实现Comparator接口的比较器对象，或者采用匿名内部类的方式new一个Comparator对象，重写里面的compare()方法；
  10.         1-2-2、HashSet 基于哈希表实现，底层数据结构是数组，默认初始化容量16，加载因子0.75，支持快速查找，但不支持有序性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。 
  11.         1-2-3、LinkedHashSet 具有 HashSet 的查找效率，底层数据结构采用链表(元素顺序性)+哈希表(元素唯一性)，线程不安全，内部使用双向链表维护元素的插入顺序。
  13. 2、List：
  14.     2-1、概念：
  15.         2-1-1、存储的是有序的，可以重复的元素。
  16.         2-1-2、List和数组类似，可以动态增长，根据实际存储的数据的长度自动增长List的长度。查找元素效率高，插入删除效率低，因为会引起其他元素位置改变。
  17.         2-1-3、List可通过索引直接操作元素。
  18.        2-2、分类：
  19.         2-2-1、ArrayList 基于动态数组实现，查询快，增删慢，线程不安全，支持随机访问。 
  20.         2-2-2、Vector 和 ArrayList 类似，底层数据结构是数组，查询快，增删慢，但它是线程安全的。 
  21.         2-2-3、LinkedList 基于双向链表实现，只能顺序访问，查询慢，增删快，线程不安全，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。
  23. 3、Queue
  24.     3-1、LinkedList 可以用它来实现双向队列。
  25.     3-2、PriorityQueue 基于堆结构实现，可以用它来实现优先队列。
  27. 4、Map  
  28.     4-1、TreeMap 基于红黑树实现，实现SortMap接口，排序方式：自然排序、定制排序。 
  29.     4-2、HashMap 基于哈希表实现，没有同步，线程不安全。 
  30.     4-3、HashTable 和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程可以同时写入 HashTable 并且不会导致数据不一致。它是遗留类，不应该去使用它。
  31.     4-4、ConcurrentHashMap 来支持线程安全，并且 ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。 
  32.     4-5、LinkedHashMap 使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用(LRU)顺序。
  33.     4-6、Properies 
  34.         4-6-1、该类主要用于读取Java的配置文件，不同的编程语言有自己所支持的配置文件，配置文件中很多变量是经常改变的，为了方便用户的配置，能让用户够脱离程序本身去修改相关的变量设置。
  35.         4-6-1、继承了Hashtable类
  36.             public class Properties extends Hashtable<Object,Object> {}

1-2-1、Java-容器-介绍-List结构图

Java-集合(Collection) - 图2

1-2-2、Java-容器-介绍-Set结构图

Java-集合(Collection) - 图3

1-2-3、Java-容器-介绍-Queue结构图

Java-集合(Collection) - 图4

1-2-4、Java-容器-介绍-Map结构图

Java-集合(Collection) - 图5

1-3、Java-容器-介绍-ArrayList

  1. 1、ArrayList是List接口的可变数组的实现，存放相同类型的元素数据，实现了所有可选列表操作，允许null在内的所有元素。
  2. 2、每个ArrayList实例都有一个容量，该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。
  3. 3、随着向ArrayList中不断添加元素，其容量也自动增长。自动扩容会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造ArrayList时指定其容量。
  4. 4、ArrayList的实现，它实现List接口、底层使用数组保存所有元素。其操作基本上是对数组的操作。

1-3-1、介绍-ArrayList-继承体系

  1. 1、ArrayList实现List、RandomAccess、Cloneable、Serializable等接口。    
  2.     1-1.Arraylist实现List，提供了基础的添加、删除、遍历等操作。  
  3.     1-2.ArrayList实现RandomAccess，提供随机访问的能力。  
  4.     1-3.ArrayList实现Cloneable，可以被克隆。  
  5.     1-4.ArrayList实现Serializable，可以被序列化(将对象转换成以字节序列的形式来表示，以便于持久化和传输。 实现方法：实现序列化接口。 然后用的时候拿出来进行反序列化即可又变成java对象。)。
  6. 2、
  7.     public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
  8.     }

1-3-2、介绍-ArrayList-继承体系-示意图

Java-集合(Collection) - 图6

1-3-3、介绍-ArrayList-源码分析

容器(集合)-ArrayList-源码分析

1-4、Java-容器-介绍-LinkedList

  1. 1、LinkedList同时实现了List接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列(Queue)，同时又可以看作一个栈(Stack)。
  2. 2、当你需要使用栈或者队列时，可以考虑使用LinkedList
  3. 3、关于栈或队列，现在的首选是ArrayDeque，它有着比LinkedList(当作栈或队列使用时)有着更好的性能。
  4. 4、LinkedList的实现方式决定了所有跟下标相关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间。为追求效率LinkedList没有实现同步(synchronized)，如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装。
  5. 5、LinkedList底层通过双向链表实现。
  6.     5-1、链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的地址。
  7.     5-2、链表可分为单向链表和双向链表。一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接。一个双向链表有三个整数值: 数值、向后的节点链接、向前的节点链接。

1-4-1、介绍-LinkedList-继承体系

  1. 1、LinkedList-继承体系
  2.     1-1、LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
  3.     1-2、LinkedList 实现 List 接口，能对它进行队列操作。
  4.     1-3、LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
  5.     1-4、LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
  6.     1-5、LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
  7.     1-6、LinkedList 是非同步的，非线程安全。
  8. 2、
  9.     public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
  10.     }

1-4-2、介绍-LinkedList-继承体系-示意图

image.png

1-4-3、介绍-LinkedList-源码分析

容器(集合)-LinkedList-源码分析

1-4-4、介绍-LinkedList-小结

  1. 1、LinkedList 特点：
  2.     1-1、双向链表实现
  3.     1-2、元素时有序的，输出顺序与输入顺序一致
  4.     1-3、允许元素为 null
  5.     1-4、所有指定位置的操作都是从头开始遍历进行的
  6.     1-5、和 ArrayList 一样，不是同步容器
  8. 2、并发访问注意事项：
  9.     2-1、linkedList 和 ArrayList 一样，不是同步容器。所以需要外部做同步操作，或者直接用 Collections.synchronizedList 方法包一下，最好在创建时就报一下：
  10.         List list = Collections.synchronizedList(new LinkedList(...));
  12. 3、LinkedList 的迭代器都是 fail-fast 的: 如果在并发环境下，其他线程使用迭代器以外的方法修改数据，会导致 ConcurrentModificationException.
  14. 4、对LinkedList遍历，使用foreach方式，而不是for循环方式。

1-4、Java-容器-介绍-Stack/Queue

  1. 1、Stack/Queue-概述：
  2.     1-1、Java里有一个叫做Stack的类，却没有叫做Queue的类(它是个接口名字)。
  3.     1-2、当需要使用栈时，Java已不推荐使用Stack，而是推荐使用更高效的ArrayDeque，次选是LinkedList
  4.     1-3、Queue接口继承自Collection接口，除了最基本的Collection的方法之外，它还支持额外的insertion(插入), extraction(获取)和inspection(删除)操作。这里有两组格式，共6个方法，一组是抛出异常的实现；另外一组是返回值的实现(没有则返回null)。
  5.         1-3-1、方法为：
  6.                 Insert    add(e)    offer(e)
  7.                 Remove    remove()    poll()
  8.                 Examine    element()    peek()
  10. 2、Deque-概述：
  11.     2-1、Deque是"double ended queue", 表示双向的队列，Deque 继承自 Queue接口，除了支持Queue的方法之外，还支持insert, remove和examine操作。
  12.     2-2、由于Deque是双向的，所以可以对队列的头和尾都进行操作，它同时也支持两组格式(共12个方法)，一组是抛出异常的实现；另外一组是返回值的实现(没有则返回null)。
  13.     2-3、当把Deque当做FIFO的队列(先进先出)来使用时，元素是从deque的尾部添加，从头部进行删除的。deque的部分方法是和queue是等同的：
  14.         Queue        Deque
  15.         add(e)         addLast(e) 
  16.         offer(e)     offerLast(e) 
  17.         remove()     removeFirst() 
  18.         poll()         pollFirst() 
  19.         element()     getFirst() 
  20.         peek()         peekFirst()
  21.     2-4、当把Deque当做LIFO的栈(先进后出)来使用时，deque的部分方法是和queue是等同的：
  22.         Queue            Deque                说明
  23.         add(e)             addLast(e)             向队尾插入元素，失败则抛出异常 
  24.         offer(e)         offerLast(e)         向队尾插入元素，失败则返回false             
  25.         remove()         removeFirst()         获取并删除队首元素，失败则抛出异常 
  26.         poll()             pollFirst()         获取并删除队首元素，失败则返回null 
  27.         element()         getFirst()             获取但不删除队首元素，失败则抛出异常 
  28.         peek()             peekFirst()         获取但不删除队首元素，失败则返回null
  30. 3、Deque月Stack对应接口方法：
  31.         Stack            Deque                    说明
  32.         push(e)         addFirst(e)          向栈顶插入元素，失败则抛出异常 
  33.         无                offerFirst(e)         向栈顶插入元素，失败则返回false 
  34.         pop()             removeFirst()          获取并删除栈顶元素，失败则抛出异常 
  35.         无                pollFirst()             获取并删除栈顶元素，失败则返回null 
  36.         peek()             peekFirst()          获取但不删除栈顶元素，失败则抛出异常 
  37.         无                peekFirst()             获取但不删除栈顶元素，失败则返回null

1-4-1、Java-容器-介绍-ArrayDeque

  1. 1、ArrayDeque-概述
  2.     1-1、LinkedList是Deque的两个通用实现，由于官方更推荐使用AarryDeque用作栈和队列。
  3.     1-2、ArrayDeque是Deque接口的一个实现，使用了可变数组(循环数组(circular array)，也就是说数组的任何一点都可能被看作起点或者终点。)，所以没有容量上的限制。
  4.         1-2-1、head指向首端第一个有效元素，tail指向尾端第一个可以插入元素的空位。因为是循环数组，所以head不一定总等于0，tail也不一定总是比head大。
  5.     1-3、ArrayDeque是Deque的实现类，可以作为栈来使用，效率高于Stack；也可以作为队列来使用，效率高于LinkedList。
  6.     1-4、ArrayDeque是线程不安全的，在没有外部同步的情况下，不能再多线程环境下使用。
  7.     1-5、[!!!]ArrayDeque不支持null值。

1-4-2、Java-容器-介绍-ArrayDeque-继承体系

  1. 1、ArrayDeque-继承体系：
  2.     1-1、ArrayDeque 实现 Deque 接口，即能将ArrayDeque当作双端队列使用。
  3.     1-2、ArrayDeque 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
  4.     1-3、ArrayDeque 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
  5.     1-4、ArrayDeque 是非同步的，非线程安全。
  6.     public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable{
  7.     }

1-4-3、Java-容器-介绍-ArrayDeque-继承体系-示意图

image.png

1-4-4、Java-容器-介绍-ArrayDeque-实现示意图

  1. 1、head指向首端第一个有效元素，tail指向尾端第一个可以插入元素的空位。因为是循环数组，所以head不一定总等于0，tail也不一定总是比head大。
  2. 2、通过二进制方式判断数组是否已满(tail = (tail + 1) & (elements.length - 1)) == head
  3. 3、操作插入和移除时，有Throws exception 和 return Special value 俩种情况。

Java-集合(Collection) - 图9

1-4-5、Java-容器-介绍-ArrayDeque-源码分析

容器(集合)-ArrayDeque-源码分析

1-4-6、Java-容器-介绍-ArrayDeque-小结

  1. 1、ArrayDeque 既可实现普通队列 FIFO 先进先出，也可实现栈的先进后出功能，因为ArrayDeque实现了双端的操作。
  2.     1-1、先进先出
  3.         addFirst() 方法 配合pollLast() 方法
  4.         addLast() 方法 配合 pollFirst()方法
  5.     1-2、先进后出（栈）
  6.         addFirst() 方法配合 pollFirst()方法
  7.         addLast()方法配合pollLast()方法
  9. 2、双端队列与双重队列？
  10.     双端队列（Deque）是指队列的两端都可以进出元素的队列，里面存储的是实实在在的元素。
  11.     双重队列（Dual Queue）是指一种队列有两种用途，里面的节点分为数据节点和非数据节点，它是LinkedTransferQueue使用的数据结构。
  13. 3、Throws exception 和 return Special value(也就是null值)

1-5、Java-容器-介绍-PriorityQueue

  1. 1、优先队列-概述
  2.     1-1、优先队列不是按照普通对象先进先出原FIFO则进行数据操作，其中的元素有优先级属性，优先级高的元素先出队。
  3.     1-2、PriorityQueue队列，也是一种优先队列，是基于最小堆原理实现。
  4.     1-3、一般使用堆数据结构实现，堆一般使用数组存储。
  5.     1-4、优先队列不允许空值，而且不支持non-comparable（不可比较）的对象，比如用户自定义的类。优先队列要求使用Java Comparable和Comparator接口给对象排序，并且在排序时会按照优先级处理其中的元素。
  6.     1-5、优先队列的头是基于自然排序或者Comparator排序的最小元素。如果有多个对象拥有同样的排序，那么就可能随机地取其中任意一个。当我们获取队列时，返回队列的头对象。
  7.     1-6、优先队列的大小是不受限制的，但在创建时可以指定初始大小。当我们向优先队列增加元素的时候，队列大小会自动增加。
  9. 2、最小堆-概述
  10.     2-1、 最小堆是一个完全二叉树，所谓的完全二叉树是一种没有空节点的二叉树。
  11.     2-2、最小堆特性：
  12.         2-2-1、根节点必定是最小节点，子女节点一定大于其父节点。
  13.         2-2-2、叶子节点数量=度为2的节点个数+1
  14.                 节点总个数为n，叶子节点个数为：n0，度为1的节点个数为：n1，度为2的节点个数为n2，边的个数为b
  15.                     n=n0+n1+n2
  16.                     b=n-1; b=n1+2*n2 代入二叉树==>  b=n0+n1+n2-1
  17.                                                ==>    n0+n1+n2-1=n1+2*n2
  18.                                                ==>  n0=n2+1
  19.     2-3、在 PriorityQueue队列中，基于数组保存了完全二叉树。所以在已知任意一个节点在数组中的位置，就可以通过一个公式推算出其左子树和右子树的下标。已知节点下标是i，那么他的左子树是2*i+1，右子树是2*i+2。

1-5-1、Java-容器-介绍-PriorityQueue

  1. 1、PriorityQueue-概述
  2.     1-1、Java1.5引入，基于优先堆的一个无界队列，这个优先队列中的元素可以默认自然排序或者通过提供的Comparator（比较器）在队列实例化的时排序。
  3.     1-2、PriorityQueue是非线程安全的，所以Java提供了PriorityBlockingQueue（实现BlockingQueue接口）用于Java多线程环境。
  4.     1-3、PriorityQueue实现了Queue接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值）。
  5.     1-4、可以通过数组来作为PriorityQueue的底层实现。
  6.     1-5、PriorityQueue是一个小顶堆，不是有序的，只有堆顶存储着最小的元素；
  7.     1-6、入队就是堆的插入元素的实现；出队就是堆的删除元素的实现。

1-5-2、Java-PriorityQueue-通过数组表示小顶堆实现

  1. 1、父子节点的编号之间关系：
  2.     leftNo = parentNo*2+1 
  3.     rightNo = parentNo*2+2 
  4.     parentNo = (nodeNo-1)/2
  5. 2、某个节点的父节点以及子节点的下标都可以计算出来，也就是为什么可以直接用数组来存储堆的原因。

1-5-3、Java-PriorityQueue-通过数组表示小顶堆实现-示意图

Java-集合(Collection) - 图10

1-5-4、Java-容器-介绍-PriorityQueue-继承体系

  1. 1、PriorityQueue-继承体系：
  2.     1-1、PriorityQueue 实现 AbstractQueue 接口，即能将PriorityQueue当作双端队列使用。
  3.     1-2、PriorityQueue 实现java.io.Serializable接口，这意味着PriorityQueue支持序列化，能通过序列化去传输。
  4.     1-3、PriorityQueue 是非同步的，非线程安全。
  5.     1-4、源码Demo：
  6.         public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable {
  7.         }
  8.         public abstract class AbstractQueue<E> extends AbstractCollection<E> implements Queue<E> {
  9.         }

1-5-5、Java-容器-介绍-PriorityQueue-继承体系-示意图

image.png

1-5-6、Java-容器-介绍-PriorityQueue-源码分析

容器(集合)-PriorityQueue-源码分析

1-5-7、Java-容器-介绍-PriorityQueue-小结

  1. 1、PriorityQueue-小结：
  2.     1-1、PriorityQueue队列不适合进场出队入队的频繁操作，但是他的优先级特性非常适合一些对顺序有要求的数据处理场合。
  3.     1-2、 PriorityQueue本质上就是堆排序里面建的最小堆。最小堆满足的一个基本性质是堆顶端的元素是所有元素里最小的那个。
  4.     1-3、对堆的操作和调整主要包含三个方面，增加新的元素，删除顶端元素和建堆时保证堆性质的操作。