环境和版本

  • Mac M1
  • IDEA 2021
  • Zulu Open JDK

简介：集合框架，将会是一个非常好玩的地方，可以任意分析各种源码的实现。里面会用到很多的概率论知识、
高等数学知识等。
目标：精通各种集合框架的底层实现，可以手写各种集合框架。
下一个阶段的目标：现在只是讲解Java集合框架基础的部分，也就是常用的，但是还有一些和多线程相关的集合框架，需要在JUC的时候进行单独学习。

整体继承体系概览

  • 顶级接口是啥、一个集合从哪些接口实现的

image.png

  • 来个更详细的

image.png

容器：容纳其他对象的对象

  • 降低编程难度
  • 提高程序性能
  • 提高API间的互操作性
  • 降低学习难度
  • 降低设计和实现相关API的难度
  • 增加程序的重用性

    List

    List 的特点是存取有序，可以存放重复的元素，可以用下标对元素进行操作

ArrayList

  • ArrayList 是由数组实现的，支持随机存取，也就是可以通过下标直接存取元素；
  • 从尾部插入和删除元素会比较快捷，从中间插入和删除元素会比较低效，因为涉及到数组元素的复制和移动；

  • 如果内部数组的容易不足时会自动扩容，因此当元素非常庞大的时候，效率会比较低。

    LinkedList

  • LinkedList 是由双向链表实现的，不支持随机存取，只能从一端开始遍历，直到找到需要的元素后返回；

  • 任意位置插入和删除元素都很方便，因为只需要改变前一个节点和后一个节点的引用即可，不像 ArrayList 那样需要复制和移动数组元素；

  • 因为每个元素都存储了前一个和后一个节点的引用，所以相对来说，占用的内存空间会比 ArrayList 多一些。

    Vector 和 Stack

  • List 的实现类还有一个 Vector，是一个元老级的类，比 ArrayList 出现得更早。ArrayList 和 Vector 非常相似，只不过 Vector 是线程安全的，像 get、set、add 这些方法都加了 synchronized 关键字，就导致执行执行效率会比较低，所以现在已经很少用了。

  • 更好的选择是并发包下的 CopyOnWriteArrayList。
  • Stack 是 Vector 的一个子类，本质上也是由动态数组实现的，只不过还实现了先进后出的功能（在 get、set、add 方法的基础上追加了 pop、peek 等方法），所以叫栈。
  • 不过，由于 Stack 执行效率比较低（方法上同样加了 synchronized 关键字），就被双端队列 ArrayDeque 取代了。

    Set

    Set 的特点是存取无序，不可以存放重复的元素，不可以用下标对元素进行操作，和 List 有很多不同

HashSet

  • HashSet 其实是由 HashMap 实现的，只不过值由一个固定的 Object 对象填充，而键用于操作。

    LinkedHashSet

  • LinkedHashSet 继承自 HashSet

    TreeSet

  • TreeSet 是由 TreeMap 实现的，只不过同样操作的键位

    SortedSet

  • 有序Set

    Queue

    Queue，也就是队列，通常遵循先进先出（FIFO）的原则，新元素插入到队列的尾部，访问元素返回队列的头部。

ArrayDeque

  • ArrayDeque 是一个基于数组实现的双端队列，为了满足可以同时在数组两端插入或删除元素的需求，数组必须是循环的，也就是说数组的任何一点都可以被看作是起点或者终点。
  • 这是一个包含了 4 个元素的双端队列，和一个包含了 5 个元素的双端队列。

image.png

  • head 指向队首的第一个有效的元素，tail 指向队尾第一个可以插入元素的空位，因为是循环数组，所以 head 不一定从是从 0 开始，tail 也不一定总是比 head 大。

    LinkedList

  • LinkedList 一般都归在 List 下，只不过，它也实现了 Deque 接口，可以作为队列来使用。等于说，LinkedList 同时实现了 Stack、Queue、PriorityQueue 的所有功能。

    PriorityQueue

  • PriorityQueue 是一种优先级队列，它的出队顺序与元素的优先级有关，执行 remove 或者 poll 方法，返回的总是优先级最高的元素。

  • 要想有优先级，元素就需要实现 Comparable 接口或者 Comparator 接口。

    Map

    Map 保存的是键值对，键要求保持唯一性，值可以重复。

HashMap

  • HashMap 实现了 Map 接口，根据键的 HashCode 值来存储数据，具有很快的访问速度，最多允许一个 null 键。

    LinkedHashMap

  • 大多数情况下，只要不涉及到线程安全的问题，有需要键值对的时候就会使用 HashMap，但 HashMap 有一个问题，就是 HashMap 是无序的。在某些场景下，我们需要一个有序的 Map。

  • 于是 LinkedHashMap 就闪亮登场了。LinkedHashMap 是 HashMap 的子类，内部使用链表来记录插入/访问元素的顺序。

  • LinkedHashMap 可以看作是 HashMap + LinkedList 的合体，它使用了 哈希表来存储数据，又用了双向链表来维持顺序。

    TreeMap

  • HashMap 是无序的，所以遍历的时候元素的顺序也是不可测的。TreeMap 是有序的，它在内部会对键进行排序，所以遍历的时候就可以得到预期的顺序。

  • 为了保证顺序，TreeMap 的键必须要实现 Comparable 接口或者 Comparator 接口。

集合框架总结
TODO