`

set 效率问题

 
阅读更多

为啥要用HashSet?

      假如我们现在想要在一大堆数据中查找X数据。LinkedList的数据结构就不说了,查找效率低的可怕。ArrayList哪,如果我们不知道X的位置序号,还是一样要全部遍历一次直到查到结果,效率一样可怕。HashSet天生就是为了提高查找效率的。

 

hashCode 散列码

      散列码是由对象导出的一个整数值。在Object中有一个hashCode方法来得到散列码。

HashSet 如何add机制

        假如我们有一个数据(散列码76268),而此时的HashSet有128个散列单元,那么这个数据将有可能插入到数组的第108个链表中(76268%128=108)。但这只是有可能,如果在第108号链表中发现有一个老数据与新数据equals()=true的话,这个新数据将被视为已经加入,而不再重复丢入链表。

       那么数据的散列码我知道,但HashSet的散列单元大小如何指定那?

       Java默认的散列单元大小全部都是2的幂,初始值为16(2的4次幂)。假如16条链表中的75%链接有数据的时候,则认为加载因子达到默认的0.75。HahSet开始重新散列,也就是将原来的散列结构全部抛弃,重新开辟一个散列单元大小为32(2的5次幂)的散列结果,并重新计算各个数据的存储位置。以此类推下去.....

 

 为什么HashSet查找效率提高了。

      知道了HashSet的add机制后,查找的道理一样。直接根据数据的散列码和散列表的数组大小计算除余后,就得到了所在数组的位置,然后再查找链表中是否有这个数据即可。

      查找的代价也就是在链表中,但是真正一条链表中的数据很少,有的甚至没有。几乎没有什么迭代的代价可言了。所以散列表的查找效率建立在散列单元所指向的链表中的数据要少 。

转自http://blog.sina.com.cn/s/blog_59dbaf860100g6pz.html

分享到:
评论

相关推荐

    List和Set使用retainAll方法的比较

    本文将深入探讨List和Set在使用`retainAll`方法时的效率差异,并通过`ListAndRetainAll.java`和`SetAndRetainAll.java`两个示例代码来具体分析。 首先,让我们了解`retainAll`方法的基本概念。`retainAll`是Java...

    Mysql中FIND_IN_SET()和IN区别简析

    需要注意的是,`FIND_IN_SET()` 不会利用索引来提高查询效率,尤其是在处理大量数据时,这可能导致性能下降。 例如,在创建的`test`表中,`list`字段存储了一个逗号分隔的字符串列表。当执行以下查询时: ```sql ...

    map和set的异同

    3. **高效性**:由于红黑树的特性,使得`map`和`set`在插入、删除和查找操作上都具有较高的效率。 4. **迭代器**:`map`和`set`支持迭代器遍历,使得用户可以方便地访问容器中的元素。 #### 四、不同点 1. **数据...

    oracle中常用的set命令

    SET FEEDBACK OFF 命令用于关闭回显本次 SQL 命令处理的记录条数的显示,以便提高脚本的执行效率。 SET TERMOUT OFF SET TERMOUT OFF 命令用于关闭显示脚本中的命令的执行结果,以便提高脚本的执行效率。 SET ...

    SETRES

    此外,不正确的使用SETRES可能会导致显示问题,如屏幕黑屏,所以在执行前最好备份当前的显示设置。 在标签“None”的情况下,可能意味着这个工具或技术比较小众,或者它可能是用户自定义的,没有被归类到特定的技术...

    DC工具中set_dont_touch和set_size_only的区别.doc

    在集成电路设计领域,DC(Design Compiler)是一...而如果希望优化 cell 的驱动能力以提高效率,同时保持功能一致性,那么 `set_size_only` 更为适用。设计师需要根据设计的具体要求和性能指标,谨慎地使用这两个命令。

    code of Levelset

    DRLSE可能是这样一个框架,利用神经网络预测levelset函数的演化,适用于实时或复杂场景的界面追踪问题。 总的来说,Levelset方法是一种强大的工具,它在处理与界面演化相关的各种问题时展现出极大的灵活性和准确性...

    SETMAIN中控门禁配置工具

    数据同步有助于实时监控和事后追溯,提高安全管理效率。 6. **调试与故障排除** 在Linux环境中,调试命令行工具如`串口调试助手`和`网络调试工具`是必不可少的。通过发送特定指令,用户可以测试设备响应,排查通信...

    IPset用来修改保存IP地址

    在处理大量IP地址时,IPset的效率远高于传统的iptables规则,因为它将多个IP地址的处理合并为一个操作,减少了内核的上下文切换次数。这对于网络安全、负载均衡、DDoS防御等场景非常有用。 总的来说,IPset是Linux...

    set容器对类进行排序

    在C++编程中,`set`容器是STL(Standard Template Library,标准模板库)的一部分,它是一个关联容器,提供了唯一的、有序的元素...在实际编程中,根据项目需求灵活选择合适的方法,可以极大地提高代码的可读性和效率。

    Python 中list ,set,dict的大规模查找效率对比详解

    实验结果表明,在进行单次查找操作时,set的效率最高,其次是dict,而list的查找效率最低,甚至在实验中出现了list花费了20分钟都没有完成查找的情况。 值得注意的是,虽然dict的查找效率通常非常高,但是它的效率...

    level set 编程书籍

    Level Set方法是一种在计算几何、图像处理、物理模拟等领域广泛应用的数学工具,尤其在界面捕捉方面表现出极高的效率和灵活性。它最初由Osher和Sethian在1988年提出,是解决移动界面问题的一种非局部方法。通过将...

    C++set函数学习

    set容器的元素在内部是按照红黑树的结构进行存储的,这种数据结构保证了插入、删除和查找操作的效率都是对数级别的。 与set不同,multiset允许元素的重复。它和set一样,会自动根据元素的值对存储的元素进行排序。...

    C++_STL之set容器使用方法

    `set`内部通常采用红黑树(一种自平衡的二叉查找树)来实现,这使得它在执行插入、删除和查找等操作时能够保持较高的效率。 #### 二、set容器的基本概念 ##### 1. 元素类型 在`set`容器中,每个元素都有一个特定的...

    计算机视觉数据集-Set14

    在计算机科学尤其是机器学习和深度学习领域,数据集的大小往往直接影响模型的训练效率和泛化能力。Set14因其相对较小的规模而受到青睐,它可以快速训练模型,并在有限的数据上进行有效的性能评估。 Set14包含了14张...

    SetRes 命令行分辨率设置工具

    SetRes 是一个命令行工具,专门用于调整计算机的屏幕分辨率。在没有图形用户界面的情况下,或者需要自动化批量处理分辨率设置...了解如何正确使用它的参数和功能,可以极大地提升工作效率并优化特定场景下的视觉体验。

    SQL_SET.rar_SetSQL_sql_sql set _sql set connectattr_sql set rouc

    在实际工作中,理解和熟练使用这些"SET"命令能够极大地提高数据库管理效率,确保数据处理的准确性和性能。通过阅读这些文档,你可以深入了解不同数据库系统中"SET"命令的用法差异,并且掌握如何根据需求调整会话环境...

    IDEA插件之GET/SET自动生成带模版注释插件

    安装完成后,开发者就可以在IDEA中体验到更加个性化的get/set生成服务,提升开发效率。 总之,"IDEA插件之GET/SET自动生成带模版注释插件"是IDEA的一个实用扩展,它将get/set方法的生成与自定义注释模板结合,使得...

    Set Character Encoding_0.51.zip

    “Set Character Encoding”插件的出现,主要是为了解决某些网页因编码不兼容导致的文字乱码问题。开发人员在调试网页或者访问非UTF-8编码的老旧网站时,可能会遇到这种问题,这时这个插件就能派上用场。用户可以...

    完美拼SET脚本.rar

    在IT行业中,自动化是提升工作效率的关键,特别是在计算机辅助制造(CAM)领域。"完美拼SET脚本.rar" 文件就是这样一个工具,专为Genesis2000系统设计,以实现拼SET过程的自动化。Genesis2000是一款广泛使用的CAM...

Global site tag (gtag.js) - Google Analytics