hash系列集合的性能优化
2019-05-22 06:33:43来源:博客园 阅读 ()
hash系列的集合:
HashSet、LinkedHashSet 采用hash算法决定元素在集合中的存储位置
HashMap、LinkedHashMap、Hashtable 采用hash算法决定key在集合中的存储位置
hash表中可以存储元素的位置,被称为bucket(桶)。
在通常情况下,一个bucket里只存储一个元素,此时性能最好,可根据hashCode直接定位元素所在的bucket,获得元素。
但hash表的状态是open的,在发生hash冲突时,一个bucket中会存储多个元素,这些hash冲突的元素以链表形式存储在一个bucket中:
此时hash表性能会下降,根据hash算法确定bucket位置后,还要遍历链表,找到指定的元素。
如果我们重写了自定义类的hashCode()、equals()则不会出现hash冲突的情况,一个bucket里只会存储一个元素。
hash系列的集合都有以下属性:
- capacity 容量,hash表中bucket的数量
- initial capacity 初始容量,创建hash表时bucket的数量
- size hash表中已装元素的bucket数量
- load factor 负载因子,等于size/capacity,即已装元素的bucket数占总bucket数的比例。0表示空的hash表,0.5表示半满的hash表。
- 负载极限 0~1之间的一个float,表示当前hash表的最大填满程度,即允许的load factor的最大值。
创建hash表时,此hash表的内存就确定了,根据hash算法确定的是元素在此hash表中的位置。
往hash表中添加元素时, 会先找到hash表中空的bucket,根据hash算法确定用哪个空的bucket来存储元素。
load factor较小时,添加元素时很容易找到空的bucket,hash冲突少(因为可用的空bucket很多),存储性能较高;已装元素的bucket少,很容易从中找到指定的元素,查找性能较高;但遍历集合(hash表)时,要过滤掉大量的空bucket,很花时间,所以遍历时比较慢。
当load factor达到设置的负载极限时,会发生rehashing(重哈希/再散列),hash表会自动成倍地增加容量(capacity),将原有的元素都移到新的hash表中(会重新分配存储位置),而此时原有的元素是极多的,这会增加很大的开销。
负载极限设置较高时,节省内存(空桶较少),但添加、查找元素效率较低,时间开销会增大;负载极限较低时,添加、查找元素效率较高,但会增加内存开销。默认为0.75,是时间、空间的折中,我们可根据需要自行设置。
如果我们一开始就知道要存储的元素个数,可以在创建hash表时就指定容量:元素总数/负载极限。这样避免了rehashing,节省了时间开销。且前中期hash表负载会很低,添加、查询效率极高。
hash系列集合都有的3个重载构造函数:
() //无形参,使用默认的capacity、负载极限(0.75)
(int capacity) //指定容量
(int capacity,float 负载极限)
原文链接:https://www.cnblogs.com/chy18883701161/p/10896546.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Spring系列.ApplicationContext接口 2020-06-11
- 与JAVA集合相遇 2020-06-11
- Java笔记:集合 2020-06-10
- logstash系列-入门整理 2020-06-10
- 2020最新IDEA插件大集合,一款能帮助你写代码的工具是多么重 2020-06-09
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash