各种集合类的时间复杂度分析：你真的了解它们吗？
开篇语
哈喽，各位小伙伴们，你们好呀，我是喵手。运营社区：C站/掘金/腾讯云/阿里云/华为云/51CTO；欢迎大家常来逛逛
今天我要给大家分享一些自己日常学习到的一些知识点，并以文字的形式跟大家一起交流，互相学习，一个人虽可以走的更快，但一群人可以走的更远。
我是一名后端开发爱好者，工作日常接触到最多的就是Java语言啦，所以我都尽量抽业余时间把自己所学到所会的，通过文章的形式进行输出，希望以这种方式帮助到更多的初学者或者想入门的小伙伴们，同时也能对自己的技术进行沉淀，加以复盘，查缺补漏。
小伙伴们在批阅的过程中，如果觉得文章不错，欢迎点赞、收藏、关注哦。三连即是对作者我写作道路上最好的鼓励与支持！
前言
在学习 Java 集合框架时，理解各类集合的 时间复杂度 是每个开发者都必须掌握的基础。无论是 List、Set、Map 还是其他集合类，每种集合类在不同操作下的时间复杂度可能差异巨大。如果你不清楚这些差异，就很容易在高并发或大量数据的场景中出现性能瓶颈，最终影响系统的效率。
今天，我们将对 Java 集合框架中常用的几种集合类的时间复杂度进行详细分析，帮助你理解不同集合类型在不同操作下的性能表现。准备好了吗？一起来看看这些集合类的“速度”如何吧！
集合类概述
在 Java 中，最常用的集合类大致可以分为以下几种：
- List：有序集合，允许重复元素。常见实现类包括
ArrayList和LinkedList。 - Set：无序集合，不允许重复元素。常见实现类包括
HashSet、LinkedHashSet和TreeSet。 - Map：键值对集合，不允许重复键。常见实现类包括
HashMap、LinkedHashMap和TreeMap。
接下来，我们将对这些常见集合类进行 时间复杂度 的分析，帮助你快速了解它们在不同操作下的性能差异。
1. ArrayList（实现了 List 接口）
ArrayList 是最常用的动态数组实现，支持快速随机访问元素，但对于插入和删除操作，尤其是在数组中间进行的操作，它的性能不如链表。
常见操作及时间复杂度：
| 操作 | 时间复杂度 |
|---|---|
| get(index) | O(1) |
| set(index, element) | O(1) |
| add(element) | O(1)（摊销时间） |
| insert(index, element) | O(n) |
| remove(index) | O(n) |
| contains(element) | O(n) |
| size() | O(1) |
解析：
- get(index) 和 set(index, element) 操作的时间复杂度是 O(1)，因为数组是连续的内存块，可以直接通过索引访问。
- add(element) 操作的时间复杂度是 O(1)，但如果数组已满，需要扩容，此时扩容操作的时间复杂度为 O(n)（摊销时间为 O(1)）。
- insert(index, element) 和 remove(index) 操作会导致数组元素的移动，所以时间复杂度是 O(n)，其中 n 是
ArrayList中的元素个数。
2. LinkedList（实现了 List 接口）
LinkedList 是基于双向链表实现的，插入和删除操作非常高效，但访问元素时的效率较低，因为必须从头节点或尾节点开始遍历。
常见操作及时间复杂度：
| 操作 | 时间复杂度 |
|---|---|
| get(index) | O(n) |
| set(index, element) | O(n) |
| add(element) | O(1) |
| insert(index, element) | O(n) |
| remove(index) | O(n) |
| contains(element) | O(n) |
| size() | O(1) |
解析：
- get(index) 和 set(index, element) 的时间复杂度是 O(n)，因为必须从头或尾遍历链表找到指定位置。
- add(element) 操作的时间复杂度是 O(1)，只需修改头或尾节点的指针即可。
- insert(index, element) 和 remove(index) 需要找到指定位置并修改指针，时间复杂度是 O(n)。
3. HashSet（实现了 Set 接口）
HashSet 是基于哈希表实现的集合，不允许元素重复，查找、插入和删除操作的时间复杂度通常很高效，但依赖于哈希函数的质量。
常见操作及时间复杂度：
| 操作 | 时间复杂度 |
|---|---|
| add(element) | O(1)（摊销时间） |
| remove(element) | O(1)（摊销时间） |
| contains(element) | O(1)（摊销时间） |
| size() | O(1) |
解析：
- add(element)、remove(element) 和 contains(element) 操作的时间复杂度是 O(1)（摊销时间），因为哈希表可以通过哈希值直接定位到元素的位置。
- 如果哈希冲突较多，性能可能会下降，但在理想情况下（负载因子合理、哈希函数分布均匀），时间复杂度为 O(1)。
4. LinkedHashSet（实现了 Set 接口）
LinkedHashSet 是 HashSet 的子类，它通过链表维护元素的插入顺序。因此，LinkedHashSet 在保证哈希集合性能的同时，能够保持元素的插入顺序。
常见操作及时间复杂度：
| 操作 | 时间复杂度 |
|---|---|
| add(element) | O(1)（摊销时间） |
| remove(element) | O(1)（摊销时间） |
| contains(element) | O(1)（摊销时间） |
| size() | O(1) |
解析：
LinkedHashSet 的时间复杂度与 HashSet 类似，主要在于它通过链表保持元素的插入顺序。因此，它的性能与 HashSet 相当，都是 O(1)（摊销时间）。不过，相比于 HashSet，它在实现上多了一个额外的链表结构，用于维护顺序。
5. TreeSet（实现了 Set 接口）
TreeSet 是基于 红黑树 实现的，它能够保持元素的有序性。在插入和删除元素时，它会自动调整树结构，保证其有序性。
常见操作及时间复杂度：
| 操作 | 时间复杂度 |
|---|---|
| add(element) | O(log n) |
| remove(element) | O(log n) |
| contains(element) | O(log n) |
| size() | O(1) |
解析：
- add(element)、remove(element) 和 contains(element) 操作的时间复杂度是 O(log n)，因为
TreeSet依赖于红黑树，它保证了操作的对数时间复杂度。 - 由于红黑树的平衡特性，它的性能在需要有序集合时十分优秀。
6. HashMap（实现了 Map 接口）
HashMap 是基于哈希表实现的映射，键值对的查找、插入和删除操作通常是 O(1) 时间复杂度，前提是哈希表的负载因子合理，哈希冲突较少。
常见操作及时间复杂度：
| 操作 | 时间复杂度 |
|---|---|
| get(key) | O(1)（摊销时间） |
| put(key, value) | O(1)（摊销时间） |
| remove(key) | O(1)（摊销时间） |
| containsKey(key) | O(1)（摊销时间） |
| size() | O(1) |
解析：
- get(key)、put(key, value) 和 remove(key) 操作的时间复杂度是 O(1)（摊销时间），因为哈希表通过哈希值直接定位到键的位置。
- 哈希冲突会影响性能，但在理想情况下，时间复杂度为 O(1)。
7. TreeMap（实现了 Map 接口）
TreeMap 是基于 红黑树 实现的映射，能够保持键的有序性。它在查找、插入和删除时，自动保持元素的有序排列。
常见操作及时间复杂度：
| 操作 | 时间复杂度 |
|---|---|
| get(key) | O(log n) |
| put(key, value) | O(log n) |
| remove(key) | O(log n) |
| containsKey(key) | O(log n) |
| size() | O(1) |
解析：
与 TreeSet 类似，TreeMap 的操作都需要维护红黑树的平衡，因此时间复杂度为 O(log n)。
总结
在选择合适的集合类时，了解它们的时间复杂度至关重要。根据操作类型和使用场景的不同，选择最适合的集合类能够大大提高程序的性能。以下是几种常用集合类的总结：
- ArrayList：适合频繁的随机访问，但插入和删除操作较慢（特别是在中间位置）。
- LinkedList：适合频繁的插入和删除，但随机访问性能较差。
- HashSet：适合不要求有序、频繁的查找、插入和删除。
- TreeSet：适合需要有序元素的场景，查找、插入和删除操作的时间复杂度是 O(log n)。
- HashMap：适合频繁的查找、插入和删除操作，前提是哈希表的负载因子合理。
- TreeMap：适合需要有序的映射，支持按键排序。
希望通过本文的时间复杂度分析，你能对 Java 中各种集合类的性能有更深入的理解，帮助你在实际开发中做出更合理的选择。
… …
文末
好啦，以上就是我这期的全部内容，如果有任何疑问，欢迎下方留言哦，咱们下期见。
… …
学习不分先后，知识不分多少；事无巨细，当以虚心求教；三人行，必有我师焉！！！
wished for you successed ！！！
⭐️若喜欢我，就请关注我叭。
⭐️若对您有用，就请点赞叭。
⭐️若有疑问，就请评论留言告诉我叭。
版权声明：本文由作者原创，转载请注明出处，谢谢支持！
- 点赞
- 收藏
- 关注作者
评论（0）