注册

从源码角度解读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,Cloneablejava.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]。


优缺点分析


优点



  1. Set接口的实现类可以高效地检查元素是否存在;
  2. Set接口的实现类不允许存在重复元素,可以用来进行去重操作;
  3. HashSet的添加、删除、查找操作时间复杂度为O(1);TreeSet的添加、删除、查找操作时间复杂度为O(logN)。

缺点



  1. 如果需要有序存储元素,那么需要使用TreeSet,但是由于TreeSet是基于红黑树实现的,因此占用内存空间较大;
  2. HashSet在哈希冲突的情况下,会导致链表长度增加,从而影响查找效率;
  3. HashSet在遍历元素时,元素的顺序不能保证。

类代码方法介绍


HashSet



  1. add(E e):向集合中添加元素;
  2. clear():清空集合中所有元素;
  3. contains(Object o):判断集合中是否存在指定的元素;
  4. isEmpty():判断集合是否为空;
  5. iterator():返回一个用于遍历集合的迭代器;
  6. remove(Object o):从集合中移除指定的元素;
  7. size():返回集合中元素的数量。

TreeSet



  1. add(E e):向集合中添加元素;
  2. ceiling(E e):返回集合中大于等于指定元素的最小元素;
  3. clear():清空集合中所有元素;
  4. contains(Object o):判断集合中是否存在指定的元素;
  5. descendingIterator():返回一个逆序遍历集合的迭代器;
  6. first():返回集合中的第一个元素;
  7. headSet(E toElement, boolean inclusive):返回集合中小于指定元素的子集;
  8. isEmpty():判断集合是否为空;
  9. iterator():返回一个用于遍历集合的迭代器;
  10. last():返回集合中的最后一个元素;
  11. remove(Object o):从集合中移除指定的元素;
  12. size():返回集合中元素的数量;
  13. subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive):返回集合中大于等于fromElement且小于等于toElement的子集;
  14. 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接口的具体类,并测试了以下基本操作:



  1. 向集合中添加元素
  2. 打印出集合中的元素个数
  3. 判断集合是否为空
  4. 判断集合中是否包含某个元素
  5. 从集合中移除某个元素
  6. 使用迭代器遍历集合中的元素
  7. 清空集合中的所有元素

测试结果


  根据如上测试用例,本地测试结果如下,仅供参考,你们也可以自行修改测试用例或者添加更多的测试数据或测试方法,进行熟练学习以此加深理解。


当运行该测试用例后,我们将得到以下输出结果:


集合中的元素个数为:3
集合是否为空:false
集合中是否包含 Python:true
从集合中移除元素后,集合中的元素个数为:2
遍历集合中的元素:
Java
Python
清空集合中的元素后,集合中的元素个数为:0

具体执行截图如下:


在这里插入图片描述


测试代码分析


  根据如上测试用例,在此我给大家进行深入详细的解读一下测试代码,以便于更多的同学能够理解并加深印象。


这段代码演示了如何使用Java中的Set接口和HashSet类。具体来说,代码实现了:


1.创建一个HashSet对象。


2.向集合中添加元素。


3.打印出集合中的元素个数。


4.判断集合是否为空。


5.判断集合中是否包含某个元素。


6.从集合中移除某个元素。


7.使用迭代器遍历集合中的元素。


8.清空集合中的所有元素。


  从这段代码可以看出,Set接口和HashSet类可以帮助我们快速地实现集合的添加、删除、查找等操作,并且还支持迭代器遍历集合中的所有元素。


作者:bug菌
来源:juejin.cn/post/7298969233546067968

0 个评论

要回复文章请先登录注册