JAVA集合Set之HashSet详解

HashSet这个类实现了Set集合,实际为一个HashMap的实例。并且HashSet提供了三个构造函数

大家好,又见面了,我是你们的朋友全栈君。

HashSet这个类实现了Set集合,实际为一个HashMap的实例。对集合的迭代次序没有任何保证; 特别是,它不能保证订单会随着时间的推移保持不变。这个类允许null 元素。

JAVA集合Set之HashSet详解

并且HashSet提供了三个构造函数:

JAVA集合Set之HashSet详解

无参数的构造函数,此构造函数创建一个大小为16的容器,加载因子为0.75(容器的大小始终是2的冥,默认为16不在赘述,在后面文章中介绍另外的构造函数,添加指定值的时候会介绍程序是如何保证始终是2的冥,透露一点如果我们传值为5的一个容器大写,那么创建的容器实际大小为8,感兴趣的可以先去看一下算法。),具体看一下实例化一个hashSet的具体参数,并且为了保证速度,我们在实例化的这个参数的时候尽量不要把容器设置的太大,或者加载因子设置太小,后面在说得到HashSet的另外三个构造函数。

Set<String> set =new HashSet<>();

JAVA集合Set之HashSet详解

由此图我们可以看到确实实例化了一个容量为16的HashMap,其中loadFactor为加载因子,当容量*加载因子=threshold,

为这个容器的临界值,当存储的元素到了这个临界值,那么容器就会自动扩容。

那么我接下来思考,容器是怎么保证添加的元素不重复的呢?(由于Set取值的时候是调用值本身来取值的,所以不能重复,如果重复了,根据值去取的时候就会不知道取哪一个。list是根据下标map是根据具体key取值

接下来我们看一下HashSet的add方法:

JAVA集合Set之HashSet详解

这个方法实际上是添加的一个put方法,描述的意思是:向这个set集合中添加元素,如果这个元素没有在集合中则添加到这个集合中。如果这个集合已经存在元素调用将离开。(其中PRESENT)

JAVA集合Set之HashSet详解

K为我们添加的参数,V为一个Object的定值。

下面我们看一下具体的put方法:

JAVA集合Set之HashSet详解

如果key为空,我们添加一个null=value的一个元素到容器里面,如果此时容器中有一个k,v 为 null=“1234”的元素,我们在添加一个null= “456”的一个元素,容器是怎么计算的:

我们看一下这个方法return putForNullKey(value):

JAVA集合Set之HashSet详解

卸载这个put空的key。什么意思?就是删除并替换的意思。

会循环拿出容器里面的元素,e=table[0],然后判断e != null 说明这个集合中是有元素的,那么紧接着开始判断,因为是K,V的形式,拿到这个k判断是否为空,如果为空,那么就用当前的value值替换原来对应的value值,也就是 null = 1234 的这个元素被null = 456 的元素替换掉。

如果第一个e=table[0]的元素,e=null 那么就不在进入这个方法,直接modCount 做累加,然后添加这个key=null,value=456的值。上面是添加key=null,后面讲addEntry方法的具体实现。

下面我们分析具体添加的实现,来理解key是如何保证key不重复的:

其中

JAVA集合Set之HashSet详解

为计算的具体hash值,具体实现如下:

JAVA集合Set之HashSet详解

useAltHashing具体是什么目前还没有理解,我们就按默认的false来计算这个hash值。

^为异或运算符这里简单说一下这个异或:

^是异或运算符(把数据转换成二进制,然后按位进行运算)。
运算规则:0^0 = 0, 1^0 = 1,  0^1 = 1,  1^1 = 0,运算对象相同为0,不同为1.
如:3^5 的运算过程为:
    (1)先将3和5转换成二进制的11和101
    (2)再按对应的位分别进行运算,11位数不足补零
             011
       ^   101
      ———–
             110
     (3)运算结果转换成10进制:6
 
异或运算的三个个特点:
    (1) 0^0=0,   0^1=1   0与任何数异或=任何数
    (2) 1^0=1,   1^1=0   1与任何数异或 =任何数取反
    (3) 任何数异或自己=把自己置0

还有 | & 可以百度了解下

然后简单介绍一下HashCode的算法:下面说两种

1.Integer的算法:

JAVA集合Set之HashSet详解

return当前的一个值,这个比较简单。

2.String的算法:

JAVA集合Set之HashSet详解

String中的hash算法,我们以int h = hash; h = 0 为基础算:例如传值为:String str = “srt”;

char val[] = {‘s’,’r’,’t’}

循环获取数组val的值,其中  h = 31 * h + val[i],val[i] 获取的是ASCII十进制的对应值,循环计算相加。最后返回具体的hash值。

最后在

JAVA集合Set之HashSet详解

这样计算出具体的hash值,也就是存储在map中的具体位置,相当于数组中的下标,所以效率上是非常快的。

后面就好理解了:

根据hash得到具体的位置,然后判断这个位置上面你的值是否hash一样并且key是否一样,如果一样,那么就替换掉,如果不一样就填加进去,具体添加方法为:

JAVA集合Set之HashSet详解

其中处理为:

JAVA集合Set之HashSet详解

添加值到容器中,在适当的时候扩容,什么时候扩容,当当前size >= threshold,临界值时候,扩容当前table大小的两倍,如16,到了size= 12 时候扩容到32.

具体添加如下:

JAVA集合Set之HashSet详解

另外三个构造函数简答列举一下:

HashSet(Collection<? extends E> c)
构造一个包含指定集合中的元素的新集合。  
HashSet(int initialCapacity)
构造一个新的空集合; 背景HashMap实例具有指定的初始容量和默认负载因子(0.75)。  
HashSet(int initialCapacity, float loadFactor)
构造一个新的空集合; 背景HashMap实例具有指定的初始容量和指定的负载因子。 

这些都有在jdk的API中可以具体看一下。

最后总结一下:

此文章主要介绍了一下Set的一种实现HashSet的具体实现和保证key不重复的源码算法和原因。并且在最后说明一下上面忘记了:此实现不同步,为线程不安全的实现,如果有多个线程同时访问这个容器(HashSet),并对立面的元素进行了修改,则需要在外部同步。保证数据的冥等性(幂等是数据中得一个概念,表示N次变换和1次变换的结果相同。

后面后再其他文章分别介绍TreeSet和LinkedHashSet

如果有对此文好的建议欢迎评价交流。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/124684.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Flicker-detect Sensor_sensorless sensing

    Flicker-detect Sensor_sensorless sensingSensor在日光灯作为光源下获取图像数据时会产生flicker,其根本原因是照在不同pixel上光能量不同产生的,所接受的光能量的不同也就是图像的亮度的不同。电源的频率有两种标准:50Hz(大陆)和60Hz(台湾、日本)的正弦波形,当然能量是没有方向性的,因此对应的能量是一个频率为100Hz和120Hz的波形,如下图1所示:图1、60Hz电源频率及能量波形      由于能量在时间…

    2022年10月13日
  • Ext.apply 学习[通俗易懂]

    Ext.apply 学习[通俗易懂]一:ext.apply用来把参数拷贝到对象中,先看ext.apply源代码: Ext.apply=function(o,c,defaults){//no"this"referenceforfriendlyoutofscopecallsif(defaults){Ext.apply(o,defaults);}…

  • CIDR地址块及其子网划分(内含原始IP地址分类及其子网划分的介绍)

    CIDR地址块及其子网划分(内含原始IP地址分类及其子网划分的介绍)CIDR地址块及其子网划分1.CIDR概述及其地址块计算  CIDR中文全称是无分类域间路由选择,英文全称是ClasslessInter-DomainRouting,在平常,大家多称之为无分类编址,它也是构成超网的一种技术实现。2.CIDR子网划分3.总结

  • linux(3) 处理目录的常用命令「建议收藏」

    linux(3) 处理目录的常用命令「建议收藏」目录命令总览ls(英文全拼:listfiles):列出目录及文件名cd(英文全拼:changedirectory):切换目录pwd(英文全拼:printworkdirectory):显

  • 基于卷积神经网络的人脸识别[通俗易懂]

    基于卷积神经网络的人脸识别[通俗易懂]基于卷积神经网络的人脸识别的实现利用opencv获取人脸,采集人脸数据,将收集到的人脸数据加载到内存,搭建属于自己的卷积神经网络,并用人脸数据训练自己的网络,将训练好的网络保存成模型,最后再用opencv获取实时人脸用先前训练好的模型来识别人脸。1.前言随着社会的不断进步以及各方面对于快速有效的自动身份验证的迫切要求,生物特征识别技术在近几十年得到了飞速的发展。作为人的一种内在属性,并且具有…

  • 学计算机应该怎样学,初学者该如何学习电脑知识

    学计算机应该怎样学,初学者该如何学习电脑知识看到不少刚入门的电脑刚入门者找不到适合自己的学习方法,到处碰壁,那么初学者该如何学习电脑知识呢?接下来大家跟着学习啦小编一起来了解一下学习电脑知识的解决方法吧。初学者学习电脑知识方法第一阶段:鼠标和键盘的操作鼠标的操作主要是:移动、拖动、单击、双击和右击,知道鼠标的作用以及基本操作。掌握键盘的操作,可以通过打字练习来完成,熟悉键盘排列,可以熟练打字。第二阶段:操作系统的学习对windowsxp的…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号