Java基础之集合框架思维导图

集合框架是Java中用于存储和操作数据的一组接口和类的集合。

概述

基于数组实现

原理

子主题

动态扩容：ArrayList内部维护了一个数组，当元素个数超出数组容量时，会自动进行扩容操作，以保证能容纳更多的元素。快速访问：由于ArrayList是基于数组实现的，因此可以通过索引快速访问到任意位置的元素。元素有序：ArrayList中的元素按照插入的顺序排列，可以根据索引进行插入、删除和修改操作。

特性

常用方法

频繁的插入、删除操作时性能较差，因为在插入和删除时需要移动其他元素。如果需要频繁的插入、删除操作，建议使用LinkedList类。

注意

ArrayList类

基于双向链表实现

快速插入和删除：由于LinkedList基于链表实现，插入和删除操作只需要修改节点的引用，不需要移动其他元素，因此在频繁的插入和删除操作时性能较好。随机访问较慢：由于LinkedList没有像ArrayList那样基于数组实现，因此要访问特定位置的元素需要从链表的头部或尾部开始遍历，直到找到目标位置，因此随机访问的性能较差。支持队列和栈的操作：LinkedList实现了Deque接口，可以用作队列或栈来进行元素的添加和删除操作。

由于LinkedList是基于链表实现的，因此它在插入和删除操作上具有较好的性能，但在随机访问操作上较慢。

LinkedList类

List接口

基于哈希表实现

哈希表存储：HashSet内部使用哈希表来存储元素，每个元素被存储在哈希表的一个bucket中。元素唯一性：HashSet中的元素是不重复的，即不能包含重复元素。它是通过哈希表的键来实现元素的唯一性的。无序性：HashSet中的元素没有特定的顺序，即不保证元素的存储和插入顺序一致。

添加元素：add(element)删除元素：remove(element)判断是否包含某元素：contains(element)获取大小：size()判断是否为空：isEmpty()

HashSet中的元素需要具有正确的hashCode()和equals()方法的实现，以便正确地判断元素的唯一性。当使用自定义对象作为HashSet中的元素时，需要重写这两个方法。HashSet的插入、删除和判断是否包含某元素的性能都是非常好的，但是它不保证元素的顺序，如果需要有序的存储和遍历操作，可以考虑使用LinkedHashSet。

HashSet类

基于哈希表和双向链表实现

哈希表存储：LinkedHashSet内部使用哈希表来存储元素，保证元素的唯一性和快速的插入、删除、查找操作。双向链表维护插入顺序：除了哈希表外，LinkedHashSet还使用一个双向链表来维护元素的插入顺序。因此，它可以保持元素的插入顺序，即按照元素插入的先后顺序进行遍历。

LinkedHashSet的性能与HashSet类似，其插入、删除和判断是否包含某元素的性能都是非常好的。额外的双向链表维护插入顺序并不会影响这些操作的性能。然而，与HashSet相比，LinkedHashSet在遍历操作上略慢一些，因为需要遍历链表来保持插入顺序。但是，LinkedHashSet仍然是一个非常有效的集合类，适用于需要保持插入顺序的场景。

LinkedHashSet类

基于红黑树（一种自平衡的二叉搜索树）实现

有序存储：TreeSet中的元素是有序的，默认按照元素的自然顺序进行排序，或者可以通过传入Comparator来指定元素的排序方式。元素唯一性：TreeSet中的元素是不重复的，即不能包含重复元素。它是通过比较元素的顺序来实现元素的唯一性。操作效率：由于使用红黑树实现，TreeSet的插入、删除和查找操作的平均时间复杂度为O(log n)，具有较高的操作效率。

添加元素：add(element)删除元素：remove(element)获取元素：first()、last()获取小于等于/大于等于某元素的最大/最小元素：floor(element)、ceiling(element)判断是否包含某元素：contains(element)获取大小：size()判断是否为空：isEmpty()

TreeSet类

Set接口

基于堆实现的

堆数据结构：PriorityQueue内部使用堆来存储元素，通常使用二叉堆。二叉堆是一种完全二叉树，它的每个节点都满足父节点大于等于子节点（最大堆）或父节点小于等于子节点（最小堆）的条件。元素优先级排序：PriorityQueue中的元素按照优先级进行排序，具有最高优先级的元素在队首。元素的优先级可以通过实现Comparable接口或传入Comparator来指定。自动调整：当元素插入或删除时，PriorityQueue会自动调整堆结构，以保持堆的性质。

入队操作：add(element)、offer(element)出队操作：remove()、poll()获取队首元素：element()、peek()获取队列大小：size()判断队列是否为空：isEmpty()

需要注意的是，PriorityQueue中的元素需要具有可比较性，即实现了Comparable接口或通过传入Comparator来进行比较。当使用自定义对象作为PriorityQueue中的元素时，需要确保该对象实现了Comparable接口或提供了Comparator进行比较。PriorityQueue允许插入、删除和获取最高优先级元素的操作具有较高的效率，插入元素的时间复杂度为O(log n)，删除和获取最高优先级元素的时间复杂度为O(1)。它适用于需要按照优先级排序的场景，比如任务调度、事件处理等。

