Java 集合

①、集合相关思维导图

Java集合.png

②、集合

1、Collection接口

image.png
Collection_1.png
AbstractCollection.png

Collection.png
Collection.png

A.List集合

List 集合存储的是有序的数据集合，其数据结构特点是：读取快，修改慢，适合于读取多、写入修改少的场景。

1、list集合的类继承结构如下：

image.png

2、List列表实现

image.png
ArrayList 类是很常用的 List 实现，其底层是用数组实现的。其读取元素的时间复杂度是 O(1)，修改写入元素的时间复杂度是 O(N)。

3、List列表安全实现

Vector 类也是很常用的 List 实现，其数据结构与 ArrayList 非常类似。但其与 ArrayList 的一个最大的不同是：Vector 是线程安全的，而 ArrayList 则不是线程安全的。
Stack 类则是在 Vector 的基础上，又实现了一个双向队列。所以其除了是线程安全的之外，其还是一个先进后出的 List 实现。
List 集合最为关键的几个实现类是：

  • ArrayList：列表集合经典实现。
  • Vector：列表集合经典实现，线程安全，与 ArrayList 对应。
  • Stack：栈结构的经典实现，先进后出的数据结构。继承了 Vector，线程安全。

  • LinkedList：链表结构的经典实现。

    4、List链表实现

    LinkedList 是一个经典的链表实现。LinkedList 继承了 AbstractSequentialList 抽象类。AbstractSequentialList 抽象类从字面上理解是抽象连续列表。这里的重点是 sequential 这个词，表示其数据结构是连续的（链表）。

    B.Set集合

    Set 集合中存储的元素是不重复的，但是其存储顺序是无序的。

    1、Set集合的类继承结构图

    image.png

    2、Set集合的实现

    Set 集合的实现可以分为两大块，一块是 Set 集合的有序实现（红色部分），另一块是 Set 集合的哈希实现（蓝色部分）
    image.png

    3、有序实现(TreeSet)

    SortedSet 接口继承了 Set 接口，TreeSet 实现了 SortedSet。
    Set 集合中的元素是无序的，而 SortedSet 接口则是定义了有序 Set 集合的接口。而 TreeSet 则是 SortedSet 的具体实现。

    4、哈希实现(HashSet、LinkedHashSet)

    HashSet 是 Set 接口的经典哈希实现。但 Set 集合中的元素是无序的，为了维护 Set 集合的插入顺序，出现了 LinkedHashSet。LinkedHashSet 是在 HashSet 的基础上用链表维护元素的插入顺序。
    Set 集合的所有实现：

  • TreeSet：Set 集合的有序实现。

  • HashSet：Set 集合的哈希实现。
  • LinkedHashSet：Set 集合的哈希实现，维护了元素插入顺序。

    C.Queue集合

    队列是一个特殊的线性表，其数据结构特点是先进先出。

    1、Queue类结构体系如下

    image.png

    2、Queue的具体实现

    image.png
    Queue 接口继承了 Collection 接口。Queue 接口在拥有基本集合操作的基础上，定义了队列这种数据结构的基本操作。offer、poll 等方法都是队列独有的操作。
    AbstractQueue 是对 Queue 接口的抽象实现。针对队列这种数据结构，其添加、删除元素的动作都不一样。在 AbstractQueue 抽象类里将队列的基本操作都实现了一遍。例如 AbstractQueue 中的 add 方法就和 AbstractList 中的 add 方法有着不同的实现。

    3、有序实现

    PriorityQueue 是 AbstractQueue 抽象类的具体实现。
    PriorityQueue 表示优先级队列，其按照队列元素的大小进行重新排序。当调用 peek() 或 pool() 方法取出队列中头部的元素时，并不是取出最先进入队列的元素，而是取出队列的最小元素。

    4、双向实现

  1. Deque（double ended queue）是双向队列的意思，它能在头部或尾部进行元素操作。
  2. LinkedList 是一个链表，但它还是一个双向队列。因此 LinkedList 具有 List 和 Queue 的双重特性。ArrayDeque 是一个双向循环队列，其底层是用数组实现。

    5、Queue 体系常见实现类：

  • PriorityQueue：优先级队列
  • LinkedList：双向队列实现
  • ArrayDeque：双向循环队列实现

    D.Map集合

    Map 集合与 List、Set、Queue 有较大不同，其实类似于 key/value 的数据结构。
    image.png

Map.png
Map.png

1、Map集合的实现

  • 首先，Map 接口是最顶层的接口。

与 List、Set、Queue 类似，Map 接口定义的是哈希表数据结构的操作。例如常用的 put、get、keySet 等。

  • 接着，有 AbstractMap 抽象类。

和 List 等类似，AbstractMap 是 Map 接口的抽象实现。如下图所示，Map 集合的整个类结构可以分为红、黄、棕三块。
image.png

2、哈希实现

  • AbstractMap 有具体的实现类 HashMap。

HashMap 是 AbstractMap 基于哈希算法的具体实现。

  • LinkedHashMap 和 WeakedHashMap 继承了 HashMap。

LinkedHashMap 是 HashMap 的进一步实现，其用链表保存了插入 HashMap 中的元素顺序。WeakedHashMap 是 HashMap 的进一步实现，与 HashMap不同的是：WeakedHashMap 中的引用是弱引用，如果太久没用，则会被自动回收。

3、有序实现

  • SortedMap 接口继承了 Map 接口。

与 Set 一样，Map 中的元素是没有顺序的，SortedMap 就是有序 Map 的接口定义。

  • NavigableMap 继承了 SortedMap 接口。

NavigableMap 接口定义了一些查找逻辑，方便后续实现。

  • TreeMap 则是 NavigableMap 接口的具体实现。

其实 TreeMap 是基于红黑树的 Map 实现。

4、Map集合的所有实现类

  • HashMap：Map 集合的经典哈希实现。
  • LinkedHashMap：在 HashMap的基础上，增加了对插入元素的链表维护。
  • WeakedHashMap：在 HashMap的基础上，使强引用变为弱引用。

  • TreeMap：Map 集合的有序实现。

    E.工具类

    工具类(Iterator 迭代器、Enumeration 枚举类、Arrays 和 Collections)

    1.Iterator迭代器

    Iterator 迭代器是一个用来遍历并选择序列中的对象。Java 的 Iterator 只能单向移动。可以看到在 ArrayList、WeakHashMap 等集合类都实现了该接口，从而实现不同类型集合的遍历。

    2.ListIterator迭代器

    ListIterator 继承了 Iterator 接口，所以其有更强大的功能，即它能够实现双向移动。但从其名字也可以看出，其只能适用于 List 集合的遍历。

    3.Enumeration枚举类

    Enumeration 枚举类是 JDK 1.0引入的接口。作用和Iterator一样，也是遍历集合。但是Enumeration的功能要比Iterator少。Enumeration只能在Hashtable, Vector, Stack中使用。这种传统接口已被迭代器取代，虽然 Enumeration 还未被遗弃，但在代码中已经被很少使用了。

    4.Arrays

    Java.util.Arrays类能方便地操作数组，它提供的所有方法都是静态的。

    5.Collections

    Collections 是一个包含各种有关集合操作的静态多态方法的工具类。

    2、同步容器

    Java中同步容器主要包括2类

  • 1、Vector、Stack、HashTable

  • 2、Collections类中提供的静态工厂方法创建的类

    同步容器存在的问题

    同步容器直接保证单个线程的操作安全性，但是无法保证复合操作的线程安全，遇到这种情况时，必须要通过主动加锁的方式来实现。而且，除此之外，同步容易由于对其所有方法都加了锁，这就导致多个线程访问同一个容器的时候，只能进行顺序访问，即使是不同的操作，也要排队，如get和add要排队执行。这就大大的降低了容器的并发能力。

    3、并发容器

    java.util.concurent包下，提供了大量支持高效并发的访问的集合类，称之为并发容器
    image.png
    image.png
    同步容器的复合操作的问题，一般在Map中发生的比较多，所以在ConcurrentHashMap中增加了对常用复合操作的支持，比如putIfAbsent()、replace()，这2个操作都是原子操作，可以保证线程安全。
    另外，并发包中的CopyOnWriteArrayList和CopyOnWriteArraySet是Copy-On-Write的两种实现。
    Copy-On-Write容器即写时复制的容器。通俗的理解是当往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。
    CopyOnWriteArrayList中add/remove等写方法是需要加锁的，而读方法是没有加锁的。
    这样做的好处是可以对CopyOnWrite容器进行并发的读，当然，这里读到的数据可能不是最新的。因为写时复制的思想是通过延时更新的策略来实现数据的最终一致性的，并非强一致性。
    但是，作为代替Vector的CopyOnWriteArrayList并没有解决同步容器的复合操作的线程安全性问题。