文档章节

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

BKC
 BKC
发布于 2016/07/11 10:27
字数 577
阅读 538
收藏 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:HashMap和Hashset的实现

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

樂天
2015/06/28
0
2
java 集合类Array、List、Map区别和联系

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

五大三粗
2015/02/27
0
0
Java高级程序员面试大纲——错过了金三,你还要错过银四吗

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

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

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

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

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

java高级架构牛人
04/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

js的

<%@ taglib uri="http://java.sun.com/jsp/jstl/core" prefix="c" %> <c:forEach items="${topics}" var="item" varStatus="status"> </c:forEach> 注意 c:forEach E大写 varStatus ......

踏破铁鞋无觅处
36分钟前
2
0
带你走进java集合之ConcurrentHashMap

一、概述 上一篇文章《带你走进java集合之HashMap》分析了HashMap的实现原理,重点分析了HashMap是怎么样的一种数据结构,以及如何去插入,查询,扩容等操作。相信经过上一篇文章的学习,大家...

木木匠
37分钟前
1
0
spring-boot 热加载实现替换

参考资料 1、spring-boot 热加载实现替换

哎小艾
39分钟前
1
0
kotlin使用spring mvc(二)

使用FilterRegistrationBean注册Filter 使用WebFilter配置过滤器的缺点是不可以对过滤器进行排序,但是使用FilterRegistrationBean可以设置Filter执行的顺序 编写过滤器 class CustomFilter...

weidedong
40分钟前
0
0
Qt那些事0.0.5

碰到了中文乱码问题。 虽然是自己做了件令自己都不齿的事情,但是情急之下,暂且如此:将中文硬编码进代码中。 我也想通过tr+qm翻译进行转换,但是难过的是,tr之后,找不到或者不起作用。这...

Ev4n
42分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部