文档章节

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

BKC
 BKC
发布于 2016/07/11 10:27
字数 577
阅读 550
收藏 2

        首先需要明白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 代码到 Java 堆

从 Java 代码到 Java 堆 分析是一种美德,PS原文地址:http://www.ibm.com/developerworks/cn/java/j-codetoheap/ 理解和优化您的应用程序的内存使用 本文将为您提供 Java™ 代码内存使用情况...

北极之北
2016/03/10
568
3
java 集合类Array、List、Map区别和联系

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

五大三粗
2015/02/27
0
0
最近一次蚂蚁金服Java面试经历!稳妥了!

电话一面 1、自我介绍、自己做的项目和技术领域 2、项目中的监控:那个监控指标常见的哪些? 3、微服务涉及到的技术以及需要注意的问题有哪些? 4、注册中心你了解了哪些? 5、consul 的可靠...

Java干货分享
2018/10/26
0
0
Java:HashMap和Hashset的实现

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

樂天
2015/06/28
0
2
【JAVA集合框架二 】java集合框架容器 java框架层级 继承图结构 集合框架的抽象类 集合框架主要实现类

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

noteless
2018/07/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

echarts实现中国地图

最近项目中有个需求:在地图上展示各省市的数据分布,像这样: 项目中接入的图表展示工具是echart,查了echart官网,发现并没有中国地图相关的实现,唯一接近的,只有香港18区人口密度。没办...

Funcy1122
16分钟前
0
0
持续集成工具Jenkins结合SVN的安装和使用

持续集成工具Jenkins结合SVN的安装和使用 2018年06月08日 11:30:23 止步前行 阅读数:2932 版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/zxd1435513775/ar...

linjin200
23分钟前
0
0
ES6 对象的解构赋值

基本用法 1.等号右边如果不是数组,将会报错(不是可遍历结构) 2.解构赋值 var, let, const命令声明均适用 3.set结构也可解构赋值(具有Iterator接口,可采用数组形式结构赋值) set解构:任何...

Jack088
25分钟前
0
0
微信小程序富文本table超出宽度处理

一、微信小程序富文本table超出宽度处理 处理思路: 使用正则删除table中的width属性。 //去除table的宽度content = content.replace(/<table[^>]*>/gi, function (match, capture) { ...

tianma3798
27分钟前
0
0
阿里云全站加速DCDN全面支持WebSocket协议

WebSocket协议可以为网站和应用提供真正的双向通信,具有控制开销、保持连接状态、更强实时性、更好的压缩效果等优点,是当下低延时应用最常采用的一种技术协议。为了更好的满足客户在实时通...

阿里云官方博客
28分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部