Java进阶之集合框架(Set)

基本内容】

     二、Set接口(接上一章)

     Set是Java集合框架中不允许有重复元素的无序集合,其典型的实现类是HashSet,它完全是遵循Set接口特性规范实现的,无序且不允许元素重复;而Set接口下的实现类还有LinkedHashSet和TreeSort,两者实现了有序的Set。Set接口及其实现类的完整继承关系如下图:

图片

     从上述继承图可以看出,HashSet只是继承了抽象类AbastractSet和实现了Set接口,是比较典型的Set接口的实现,而LinkedHashSet和TreeSet则都实现了SequencedSet接口,以此保证元素的有序。下面对三个实现类作具体介绍。

       HashSet

       HashSet的特性基本上等同Set接口的特性:无序且不能元素重复。从HashSet的命名来看,其底层存储实现和哈希表有关,那HashSet实现类是如何实现元素不能重复的呢?我们不妨看看HashSet的源代码:


public class HashSet<E>extends AbstractSet<E>implements Set<E>, Cloneable, java.io.Serializable
{@java.io.Serialstatic final long serialVersionUID = -5024744406713321676L;transient HashMap<E,Object> map;// Dummy value to associate with an Object in the backing Mapstatic final Object PRESENT = new Object();/*** Constructs a new, empty set; the backing {@code HashMap} instance has* default initial capacity (16) and load factor (0.75).*/public HashSet() {map = new HashMap<>();}/*** Constructs a new set containing the elements in the specified* collection.  The {@code HashMap} is created with default load factor* (0.75) and an initial capacity sufficient to contain the elements in* the specified collection.** @param c the collection whose elements are to be placed into this set* @throws NullPointerException if the specified collection is null*/public HashSet(Collection<? extends E> c) {map = HashMap.newHashMap(Math.max(c.size(), 12));addAll(c);}......HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);}}

     从上述HashSet的源代码定义可以看出,HashSet底层是采用Java集合框架双列集合HashMap来存储数据元素的,而我们知道HashMap底层是主要采用哈希表实现,那HashSet是如何通过HashMap实现元素不能重复的呢?我们继续看源代码:

   public Iterator<E> iterator() {return map.keySet().iterator();}......public boolean contains(Object o) {return map.containsKey(o);}/*** Adds the specified element to this set if it is not already present.* More formally, adds the specified element {@code e} to this set if* this set contains no element {@code e2} such that* {@code Objects.equals(e, e2)}.* If this set already contains the element, the call leaves the set* unchanged and returns {@code false}.** @param e element to be added to this set* @return {@code true} if this set did not already contain the specified* element*/public boolean add(E e) {return map.put(e, PRESENT)==null;}/*** Removes the specified element from this set if it is present.* More formally, removes an element {@code e} such that* {@code Objects.equals(o, e)},* if this set contains such an element.  Returns {@code true} if* this set contained the element (or equivalently, if this set* changed as a result of the call).  (This set will not contain the* element once the call returns.)** @param o object to be removed from this set, if present* @return {@code true} if the set contained the specified element*/public boolean remove(Object o) {return map.remove(o)==PRESENT;}

     从上述HashSet增删元素的方法实现中,我们可以看到HashSet是把元素作为内部HashMap的键,把一个不可变的常量对象PRESENT作为内部HashMap的值;我们都知道HashMap的键是哈希值是唯一的,如果HashSet添加的新元素和HashMap的某个键重复,HashMap的键自然会被覆盖,因而不会出现重复;而HashSet获取元素的时候,也是获取内部HashMap的键的列表。至于HashMap的键如何保持唯一性,不是还会有哈希冲突吗?相关知识请看后续Java集合框架相关文章。

      总之,HashSet通过内部HashMap的键实现了元素的唯一性和不重复,同时因为底层采用哈希表实现,通过哈希键值能快速定位元素,因而具有高效的随机访问和快速查找能力。

       LinkedHashSet

      LinkedHashSet是HashSet的子类,所以自然具备HashSet快速查找元素和不允许重复元素的特性,但是为了保证元素的有序性,LinkedHashSet通过内置了一个双向链表来维护所有元素,从而可以利用迭代器快速遍历元素和保证元素存取的有序性。那LinkedHashSet内部是如何实现这样一个双向链表的呢?其实双向链表的实现不在LinkedHashSet的源代码中,双向链表的功能是通过其内部的LinkedHashMap来实现的,我们看LinkedHashSet的源代码:


public class LinkedHashSet<E>extends HashSet<E>implements SequencedSet<E>, Cloneable, java.io.Serializable {....../*** Constructs a new, empty linked hash set with the specified initial* capacity and load factor.** @apiNote* To create a {@code LinkedHashSet} with an initial capacity that accommodates* an expected number of elements, use {@link #newLinkedHashSet(int) newLinkedHashSet}.** @param      initialCapacity the initial capacity of the linked hash set* @param      loadFactor      the load factor of the linked hash set* @throws     IllegalArgumentException  if the initial capacity is less*               than zero, or if the load factor is nonpositive*/public LinkedHashSet(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor, true);}/*** Constructs a new, empty linked hash set with the specified initial* capacity and the default load factor (0.75).** @apiNote* To create a {@code LinkedHashSet} with an initial capacity that accommodates* an expected number of elements, use {@link #newLinkedHashSet(int) newLinkedHashSet}.** @param   initialCapacity   the initial capacity of the LinkedHashSet* @throws  IllegalArgumentException if the initial capacity is less*              than zero*/public LinkedHashSet(int initialCapacity) {super(initialCapacity, .75f, true);}/*** Constructs a new, empty linked hash set with the default initial* capacity (16) and load factor (0.75).*/public LinkedHashSet() {super(16, .75f, true);}......}

     从上述代码中可以看出,LinkedHashSet的构造函数都调用了基类的构造函数,这个基类正是HashSet,我们再回头看看HashSet的构造函数代码,其实现如下:

HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);}

      HashSet的构造函数之一正是新创建了一个LinkedHashMap,正是这个LinkedHashMap实现了双向链表的功能从而有效地支持了LinkedHashSet元素存取的有效性,同时也保留了基于哈希键值快速定位元素的特性以及唯一性。从后续的代码也可以看出,LinkedHashSet的其他操作都是通过这个内部的LinkedHashMap来进行的。代码如下:

@SuppressWarnings("unchecked")LinkedHashMap<E, Object> map() {return (LinkedHashMap<E, Object>) map;}/*** {@inheritDoc}* <p>* If this set already contains the element, it is relocated if necessary so that it is* first in encounter order.** @since 21*/public void addFirst(E e) {map().putFirst(e, PRESENT);}/*** {@inheritDoc}* <p>* If this set already contains the element, it is relocated if necessary so that it is* last in encounter order.** @since 21*/public void addLast(E e) {map().putLast(e, PRESENT);}/*** {@inheritDoc}** @throws NoSuchElementException {@inheritDoc}* @since 21*/public E getFirst() {return map().sequencedKeySet().getFirst();}/*** {@inheritDoc}** @throws NoSuchElementException {@inheritDoc}* @since 21*/public E getLast() {return map().sequencedKeySet().getLast();}/*** {@inheritDoc}** @throws NoSuchElementException {@inheritDoc}* @since 21*/public E removeFirst() {return map().sequencedKeySet().removeFirst();}/*** {@inheritDoc}** @throws NoSuchElementException {@inheritDoc}* @since 21*/public E removeLast() {return map().sequencedKeySet().removeLast();}/*** {@inheritDoc}* <p>* Modifications to the reversed view are permitted and will be propagated to this set.* In addition, modifications to this set will be visible in the reversed view.** @return {@inheritDoc}* @since 21*/public SequencedSet<E> reversed() {class ReverseLinkedHashSetView extends AbstractSet<E> implements SequencedSet<E> {public int size()                  { return LinkedHashSet.this.size(); }public Iterator<E> iterator()      { return map().sequencedKeySet().reversed().iterator(); }public boolean add(E e)            { return LinkedHashSet.this.add(e); }public void addFirst(E e)          { LinkedHashSet.this.addLast(e); }public void addLast(E e)           { LinkedHashSet.this.addFirst(e); }public E getFirst()                { return LinkedHashSet.this.getLast(); }public E getLast()                 { return LinkedHashSet.this.getFirst(); }public E removeFirst()             { return LinkedHashSet.this.removeLast(); }public E removeLast()              { return LinkedHashSet.this.removeFirst(); }public SequencedSet<E> reversed()  { return LinkedHashSet.this; }public Object[] toArray() { return map().keysToArray(new Object[map.size()], true); }public <T> T[] toArray(T[] a) { return map().keysToArray(map.prepareArray(a), true); }}return new ReverseLinkedHashSetView();}

     包括实现SequencedSet接口的反向操作,间接都是通过内部的LinkedHashMap来最终完成的。至于LinkedHashMap内部如何实现双向链表的功能,我们暂时把它当做一个黑盒,在后面的Java集合框架章节中去深入了解。

      总之,LinkedHashSet是通过内部的LinkedHashMap保留了基类HashSet的特性,同时又实现了元素存取的有序性,但是因为维护内部的双向链表,在性能上逊色HashSet。

       它的应用场景:1. 在一个流式处理数据的应用中,需要对元素进行去重和排序操作;2. 在一个多线程爬虫程序中,需要对爬取到的URL进行去重操作,就可以使用LinkedHashSet来避免并发修改异常。

      TreeSet

      TreeSet是Set接口家族中的一员,它和HashSet以及LinkedHashSet一样,不允许元素重复,同样无法保证线程安全,具体区别如下表:

图片

      TreeSet底层是通过红黑树实现了对元素的排序,但是是通过内部的TreeMap来实现的,红黑树的具体逻辑在TreeMap代码中实现,这点HashSet、LinkedHashSet和TreeSet三者都是一样的,依赖的都是对应的Map集合类。

       TreeSet默认是自然排序,按元素的大小进行排序,具体规则如下:

1.对于数值类型:Integer、Double,默认按照从小到大的顺序进行排序。
2.对于字符、字符串类型:按照字符在ASCII码表中的数字升序进行排序。

       参考代码如下:


import java.util.TreeSet;public class TreeSetExample {public static void main(String[] args) {TreeSet<Integer> set = new TreeSet<>();// 添加元素set.add(20);set.add(10);       set.add(30);set.add(40);// 尝试添加重复元素boolean isAdded = set.add(20); // 返回 false// 获取第一个和最后一个元素int first = set.first(); // 返回 10int last = set.last(); // 返回 40// 遍历 TreeSetfor (Integer num : set) {System.out.println(num);}  // 输出顺序为:10 ,20, 30 ,40}
}

      自然排序主要应用于Jdk内置的数据类型,对于用户自定义类型需要采用定制排序,定制排序有两种方式:方法一、放入TreeSet集合的元素需要实现接口java.lang.Comparable接口,例如以下代码:


public class TreeSetTest04 {public static void main(String[] args) {Person1 p1 = new Person1(32);Person1 p2 = new Person1(20);Person1 p3 = new Person1(25);TreeSet<Person1> ts = new TreeSet<>();ts.add(p1);ts.add(p2);ts.add(p3);for (Person1 x:ts) {System.out.println(x);}}}/*** 放在TreeSet集合中的元素需要实现java.lang.Comparable接口* 并且实现compareTo方法。equals可以不写*/
class Person1 implements  Comparable<Person1>{int age;public Person1(int age){this.age = age;}// 重写toString方法@Overridepublic String toString() {return "Person1{" +"age=" + age +'}';}/*** 需要在这个比较的方法中编写比较的逻辑或者比较的规则,按照什么进行比较* 拿着参数k和集合中的每一个key进行比较,返回值可能是大于0 小于0 或者等于0* 比较规则最终还是由程序员指定的; 例如按照年龄升序,或者按照年龄降序。* @param o* @return*/@Overridepublic int compareTo(Person1 o) { // c1.compareTo(c2)return this.age-o.age; // >0 =0 <0 都有可能}
}

   方法二,在构造器TreeSet的时候给它传一个实现了Comparator比较器接口的对象,例如以下代码:


public class TreeSetTest06 {public static void main(String[] args) {// 此时创建TreeSet集合的时候,需要使用这个比较器。// TreeSet<WuGui> wuGui = new TreeSet<>(); // 这样不行,没有通过构造方法传递一个比较器进去。// 给构造方法传递一个比较器TreeSet<WuGui> wuGui = new TreeSet<>(new WuGuiComparator()); // 底层源码可知其中一个构造方法的参数为比较器// 大家可以使用匿名内部类的方式wuGui.add(new WuGui(100));wuGui.add(new WuGui(10));wuGui.add(new WuGui(1000));for (WuGui wugui:wuGui) {System.out.println(wugui);}}
}
class WuGui {int age;public WuGui(int age) {this.age = age;}@Overridepublic String toString() {return "WuGui{" +"age=" + age +'}';}
}
// 单独再这里编写一个比较器
// 比较器实现java.util.Comparator接口 (Comparable是java.lang包下的。Comparator是java.util包下的。)
class WuGuiComparator implements Comparator<WuGui>{@Overridepublic int compare(WuGui o1, WuGui o2) {// 指定比较规则// 按照年龄排序return o1.age-o2.age;}
}

      两种方法适应场景如下:


1.比较规则经常变换: Comparator 接口的设计符合OCP原则(可切换)2.比较规则较固定: Comparable

    如果一个TreeSet集合两种比较方法都实现了,则以方法二比较器接口优先。

【注意事项

1.自然排序的注意事项:如果字符串里的字符比较多,那么它就是从首字母开始,挨个比较的,要注意的是,此时跟字符串的长度是没有什么关系的,例如 "aaa" 和 "ab",在比较的时候,首先比第一个字母,发现第一个字母都是 a;继续往后来比第二个字母,第二个字母就不一样了,这个时候就已经能确定大小关系了,'a' 比 b 大,此时后面的就不会再看了。

码农爱刷题

为计算机编程爱好者和从业人士提供技术总结和分享 !为前行者蓄力,为后来者探路!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/426472.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

前后端分离Vue美容店会员信息管理系统o7grs

目录 技术栈介绍具体实现截图系统设计研究方法&#xff1a;设计步骤设计流程核心代码部分展示研究方法详细视频演示试验方案论文大纲源码获取 技术栈介绍 本课题的研究方法和研究步骤基本合理&#xff0c;难度适中&#xff0c;本选题是学生所学专业知识的延续&#xff0c;符合…

java项目之疫情下图书馆管理系统源码(springboot)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的疫情下图书馆管理系统。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息。 项目简介&#xff1a; 疫情下图书馆管理系…

【OJ刷题】双指针问题6

这里是阿川的博客&#xff0c;祝您变得更强 ✨ 个人主页&#xff1a;在线OJ的阿川 &#x1f496;文章专栏&#xff1a;OJ刷题入门到进阶 &#x1f30f;代码仓库&#xff1a; 写在开头 现在您看到的是我的结论或想法&#xff0c;但在这背后凝结了大量的思考、经验和讨论 目录 1…

OpenAI o1——人工智能推理能力的飞跃,助力高级问题解决

前言 开放人工智能 新模型&#xff0c; OpenAI o1 或草莓&#xff0c;代表了 人工智能。它以 OpenAI 的 GPT 系列等先前模型为基础&#xff0c;并引入了增强的推理能力&#xff0c;从而加深了科学、编码和数学等各个领域的问题解决能力。与主要擅长处理和生成文本的前辈不同&a…

Pandas的入门操作-Series对象

Pandas的数据结构 Series对象 class pandas.Series(dataNone, indexNone) data参数 含义&#xff1a;data是Series构造函数中最主要的参数&#xff0c;它用来指定要存储在Series中的数据。 数据类型&#xff1a;data可以是多种数据类型&#xff0c;例如&#xff1a; Python 列…

【JavaEE初阶】多线程6(线程池\定时器)

欢迎关注个人主页&#xff1a;逸狼 创造不易&#xff0c;可以点点赞吗~ 如有错误&#xff0c;欢迎指出~ 目录 实例3:线程池 参数解释 核心线程数, 最大线程数 允许空闲的最大时间 ,时间单位 任务队列(阻塞队列) 线程工厂>工厂设计模式 拒绝策略 使用举例 模拟实现一个线…

leetcode:最高乘法得分

用auto可以过 class Solution { public:long long maxScore(vector<int>& a, vector<int>& b) {int n b.size();vector<vector<long long>> memo(4,vector<long long>(b.size(), LLONG_MIN));auto dfs [&](auto&& dfs, i…

构建自己的文生图工具:Python + Stable Diffusion + CUDA

构建自己的文生图工具&#xff1a;Python Stable Diffusion CUDA 前言概述环境搭建安装PyTorch安装Stable Diffusion编写Python代码结论结语 前言 在这个数字化和人工智能飞速发展的时代&#xff0c;图像生成技术正逐渐成为现实。想象一下&#xff0c;只需输入几个关键词&…

Nginx反向代理出现502 Bad Gateway问题的解决方案

&#x1f389; 前言 前一阵子写了一篇“关于解决调用百度翻译API问题”的博客&#xff0c;近日在调用其他API时又遇到一些棘手的问题&#xff0c;于是写下这篇博客作为记录。 &#x1f389; 问题描述 在代理的遇到过很多错误码&#xff0c;其中出现频率最高的就是502&#x…

【数据结构与算法 | 灵神题单 | 自顶向下DFS篇】力扣1022,623

1. 力扣1022&#xff1a;从根到叶的二进制之和 1.1 题目&#xff1a; 给出一棵二叉树&#xff0c;其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。 例如&#xff0c;如果路径为 0 -> 1 -> 1 -> 0 -> 1&#xff0c;那…

OpenHarmony(鸿蒙南向开发)——标准系统方案之扬帆移植案例

往期知识点记录&#xff1a; 鸿蒙&#xff08;HarmonyOS&#xff09;应用层开发&#xff08;北向&#xff09;知识点汇总 鸿蒙&#xff08;OpenHarmony&#xff09;南向开发保姆级知识点汇总~ OpenHarmony&#xff08;鸿蒙南向开发&#xff09;——轻量系统STM32F407芯片移植案…

SpringBoot---------Actuator监控

1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-actuator</artifactId> </dependency> 2、开启配置 management.endpoints.web.exposure.include* 3、启动项目&#xff0c;查看监控…

Linux·权限与工具-git与gdb

1. git工具 git是一款软件&#xff0c;发明它的人同时发明了Linux操作系统&#xff0c;也就是大名鼎鼎的Linus Torvalds 林纳斯托瓦兹。后来人们把git软件包装&#xff0c;产生了github、gitee等平台。 git产生的初衷就是便于进行多人协同管理&#xff0c;同时它还可以用来将本…

神经网络通俗理解学习笔记(3)注意力神经网络

Tansformer 什么是注意力机制注意力的计算键值对注意力和多头注意力自注意力机制注意力池化及代码实现Transformer模型Transformer代码实现BERT 模型GPT 系列模型GPT-1模型思想GPT-2模型思想GPT-3 模型思想 T5模型ViT模型Swin Transformer模型GPT模型代码实现 什么是注意力机制…

Linux基础开发环境(git的使用)

1.账号注册 git 只是一个工具&#xff0c;要想实现便捷的代码管理&#xff0c;就需要借助第三方平台进行操作&#xff0c;当然第三平台也是基于git 开发的 github 与 gitee 代码托管平台有很多&#xff0c;这里我们首选 Github &#xff0c;理由很简单&#xff0c;全球开发者…

Redis - 深入理解Redis事务

目录 Redis是如何实现事务的&#xff1f;事务中执行的命令出现错误&#xff0c;会回滚事务吗&#xff1f;同一个连接可以重复开启事务吗&#xff1f;多个客户端同时开启事务会怎样&#xff1f;使用Redis事务只用MULTI和EXEC吗&#xff1f;Redis中的WATCH机制是怎么实现的&#…

UDP聊天室项目

代码思路 服务器 #include <stdio.h> #include <sys/types.h> /* See NOTES */ #include <sys/socket.h> #include <netinet/in.h> #include <netinet/ip.h> #include <stdlib.h> #include <unistd.h> #include <arpa/inet.h>…

JVM 调优篇7 调优案例1-堆空间的优化解决

一 jvm优化 1.1 优化实施步骤* 1)减少使用全局变量和大对象&#xff1b; 2)调整新生代的大小到最合适&#xff1b; 3)设置老年代的大小为最合适&#xff1b; 4)选择合适的GC收集器&#xff1b; 1.2 关于GC优化原则 多数的Java应用不需要在服务器上进行GC优化&#xff1…

ESP8266做httpServer提示Header fields are too long for server to interpret

CONFIG_HTTP_BUF_SIZE512 CONFIG_HTTPD_MAX_REQ_HDR_LEN1024 CONFIG_HTTPD_MAX_URI_LEN512CONFIG_HTTPD_MAX_REQ_HDR_LEN由512改为1024

02 基于STM32的按键控制继电器驱动电机

本专栏所有源资料都免费获取&#xff0c;没有任何隐形消费。 注意事项&#xff1a;STM32仿真会存在各种各样BUG&#xff0c;且尽量按照同样仿真版本使用。本专栏所有的仿真都采用PROTEUS8.15。 本文已经配置好STM32F103C8T6系列&#xff0c;在PROTUES仿真里&#xff0c;32单片…