java集合复习

集合 一、集合概念 1.含义：集合可以理解为一个容器，存储引用类型数据。 2.好处：1.动态容量：集合不受容器大小限制，可以随时添加或删除元素（随意扩容）。2.集合中可以存储多种不同类型数据。3.底层使用数据结构（存取效率高）。3.丰富操作：集合提供了大量操作元素的方法（例如 add(), remove(), contains(), size(), isEmpty() 等），以及各种遍历方式（迭代器、增强for循环、Stream API），使得数据的操作和管理更加高效。 3.集合与数组的区别 3.1元素类型 集合只能存储引用类型。当存储基本类型时，会自动进行装箱转换为对应的包装类。 数组既可以存储基本类型，也可以存储引用类型。但一个数组中不能混用基本类型和引用类型（即数组的元素类型是固定的）。 3.2元素个数（长度） 集合不固定：集合的容量可以根据需要动态地进行扩容或缩减，可以随时添加或删除元素。 数组固定：数组的长度一旦指定，在创建后就不能再更改。如果需要改变数组长度，只能创建新数组并复制旧数组的元素。

二、集合分类 集合框架可以分为两条大的支线：第一条支线 Collection，第二条支线 Map 1、第一条支线 Collection 接口 1.定义： Collection 是所有单列集合的根接口，用于存储单个元素。它定义了所有单列集合的通用行为，提供了添加、删除、清空、判断元素是否存在等基本操作。 2.分类 2.1.List 接口 元素有序（按插入顺序） 可以包含重复的元素 可以通过索引访问元素。 实现类包括 ArrayList、LinkedList 等。

2.2.Set接口 元素存取无序 不可以存放重复的元素（通过 hashCode() 和 equals() 方法判断） 不可以用下标对元素进行操作，和 List 有很多不同。 实现类包括 HashSet、LinkedHashSet、TreeSet 等。

2.3Queue 接口 遵循 先进先出（FIFO） 原则，常用于模拟队列数据结构。常见的实现类有PriorityQueue优先级队列

2、第二条支线 Map接口（双列集合） 1.定义 Map用于存储键值对（Key-Value Pair）。 键（Key）是唯一的，一个键最多映射一个值，用于快速查找对应的值。 值（Value）可以重复。 Map 接口的实现类包括 HashMap、LinkedHashMap、TreeMap、Hashtable等。 二、集合框架常用工具类 集合框架位于 java.util 包下，提供了两个常用的工具类： Collections：提供了一些对集合进行排序、二分查找、同步的静态方法。 Arrays：提供了一些对数组进行排序、打印、和 List 进行转换的静态方法。

三、 Collection 接口实现类 1、list实现类 1.ArrayList ArrayList 底层基于数组实现。特点是随机访问速度快，因为可以通过索引直接定位元素， 但增删元素（特别是中间位置）效率相对较低，因为可能会涉及到大量元素的移动。 ArrayList是非线程安全的。

1.1ArrayList的底层 ArrayList实现了List接口，是顺序容器，元素存取顺序相同，允许放入null元素，底层通过数组实现。 每个ArrayList都有一个容量(capacity)，表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。 数组是Object类型的数组，以便能够容纳任何类型的对象。

1.2ArrayList自动扩容 ArrayList 是基于数组的集合，数组的容量是在定义的时候确定的，如果数组满了，再插入，就会数组溢出。所以在插入时候，会先检查是否需要扩容，如果当前容量+1 超过数组长度，就会进行扩容。ArrayList 的扩容是创建一个1.5 倍的新数组，然后把原数组的值拷贝过去。 这种操作的代价是很高的，因此在实际使用时，应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。

2.LinkedList LinkedList底层基于双向链表实现。 特点是插入和删除元素元素（特别是首尾和中间位置）效率高，因为只需修改结点的前后指针，适合频繁的插入和删除操作。 缺点是查询效率较低，因为LinkedList 是链表结构，不支持随机访问元素，不能使用下标访问元素，需要使用迭代器从头或尾依次遍历链表元素。 LinkedList也是非线程安全的。

3.ArrayList与LinkedList的区别 ArrayList 底层是动态数组，查询快，增删慢； LinkedList 底层是双向链表，查询慢，增删快。 1.ArrayList 是由数组实现的，支持随机存取，也就是可以通过下标直接存取元素； 从尾部插入和删除元素会比较快捷，从中间插入和删除元素会比较低效，因为涉及到数组元素的复制与移动； 如果内部数组的容量不足时会自动扩容，因此当元素非常庞大的时候，效率会比较低。

2.LinkedList 是由双向链表实现的，不支持随机存取，只能从一端开始遍历，直到找到需要的元素后返回； 任意位置插入和删除元素都很方便，因为只需要改变前一个节点和后一个节点的引用即可，不像 ArrayList 那样需要复制和移动数组元素； 因为每个元素都存储了前一个和后一个节点的引用，所以相对来说，占用的内存空间会比 ArrayList 多一些。

3.频繁在中间操作时优先考虑 LinkedList（或更现代的 ArrayDeque 用于两端操作），但大多数场景下 ArrayList 仍是首选，因其内存连续、遍历极快。

2、set实现类 2.1HashSet 底层实现：HashSet 内部使用 HashMap存储元素，元素作为 HashMap 的键，值统一为一个静态的 Object 常量（PRESENT），不产生额外空间开销。特点是增删改查效率高， 2.迭代顺序：HashSet 不保证顺序。HashSet 的迭代顺序不是“每次随机”，而是由哈希值与当前桶数组长度经过计算后确定的。当元素数量变化导致扩容时，元素可能会重新哈希到不同的桶中，从而改变迭代顺序。使用 Iterator 遍历 HashSet 得到的结果是不确定的。 使用场景：实际开发中，HashSet 并不常用，比如，如果我们需要按照顺序存储一组元素，那么 ArrayList 和 LinkedList 更适合；如果我们需要存储键值对并根据键进行查找，那么 HashMap 更适合。 HashSet 主要用于去重，比如，我们需要统计一篇文章中有多少个不重复的单词，就可以使用 HashSet 来实现，HashSet 会自动去重，因为它是用 HashMap 实现的，HashMap 的键是唯一的（哈希值），相同键的值会覆盖掉原来的值，第二次 set.add("小明") 的时候就覆盖了第一次的 set.add("小明")。 当业务要求记录插入顺序时，应选用 LinkedHashSet；要求自然排序或自定义比较器排序时，选用 TreeSet；只有完全不在意顺序、只关心元素是否存在时，才使用 HashSet ，它也是日常开发中默认的 Set 实现。

2.2HashSet是如何实现的 HashSet是对HashMap的简单包装，对HashSet的函数调用都会转换成合适的HashMap方法

3.LinkedHashSet 底层实现：LinkedHashSet 是一种基于哈希表实现的 Set 接口，它继承自 HashSet，它的构造器创建的是 LinkedHashMap来存储元素，使用链表维护了元素插入与访问顺序。 性能：由于需要额外维护链表结构，LinkedHashSet 的增删改查操作效率略低于 HashSet（仍然都是 O(1) 均摊时间）。但在实际开发中，当需要保持插入顺序时，这种代价通常是可以接受的，且比 TreeSet 的 O(log n) 快得多。

4.treeSet 与 TreeMap 相似，TreeSet 是一种基于红黑树实现的有序集合，它实现了 SortedSet 接口，可以自动对集合中的元素进行排序。按照键的自然顺序或指定的比较器顺序进行排序。增删改查效率相对 HashSet 略低（对数时间复杂度）。HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。TreeSet也是非线程安全的。

5.Set 集合 总体上来说，Set 集合不是关注的重点，因为底层都是由 Map 实现的，Map 的键不允许重复、无序。

3、Queue实现类 1.ArrayDeque 基于数组实现的双端队列，为了满足可以同时在数组两端插入或删除元素的需求，数组必须是循环的，也就是说数组的任何一点都可以被看作是起点或者终点。

2.PriorityQueue 优先级队列，基于堆结构实现，可以用它来实现优先队列。元素根据其自然排序或自定义比较器进行排序，每次取出的是优先级最高的元素。要想有优先级，需要实现 Comparable 接口或者 Comparator 接口，通常使用lamdba表达式。 PriorityQueue是非线程安全的。

3.LinkedList 3.1LinkedList一般应该归在 List 下，只不过，它也实现了 Deque 接口，可以作为队列来使用。等于说，LinkedList 同时实现了 Stack、Queue、PriorityQueue 的所有功能。LinkedList 和 ArrayDeque 都是 Java 集合框架中的双向队列（deque），它们都支持在队列的两端进行元素的插入和删除操作。 LinkedList 和 ArrayDeque 在实现上的不同： 3.2底层实现方式不同 1.LinkedList 是基于链表实现的，而 ArrayDeque 是基于数组实现的。 2.随机访问的效率不同：由于底层实现方式的不同，LinkedList 对于随机访问的效率较低，时间复杂度为 O(n)，而 ArrayDeque 可以通过下标随机访问元素，时间复杂度为 O(1)。 3.迭代时效率不同：ArrayDeque 的数组在内存中连续，迭代时缓存命中率高，因此实际速度更快；而 LinkedList 的节点分散在堆内存中，迭代时缓存不友好，常数因子较大。但这不是渐进复杂度的差异，两者遍历整个集合的总时间复杂度都是 O(n)。此外，若通过索引 get(i) 随机访问，LinkedList 为 O(n)，ArrayDeque 为 O(1)。 4.内存占用不同：由于 LinkedList 是基于链表实现的，它在存储元素时需要额外的空间来存储链表节点，因此内存占用相对较高，而 ArrayDeque 是基于数组实现的，内存占用相对较低。 5.因此，在选择使用 LinkedList 还是 ArrayDeque 时，需要根据具体的业务场景和需求来选择。如果需要在双向队列的两端进行频繁的插入和删除操作，并且需要随机访问元素，可以考虑使用 ArrayDeque；如果需要在队列中间进行频繁的插入和删除操作，可以考虑使用 LinkedList。

