从源码角度解读Java Set接口底层实现原理
咦咦咦,各位小可爱,我是你们的好伙伴——bug菌,今天又来给大家普及Java SE相关知识点了,别躲起来啊,听我讲干货还不快点赞,赞多了我就有动力讲得更嗨啦!所以呀,养成先点赞后阅读的好习惯,别被干货淹没了哦~
环境说明:Windows 10 + IntelliJ IDEA 2021.3.2 + Jdk 1.8
前言
Set是Java集合框架中的一个接口,它继承了Collection接口,并添加了一些独有的方法。Set可看做是没有重复元素的Collection,它的实现类包括HashSet、TreeSet等。本文将从源码的角度来解读Set接口的底层实现原理。
摘要
本文将对Java Set接口进行详细的解读,包括Set的概述、源代码解析、应用场景案例、优缺点分析、类代码方法介绍和测试用例等方面。
Set接口
概述
Set是一个不允许重复元素的集合。它继承了Collection接口,最基本的操作包括添加元素、检查元素是否存在、删除元素等。Set接口的实现类包括HashSet、TreeSet等。HashSet是基于哈希表的实现,TreeSet是基于红黑树的实现。
源代码解析
Set
Set接口是Java集合框架中的一种接口,它表示一组无序且不重复的元素。Set接口继承自Collection接口,因此它具有Collection接口的所有方法,但是在Set接口中,添加重复元素是不允许的。Set接口有两个主要的实现类:HashSet和TreeSet。其中,HashSet基于哈希表实现,对于非Null元素具有O(1)的插入和查找时间复杂度;而TreeSet基于红黑树实现,对于有序集合的操作具有良好的性能表现。在使用Set接口时,可以通过迭代器遍历元素,也可以使用foreach语句遍历元素。
如下是部分源码截图:
HashSet
HashSet基于哈希表实现,它使用了一个称为“hash表”的数组来存储元素。当我们向HashSet中添加元素时,首先会对元素进行哈希,并通过哈希值来确定元素在数组中的位置。如果该位置已经有元素了,就会通过equals方法来判断是否重复,如果重复则不添加,如果不重复则添加到该位置。当然,由于哈希表中可能会存在多个元素都哈希到同一个位置的情况,因此这些元素会被存储在同一个位置上,形成一个链表。在查找元素时,先通过哈希值定位到链表的头部,然后在链表中进行搜索,直到找到匹配的元素或到达链表的末尾。
public class HashSet extends AbstractSet implements Set, Cloneable, java.io.Serializable {
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
}
,object>
这是一个实现了 HashSet 数据结构的 Java 类。HashSet 继承了 AbstractSet 类,同时实现了 Set 接口和 Cloneable 和 Serializable 接口。
HashSet 内部使用 HashMap 来存储元素,其中元素作为 key ,一个 static final Object 作为 value,即:
private transient HashMapmap;
private static final Object PRESENT = new Object();
,object>
在构造器中,HashSet 实例化了一个空的 HashMap 对象:
public HashSet() {
map = new HashMap<>();
}
向 HashSet 中添加元素时,HashSet 调用 HashMap 的 put() 方法。当新元素没有在 HashMap 中存在时,put() 方法返回 null ,此时 HashSet 返回 true,表示添加成功。如果元素已经存在于 HashMap(即已经在 HashSet 中),那么 put() 方法返回已经存在的 Object,此时 HashSet 返回 false,表示添加失败。
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
判断 HashSet 是否包含指定元素时,HashSet 调用 HashMap 的 containsKey() 方法。如果 HashMap 中包含该元素,则 HashSet 返回 true,否则返回 false。
public boolean contains(Object o) {
return map.containsKey(o);
}
从 HashSet 中移除指定元素时,HashSet 调用 HashMap 的 remove() 方法。如果该元素存在于 HashMap 中(即在 HashSet 中),则返回 true,否则返回 false。
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
如下是部分源码截图:
TreeSet
TreeSet基于红黑树实现,它是一种自平衡的二叉查找树。每个节点都有一个额外的颜色属性,只能是红色或黑色。红黑树的基本操作包括插入、删除和查找。当我们向TreeSet中添加元素时,它会根据元素的大小来将元素添加到树中的合适位置。对于每个节点,其左子树的所有元素都比该节点的元素小,右子树的所有元素都比该节点的元素大。在删除时,如果要删除的节点有两个子节点,会先在右子树中找到最小元素,然后将该节点的元素替换为最小元素。删除最小元素就是从根节点开始,一直找到最左侧的节点即可。
public class TreeSet extends AbstractSet implements NavigableSet, Cloneable, java.io.Serializable {
private transient NavigableMap m;
private static final Object PRESENT = new Object();
public TreeSet() {
this(new TreeMap());
}
public TreeSet(NavigableMap m),object> {
this.m = m;
}
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
public boolean contains(Object o) {
return m.containsKey(o);
}
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
}
,object>,object>
这段代码定义了一个泛型类TreeSet
,继承了AbstractSet
类,并实现了接口NavigableSet
,Cloneable
和java.io.Serializable
。
类中的m
变量是一个NavigableMap,object>
类型的成员变量,TreeSet
内部实际上是通过使用TreeMap,object>
实现的。
类中还定义了PRESENT
静态常量,用于表示在TreeSet
中已经存在的元素。
TreeSet
类中的add
方法实现了向集合中添加元素的功能,使用了NavigableMap
中的put
方法,如果添加的元素在集合中不存在,则返回null
,否则返回PRESENT
。
contains
方法判断集合中是否包含某个元素。使用了NavigableMap
中的containsKey
方法。
remove
方法实现删除某个元素的功能,使用NavigableMap
中的remove
方法,如果删除成功,则返回PRESENT
。
如下是部分源码截图:
应用场景案例
Set的一个常见应用场景就是去重。由于Set中不允许存在重复元素,因此我们可以利用Set来去除列表中的重复元素,代码如下:
代码演示
Listlist = new ArrayList<>(Arrays.asList(1, 2, 3, 2, 1));
Setset = new HashSet<>(list);
list = new ArrayList<>(set);
System.out.println(list); // output: [1, 2, 3]
代码分析
根据如上代码,在此我给大家进行深入详细的解读一下测试代码,以便于更多的同学能够理解并加深印象。
该代码创建了一个包含重复元素的整型列表list,并使用list初始化了一个整型哈希集合set。然后,通过将set转换回一个新的ArrayList对象,生成一个不带重复元素的整型列表list。最后,输出list的元素。 因此,代码输出应该是[1, 2, 3]。
优缺点分析
优点
- Set接口的实现类可以高效地检查元素是否存在;
- Set接口的实现类不允许存在重复元素,可以用来进行去重操作;
- HashSet的添加、删除、查找操作时间复杂度为O(1);TreeSet的添加、删除、查找操作时间复杂度为O(logN)。
缺点
- 如果需要有序存储元素,那么需要使用TreeSet,但是由于TreeSet是基于红黑树实现的,因此占用内存空间较大;
- HashSet在哈希冲突的情况下,会导致链表长度增加,从而影响查找效率;
- HashSet在遍历元素时,元素的顺序不能保证。
类代码方法介绍
HashSet
add(E e)
:向集合中添加元素;clear()
:清空集合中所有元素;contains(Object o)
:判断集合中是否存在指定的元素;isEmpty()
:判断集合是否为空;iterator()
:返回一个用于遍历集合的迭代器;remove(Object o)
:从集合中移除指定的元素;size()
:返回集合中元素的数量。
TreeSet
add(E e)
:向集合中添加元素;ceiling(E e)
:返回集合中大于等于指定元素的最小元素;clear()
:清空集合中所有元素;contains(Object o)
:判断集合中是否存在指定的元素;descendingIterator()
:返回一个逆序遍历集合的迭代器;first()
:返回集合中的第一个元素;headSet(E toElement, boolean inclusive)
:返回集合中小于指定元素的子集;isEmpty()
:判断集合是否为空;iterator()
:返回一个用于遍历集合的迭代器;last()
:返回集合中的最后一个元素;remove(Object o)
:从集合中移除指定的元素;size()
:返回集合中元素的数量;subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)
:返回集合中大于等于fromElement且小于等于toElement的子集;tailSet(E fromElement, boolean inclusive)
:返回集合中大于等于指定元素的子集。
测试用例
下面是一些测试用例,展示了Set接口的一些基本操作:
package com.demo.javase.day61;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
/**
* @Author bug菌
* @Date 2023-11-06 10:33
*/
public class SetTest {
public static void main(String[] args) {
// 创建一个 HashSet 对象
Setset = new HashSet();
// 向集合中添加元素
set.add("Java");
set.add("C++");
set.add("Python");
// 打印出集合中的元素个数
System.out.println("集合中的元素个数为:" + set.size());
// 判断集合是否为空
System.out.println("集合是否为空:" + set.isEmpty());
// 判断集合中是否包含某个元素
System.out.println("集合中是否包含 Python:" + set.contains("Python"));
// 从集合中移除某个元素
set.remove("C++");
System.out.println("从集合中移除元素后,集合中的元素个数为:" + set.size());
// 使用迭代器遍历集合中的元素
Iterator iterator = set.iterator();
System.out.println("遍历集合中的元素:");
while (iterator.hasNext()) {
String element = iterator.next();
System.out.println(element);
}
// 清空集合中的所有元素
set.clear();
System.out.println("清空集合中的元素后,集合中的元素个数为:" + set.size());
}
}
该测试用例使用了HashSet作为实现Set接口的具体类,并测试了以下基本操作:
- 向集合中添加元素
- 打印出集合中的元素个数
- 判断集合是否为空
- 判断集合中是否包含某个元素
- 从集合中移除某个元素
- 使用迭代器遍历集合中的元素
- 清空集合中的所有元素
测试结果
根据如上测试用例,本地测试结果如下,仅供参考,你们也可以自行修改测试用例或者添加更多的测试数据或测试方法,进行熟练学习以此加深理解。
当运行该测试用例后,我们将得到以下输出结果:
集合中的元素个数为:3
集合是否为空:false
集合中是否包含 Python:true
从集合中移除元素后,集合中的元素个数为:2
遍历集合中的元素:
Java
Python
清空集合中的元素后,集合中的元素个数为:0
具体执行截图如下:
测试代码分析
根据如上测试用例,在此我给大家进行深入详细的解读一下测试代码,以便于更多的同学能够理解并加深印象。
这段代码演示了如何使用Java中的Set接口和HashSet类。具体来说,代码实现了:
1.创建一个HashSet对象。
2.向集合中添加元素。
3.打印出集合中的元素个数。
4.判断集合是否为空。
5.判断集合中是否包含某个元素。
6.从集合中移除某个元素。
7.使用迭代器遍历集合中的元素。
8.清空集合中的所有元素。
从这段代码可以看出,Set接口和HashSet类可以帮助我们快速地实现集合的添加、删除、查找等操作,并且还支持迭代器遍历集合中的所有元素。
来源:juejin.cn/post/7298969233546067968