Java集合框架 -- 03 hash算法在集合中的应用及分析

对于HashSet及其子类而言,它们采用hash算法来决定集合中元素的存储位置,并通过hash算法来控制集合的大小;

hash表里可以存储元素的位置被称为“桶”(bucket),一般而言,单个桶里存储一个元素性能是最优的。但有时会
发生冲突,即两个元素的hash值一样,即它们计算出来的存储位置一样了,此时就要解决冲突问题,那么解决冲突的
方法主要有:

开放定址法
再散列函数法
链地址法(Java集合中采用的这种方式)
公共溢出区

hash表包含的属性:
容量(capacity): hash表中桶的数量
初始化容量:创建hash表时桶的数量。HashMap和HashSet都允许再构造器中指定初始容量
尺寸(size): hash表中当前的存储数量
负载因子(装填因子):"size/capacity"的比值,为0时,表示空的hash表,0.5表示半满的hash表
负载极限:是一个0-1的数值,决定了hash表的最大填满程度,当负载因子达到了指定的负载极限时,hash表会自动成倍的增加容量(桶的数量),并将原有的对象重新分配到新的桶内,这个过程为rehashing

注意:
    这个负载极限的取值会影响性能,过大过下都不好,一把取值0.75较为合理。过大虽然能降低hash表所占用的内存时间,但会增加
    查询数据的时间开销(因此,冲突多了,挂载的分支链表也就多了长了,从而查找性能不好);过小,尽管
    会提高查询性能,但容易发生rehashing,即增加hash表所占用的内存开销。
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 实际上,HashSet 和 HashMap 之间有很多相似之处,对于 HashSet 而言,系统采用 Hash 算...
    曹振华阅读 7,216评论 1 37
  • title: java集合框架学习总结 tags:集合框架 categories:总结 date: 2017-03...
    行径行阅读 5,679评论 0 2
  • HashMap 是 Java 面试必考的知识点,面试官从这个小知识点就可以了解我们对 Java 基础的掌握程度。网...
    野狗子嗷嗷嗷阅读 11,683评论 9 107
  • 我来到你的世界 带着期盼 带着渴望 跟随着一份灵魂的感觉 意念播撒 爱 已出发 没人能告诉我结局是什么 一路踉跄前...
    阳光姐姐何姐阅读 2,444评论 0 0
  • 突然觉得我有哥可是没有这种感觉啊。我甚至是看完了这篇文章才想起来自己也是有个大两岁的亲哥的。唉,不知道是你的悲哀还...
    胖球66阅读 2,732评论 0 1

友情链接更多精彩内容