四、Map接口实现类 1、HashMap 1.1定义与特性 1.HashMap 实现了 Map 接口，可以根据键快速地查找对应的值——通过哈希函数将键映射到哈希表中的一个索引位置，从而实现快速访问。是一个基于哈希表的键值对集合。 2.HashMap 允许一个 null 键（以及任意多个 null 值）。对于 null 键，HashMap 会将其哈希值强制设为 0。在内部数组中，该键值对会被放入索引为 0 的桶（bucket）中，也就是数组的第一个位置。 3.HashMapjava8在java7哈希表数组+链表的基础上添加了红黑树。优点是查询、增删效率高，可以根据键的哈希值快速查找到值，但有可能会发生哈希冲突。但元素（键值对）无序，不保留键值对的插入顺序。 4.可以使用迭代器或者 forEach 方法遍历 HashMap 中的键值对。 5.HashMap 有一个初始容量initial capacity和一个负载因子。初始容量是指哈希表的初始大小，哈希表创建时桶数组的长度默认为 16。capacity，当前哈希表容量。 负载因子决定哈希表何时扩容的阈值。默认 0.75 ，意味着当存储的键值对数量 size ≥ capacity * 0.75 时，数组容量翻倍（通常重新 hash）。

1.2JDK1.8 HashMap如何实现 JDK1.7 HashMap使用哈希表，查找时根据hash值能够快速定位到数组的具体下标，但是之后需要遍历链表才能找到对应的值，时间复杂度取决于链表的长度，为 O(n)。 JDK1.8 HashMap 的底层结构是数组 + 链表 + 红黑树。 链表长度 ≥ 8，但数组长度 < 64，执行扩容（resize）。这是因为短数组下哈希碰撞严重，优先通过扩容来重新分散节点。 当链表长度 ≥ 8 且数组长度 ≥ 64 时，链表转换为红黑树（树化），在这些位置进行查找，时间复杂度从 O(n) 降为 O(log n)。目的是为了减少长链表的遍历开销。

1.3HashMap 的扩容机制 1.哈希表数组默认初始容量 16，负载因子 0.75。 2.当元素个数超过容量 × 负载因子时，会扩容为原来的 2 倍，同时重新哈希所有元素。

1.4HashMap 为什么线程不安全？ConcurrentHashMap 的实现原理 1.HashMap 多线程下扩容会导致数据丢失、死循环。 2.ConcurrentHashMap 用分段锁（JDK1.7）和 3.CAS+synchronized（JDK1.8）保证线程安全。

2、LinkedHashMap 继承自 HashMap，底层基于哈希表和双向链表实现。 在 HashMap 的基础上，增加了一个双向链表来维护键值对的顺序，顺序为插入顺序或者启用最近最少使用(LRU)顺序。 LRU 缓存实现：利用访问顺序 + 重写 removeEldestEntry(Map.Entry eldest) 方法，可在插入后自动移除最久未访问的条目，常见于实现固定大小的缓存。 LinkedHashMap 可以看作是 HashMap + LinkedList 的合体，它使用了哈希表来存储数据，又用了双向链表来维持顺序。 LinkedHashMap是非线程安全的。

3、TreeMap  1.TreeMap 实现了 NavigableMap 接口（它扩展了 SortedMap），可以自动将键按照自然顺序（实现 Comparable）或构造时传入的 Comparator 顺序排序，并保证其元素的顺序。内部使用红黑树来实现键的排序和查找，增删改查均为 O(log n)，效率相对 HashMap O(1) 略低。 2.TreeMap是非线程安全的。如需并发访问，可使用 Collections.synchronizedSortedMap(new TreeMap(...))，或考虑 ConcurrentSkipListMap。 3.与 HashMap 的选择：需要保持键有序时选 TreeMap；只追求快速存取且不关心顺序时选 HashMap。

4、HashTable 是 Java 早期版本（JDK 1.0）遗留类，性能较低。 Hashtable的键和值都不能为 null 。 Hashtable和 HashMap 类似，但Hashtable 是线程安全的，通过对整个对象加锁synchronized实现，同一时刻只允许一个线程操作，并发性能差。 建议使用 ConcurrentHashMap 替代，ConcurrentHashMap 效率更高，JDK 1.7 使用分段锁，JDK 1.8 引入红黑树 + CAS + synchronized，允许真正的并发写入（不同段或不同桶的锁分离）。