PriorityQueue类

基于动态数组实现的

动态数组：ArrayDeque内部使用动态数组（循环数组）来存储元素。循环数组是一种通过使用固定大小的数组，并通过头尾指针来循环利用数组空间的数据结构。双端队列：ArrayDeque既可以在队尾进行元素的入队操作，也可以在队首进行元素的出队操作，因此可以作为双端队列使用。自动扩缩容：当元素数量超过动态数组的容量时，ArrayDeque会自动扩容，当元素数量较少时，它会自动缩小容量，以提供更好的空间利用率。

入队操作：add(element)、offer(element)出队操作：remove()、poll()获取队首元素：element()、peek()入栈操作（在队首添加元素）：push(element)出栈操作（移除并返回队首元素）：pop()获取队列大小：size()判断队列是否为空：isEmpty()

需要注意的是，ArrayDeque并不是线程安全的，如果在多线程环境下使用，需要采取外部同步措施。与LinkedList相比，ArrayDeque在大多数操作上具有更高的效率。它的插入、删除和获取操作的时间复杂度都为O(1)，并且由于使用动态数组实现，相对于LinkedList，ArrayDeque在内存上的利用率更高。因此，当需要高效地进行队列和栈操作或双端队列操作时，可以选择使用ArrayDeque。

ArrayDeque

Queue接口

Collection接口

哈希表：HashMap内部使用哈希表来存储键值对，哈希表是一种根据键的哈希值进行存储和查找的数据结构。通过计算键的哈希值，可以快速定位到对应的存储位置，以提供快速的数据访问。键的唯一性：HashMap中的键是唯一的，不可以重复。当插入具有相同键的键值对时，新的值会覆盖旧的值。键值对无序：HashMap中的键值对是无序的，即不保证存储和遍历的顺序与插入顺序一致。效率优化：HashMap在插入、获取和删除操作上都具有很高的效率，并且具有扩容机制，在容量不足时会自动扩容以提供更好的性能。

HashMap适用于存储需要根据键快速查找值的场景，并且插入、获取和删除操作具有较高的效率。然而，由于哈希表的特性，HashMap的键值对是无序的，如果需要有序存储的特性，可以考虑使用LinkedHashMap。在多线程环境下使用HashMap时，需要采取外部同步措施，或者使用线程安全的ConcurrentHashMap类。

HashMap类

哈希表：LinkedHashMap内部使用哈希表来存储键值对，通过计算键的哈希值，可以快速定位到对应的存储位置，以提供快速访问。双向链表：LinkedHashMap内部使用双向链表来维护键值对的顺序，保持键值对的插入顺序或者最近访问顺序，从而实现有序存储。顺序模式：LinkedHashMap提供两种顺序模式，一种是按照插入顺序排序（插入顺序模式），另一种是按照最近访问顺序排序（访问顺序模式）。效率优化：LinkedHashMap在继承HashMap的基础上，通过维护双向链表来保持有序存储，因此在插入、获取和删除操作上与HashMap相比没有明显的性能损失。

通过设置LinkedHashMap的构造方法中的accessOrder参数为true可以启用访问顺序模式，即按照最近访问顺序排序。默认情况下，LinkedHashMap是按照插入顺序排序的。LinkedHashMap适用于需要保持有序存储的场景，可以根据插入顺序或者访问顺序进行排序和遍历。相比于HashMap，LinkedHashMap会稍微增加一些内存消耗和插入操作的开销，但通常对于大多数场景来说，这个开销是可以忽略的。

LinkedHashMap类

基于红黑树实现

红黑树：TreeMap内部使用红黑树作为底层数据结构，红黑树是一种自平衡的二叉搜索树。通过保持树的平衡状态，可以提供高效的插入、删除和查找操作。键的有序性：红黑树的特性使得TreeMap中的键是有序的。根据键的比较结果，构建起一颗有序树，从而可以实现根据键的自然顺序或者自定义的比较器进行排序。效率优化：TreeMap在插入、获取和删除操作上具有较高的效率，红黑树的自平衡特性保证了树的高度维持在较低的水平上。

由于TreeMap是按照键的有序性来排列的，因此在使用TreeMap时，可以通过键的自然顺序或者自定义的比较器进行排序。TreeMap适用于需要以键的有序性进行操作的场景，可以方便地获取最小键、最大键、小于等于给定键的最大键、大于等于给定键的最小键等操作。但需要注意的是，由于维护红黑树的特性，相比于HashMap和LinkedHashMap，TreeMap在插入、删除等操作上会稍微慢一些。

TreeMap类

Map接口

接口

添加元素

删除元素

查找元素

遍历集合

判断集合是否为空

获取集合大小

可重复性

有序性

线程安全性

需要存储大量数据

需要高效地增删改查数据

需要保持数据的有序性

需要去除重复数据

适用场景

集合框架是Java中用于存储和操作数据的一组接口和类的集合，提供了各种实现类来满足不同的需求。它具有可重复性、有序性和线程安全性等特性，适用于存储大量数据、高效地增删改查数据、保持数据有序性和去除重复数据的场景。

总结

集合框架

Java基础