java中HashSet的去重以及容量扩增原理
博客专区 > BKC 的博客 > 博客详情
java中HashSet的去重以及容量扩增原理
BKC 发表于2年前
java中HashSet的去重以及容量扩增原理
  • 发表于 2年前
  • 阅读 325
  • 收藏 2
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

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

        首先需要明白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。当元素不断增加时,以此类推扩容。

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 2
博文 32
码字总数 35753
×
BKC
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: