目录
一、集合介绍
二、List
三、Map
HashMap的数据结构
如何理解红黑树
四、set
一、集合介绍
在Java中,集合是一种用于存储对象的数据结构,它提供了一种更加灵活和强大的方式来处理和操作数据。Java集合框架提供了一系列接口和类,用于表示和操作不同类型的集合。
图片来源:《面渣逆袭手册》V1.1
List :存储的元素有序,可重复。(相当于是个篮子,临时给你放数据用的 )Set :存储的元素无序,不可重复。(去重的List,放进去的东西如果一样,后面的会把前面的覆盖掉,得到的是个无重复值的列表 )Map 是另外的接口,是键值对映射结构的集合。(Map是个键值对,可以实现用a来搜b的作用,比如用用户的id搜用户的名称之类的操作 )
以下是Java中常见的集合:
-
List(列表):
ArrayList
:基于数组实现的动态数组,支持快速随机访问元素,但插入和删除操作效率较低。LinkedList
:基于链表实现的双向列表,插入和删除操作效率较高,但访问元素的效率较低。Vector
:与ArrayList
类似,但是线程安全的,不推荐在新代码中使用。Stack
:基于Vector
实现的栈,通常用于实现后进先出(LIFO)的数据结构。
-
Set(集合):
HashSet
:基于哈希表实现的集合,不保证元素的顺序。TreeSet
:基于红黑树实现的有序集合,可以按照自然顺序或者自定义顺序对元素进行排序。LinkedHashSet
:具有预期插入顺序的集合,内部使用链表维护元素的顺序。
-
Map(映射):
HashMap
:基于哈希表实现的映射,键值对无序。TreeMap
:基于红黑树实现的有序映射,键值对按照键的自然顺序或者自定义顺序进行排序。LinkedHashMap
:具有预期插入顺序的映射,内部使用链表维护键值对的顺序。
-
Queue(队列):
PriorityQueue
:基于堆实现的优先级队列,按照元素的优先级顺序进行排序。
此外,Java集合框架还包括一些接口和抽象类,如 Collection
、Map
、Iterator
等,它们提供了一组通用的操作和方法,可以方便地对集合进行操作和遍历。
二、List
在 Java 中,ArrayList
和 LinkedList
是两种常见的集合实现,它们有以下主要区别:
- 内存分配:
ArrayList
:使用连续的内存空间来存储元素。LinkedList
:使用链式存储结构,内存空间不连续,它们在空间占用上都有一些额外的消耗。- ArrayList 是预先定义好的数组,可能会有空的内存空间,存在一定空间浪费LinkedList 每个节点,需要存储前驱和后继,所以每个节点会占用更多的空间
- 随机访问:
ArrayList
:基于数组,所以它可以根据下标查找,支持快速的随机访问,通过索引可以快速获取元素。LinkedList
:基于链表,所以它没法根据序号直接获取元素,在随机访问方面效率较低。
- 插入和删除:
- 多数情况下,ArrayList更利于查找,LinkedList更利于增删。
- ArrayList 基于数组实现, get(int index) 可以直接通过数组下标获取,时间复杂度是 O(1) ; LinkedList 基于链表实现, get(int index) 需要遍历链表,时间复杂度是O(n) ;当然, get(E element) 这种查找,两种集合都需要遍历,时间复杂度都是O(n) 。
- ArrayList增删如果是数组末尾的位置,直接插入或者删除就可以了,但是如果插入中间的位置,就需要把插入位置后的元素都向前或者向后移动,甚至还有可能触发扩容;双向链表的插入和删除只需要改变前驱节点、后继节点和插入节点的指向就行了,不需要移动元素。
-
-
- 图片来源:《面渣逆袭手册》V1.1
- 内存占用:
ArrayList
:需要预先分配一定的内存空间,如果元素数量超过容量,需要进行扩容。基于数组的集合,数组的容量是在定义的时候确定的,如果数组满了,再插入,就会数组溢出。所以在插入时候,会先检查是否需要扩容,如果当前容量+1 超过数组长度,就会进行扩容。- ArrayList的扩容是创建一个1.5倍的新数组,然后把原数组的值拷贝过去。
LinkedList
:不需要预先分配固定的内存空间。
- 遍历方式:
ArrayList
:可以通过索引或迭代器进行遍历。LinkedList
:还可以通过指针依次访问元素。
示例代码如下:-
import java.util.ArrayList; import java.util.LinkedList; import java.util.List;public class CollectionExample {public static void main(String[] args) {// 使用 ArrayListList<String> arrayList = new ArrayList<>();arrayList.add("Apple");arrayList.add("Banana");arrayList.add("Orange");System.out.println("使用 ArrayList 遍历:");for (String item : arrayList) {System.out.println(item);}// 使用 LinkedListList<String> linkedList = new LinkedList<>();linkedList.add("Apple");linkedList.add("Banana");linkedList.add("Orange");System.out.println("\n 使用 LinkedList 遍历:");for (String item : linkedList) {System.out.println(item);}} }
三、Map
在 Java 中,常见的 Map
实现有 HashMap
和 TreeMap
。
HashMap
基于哈希表实现,它的数据结构如下:
- 存储键值对。
- 通过哈希函数计算键的哈希值,以确定元素在哈希表中的存储位置。
TreeMap
基于红黑树实现,它的数据结构如下:
- 按照键的自然顺序进行排序。
- 提供有序的键值对访问。
HashMap的数据结构
数据结构示意图如下:
图片来源:《面渣逆袭手册》V1.1
哈希表的基本原理是通过哈希函数将键映射到特定的存储位置,以实现快速的插入、查找和删除操作。
哈希函数用于计算键的哈希值,并根据哈希值确定元素在哈希表中的存储位置。哈希表通常包含以下组件:
- 数组:用于存储元素。
- 哈希函数:将键转换为数组的索引。
- 冲突处理机制:处理不同键可能映射到相同索引的冲突。
在插入元素时,通过哈希函数计算键的哈希值,确定存储位置。如果该位置为空,则直接插入元素;如果存在冲突,使用冲突处理机制解决。
在查找元素时,同样通过哈希函数计算哈希值,找到对应的位置进行查找。
哈希表的优点包括:
- 快速的插入、查找和删除操作。
- 不需要按照特定顺序存储元素。
如何理解红黑树
- 颜色规则:每个节点要么是红色,要么是黑色。
- 特性规则:
- 根节点是黑色的。
- 如果一个节点是红色的,那么它的子节点必须是黑色的。
- 从每个叶子节点到根节点的所有路径上,黑色节点的数量相同。
在进行插入或删除操作时,红黑树会通过一系列的旋转和颜色调整来保持这些规则,以确保树的平衡性。
图片来源:《面渣逆袭手册》V1.1
旋转操作包括左旋和右旋,用于调整树的结构。
红黑树有两种方式保持平衡: 旋转 和 染色 。通过保持红黑树的平衡性,可以提高搜索、插入和删除操作的效率,避免出现最坏情况下的线性搜索。
有关HashMap的知识点非常多,这里不做详述,后面会单独写一篇有关HashMap的相关内容。
哈希表在以下场景中比较适用:
- 快速查找:当需要快速查找数据时,哈希表可以提供高效的查找性能。
- 存储和检索数据:适用于需要频繁地插入、删除和查找数据的场景。
- 缓存:可以用于缓存数据,以提高系统的性能。
- 统计频率:用于统计元素的出现频率。
- 数据去重:去除重复的数据。
- 关联数据:建立键值对的关联。
例如,在以下场景中可能会使用哈希表:- 数据库索引:加速数据的查询。
- 缓存系统:提高数据的访问速度。
- 网页搜索引擎:快速检索和索引网页。
- 数据处理和分析:高效地处理大量数据。
四、set
HashSet
是 Java 中的一个集合类,它不允许存储重复的元素。HashSet 底层就是基于 HashMap 实现的。( HashSet 的源码⾮常⾮常少,因为除了 clone() 、 writeObject() 、 readObject() 是 HashSet⾃⼰不得不实现之外,其他⽅法都是直接调⽤ HashMap 中的⽅法。
HashSet的add方法,直接调用HashMap的put方法,将添加的元素作为key,new一个 Object作为value,直接调用HashMap的put方法,它会根据返回值是否为空来判断是否插入元素成功。
以下是 HashSet
的一些特点:
- 无序性:元素的存储顺序是无序的。
- 不允许重复元素:确保每个元素在集合中唯一。
- 基于哈希表实现:提供快速的插入、查找和删除操作。
参考
《面渣逆袭手册》V1.1.pdf