文档章节

java中HashSet的去重以及容量扩增原理

BKC
 BKC
发布于 2016/07/11 10:27
字数 577
阅读 477
收藏 2
点赞 0
评论 0

        首先需要明白java中HastSet实际上是用散列表实现的,散列表的大小默认大小为16(也叫散列表元的数量),加载因子为0,75(下面会解释什么是加载因子)。

        去重原理:当hashset add一个元素A的时候,首先获取这个元素的散列码(hashcode方法),假设散列码为400,然后将散列码对散列表元的数量取模,400%16=0;

        0表示第一个元素,然后将元素A与散列表中的第一个链表中(取模为0,所以这里是第一个链表)的每个元素进行比较,(通过equals进行比较~~)如果该链表中没有找到与元素A相同的元素,则将元素A添加到该链表,如果找到某个元素与元素A相同,则表示Set中已经存在了该元素,不添加元素A。 

        容量扩容原理:这里先解释下什么是加载因子,当散列表中为非空的散列表元数量除以所有散列表元的数量>加载因子的时候,hashset就会进行再散列,即将散列表大小在原有基础上x2,对所有元素进行重新散列,得到新的散列表,以前的散列表就没用了~~。举个简单的例子:假设现在hashset散列表大小为·8,加载因子为0,75,hastset中元素有30个,第一个链表包含14个元素,第二个链表为空(为空记为0),以此类推分别为:14   0  0  4  2  2  2  6

        现在set添加第31个元素B,B的散列值为9,9%b=1,所以将元素B与第二个链表中的元素进行去重比较,发现第二个链表为空链表,所以将元素B添加到第二个链表。此时散列表各个链表的元素个数分别为14 1 0 4 2 2 2 6,非空链表除以整个链表的大小为7/8>0.75,这时就会进行再散列,散列表的大小为8x2=16。当元素不断增加时,以此类推扩容。

© 著作权归作者所有

共有 人打赏支持
BKC

BKC

粉丝 2
博文 32
码字总数 35753
作品 0
朝阳
程序员
java 集合类Array、List、Map区别和联系

java集合类主要分为以下三类: 第一类:Array、Arrays 第二类:Collection :List、Set 第三类:Map :HashMap、HashTable 一、Array , Arrays Java所有“存储及随机访问一连串对象”的做法...

五大三粗
2015/02/27
0
0
Java:HashMap和Hashset的实现

深入Java集合学习系列:HashMap的实现原理 深入Java集合学习系列:HashSet的实现原理 HashSet基于HashMap实现。

樂天
2015/06/28
0
2
Java高级程序员面试大纲——错过了金三,你还要错过银四吗

跳槽时时刻刻都在发生,但是我建议大家跳槽之前,先想清楚为什么要跳槽。切不可跟风,看到同事一个个都走了,自己也盲目的开始面试起来(期间也没有准备充分),到底是因为技术原因(影响自己...

Java高级架构
04/27
0
0
【JAVA集合框架二 】java集合框架容器 java框架层级 继承图结构 集合框架的抽象类 集合框架主要实现类

本文关键词: java集合框架 框架设计理念 容器 继承层级结构 继承图 集合框架中的抽象类 主要的实现类 实现类特性 集合框架分类 集合框架并发包 并发实现类 什么是容器? 由一个或多个确定的元...

noteless
07/09
0
0
Java程序员面试大纲—错过了金三银四,你还要错过2018吗?

跳槽时时刻刻都在发生,但是我建议大家跳槽之前,先想清楚为什么要跳槽。切不可跟风,看到同事一个个都走了,自己也盲目的开始面试起来(期间也没有准备充分),到底是因为技术原因(影响自己...

java高级架构牛人
04/27
0
0
Java map双括号初始化方式的问题

关于Java双括号的初始化凡是确实很方便,特别是在常量文件中,无可替代。如下所示: Map map = new HashMap() {   {   put("Name", "Unmi");   put("QQ", "1125535");   } }; 好处很明...

Airship
2015/02/28
0
0
Java反序列化漏洞的原理分析

  *本文原创作者:Moonlightos,本文属FreeBuf原创奖励计划,未经许可禁止转载   世界上有三件事最难:      把别人的钱装进自己的口袋里   把自己的想法装进别人的脑袋里   让自...

FreeBuf
05/04
0
0
阿里巴巴菜鸟Java一面11个问题,你会几个呢?

近日,w3cschool app开发者头条上分享了阿里菜鸟Java程序员一些面试题。 这吸引了不少程序员小伙伴们的注意。 在分享阿里菜鸟Java程序员面经前,来看下Java面试一些面试经验分享: 0、Java高...

W3Cschool
04/03
0
0
并发编程(二):非线程安全集合类

前言 线程不安全的集合类 ArrayList: 结果一: 结果二: 抛出异常:ArrayIndexOutofBoundsException异常; 现象:出现null值; 出现输出不全的现象; 抛出异常; 原因: ArrayList中的add方...

mengdonghui123456
2017/08/14
0
0
java虚拟机内存监控工具jps,jinfo,Jstack,jstat,jmap,jhat使用

基于Sun HotSpot JVM 这里将介绍几款sun hotspot jvm 自带的监控工具: 请确保java_home/bin配置到path环境变量下,因为这些工具都在jdk的bin目录下 jps(JVM Process Status Tool):JVM机进程...

我类个擦
2014/09/12
0
1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

百度云iOS架构师在职场中的忠告

1.工具不能代替思考 在我多年的咨询工作和与许多组织和管理者的共事中,我发现了修复问题的共同套路,那就是管理人员相信工具可以“解决”给出的问题。当问题域被理解透彻,并且不可能有很多...

_小迷糊
22分钟前
0
0
Java基础——异常

声明:本栏目所使用的素材都是凯哥学堂VIP学员所写,学员有权匿名,对文章有最终解释权;凯哥学堂旨在促进VIP学员互相学习的基础上公开笔记。 异常处理: 可以挖很多个陷阱,但是不要都是一样...

凯哥学堂
35分钟前
0
0
180723-Quick-Task 动态脚本支持框架之结构设计篇

文章链接:https://liuyueyi.github.io/hexblog/2018/07/23/180723-Quick-Task-动态脚本支持框架之结构设计篇/ Quick-Task 动态脚本支持框架之结构设计篇 相关博文: 180702-QuickTask动态脚本...

小灰灰Blog
38分钟前
0
0
SBT 常用开发技巧

SBT 一直以来都是 Scala 开发者不可言说的痛,最主要的原因就是官方文档维护质量较差,没有经过系统的、循序渐进式的整理,导致初学者入门门槛较高。虽然也有其它构建工具可以选择(例如 Mill...

joymufeng
42分钟前
0
0
HBase in Practice - 性能、监控及问题解决

李钰(社区ID:Yu Li),阿里巴巴计算平台事业部高级技术专家,HBase开源社区PMC&committer。开源技术爱好者,主要关注分布式系统设计、大数据基础平台建设等领域。连续4年基于HBase/HDFS设计和...

中国HBase技术社区
43分钟前
1
0
ES18-JAVA API 批量操作

1.批量查询 Multi Get API public static void multiGet() {// 批量查询MultiGetResponse response = getClient().prepareMultiGet().add("my_person", "my_index", "1")// 查......

贾峰uk
48分钟前
0
0
SpringBoot2.0使用health

1,引入actuator <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-actuator</artifactId></dependency> 2,application.properties ......

暗中观察
55分钟前
0
0
阿里巴巴Java开发规约

###编程规约 命名风格 【强制】代码中的命名均不能以下划线或美元符号开始,也不能以下划线或美元符号结束 【强制】代码中的命名严禁使用拼音与英文混合的方式,更不允许直接使用中文的方式。...

简心
59分钟前
0
0
如何用TypeScript来创建一个简单的Web应用

转载地址 如何用TypeScript来创建一个简单的Web应用 安装TypeScript 获取TypeScript工具的方式: 通过npm(Node.js包管理器) npm install -g typescript 构建你的第一个TypeScript文件 创建...

durban
今天
0
0
分享好友,朋友圈自定义分享链接无效

这个问题是微信6.5.6版本以后,修改了分享规则:分享的连接必须在公众号后台设定的js安全域名内

LM_Mike
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部