`

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方法效率比较,Set.retainAll方法效率较高

    set_irq_affinity

    /sbin/set_irq_affinity eth1 可以进行中断绑定指定的cpu,提高网卡收包效率 把下面“eth1” 修改成对应的网卡名称 irq=$(cat /proc/interrupts | grep eth1 | cut -d':' -f 1); echo $irq for i in $irq ; do sudo...

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

    主要介绍了Python 中list ,set,dict的大规模查找效率对比详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下

    完美拼SET脚本.rar

    上传个genesis2000用的拼set的脚本,这有助于genesis2000的自动化,提高CAM的制作效率

    ASAP2Tool-Set_14.0_Manual_EN.pdf

    此文档是Vector的A2L编辑工具APAP2 Tool Set的使用手册,基于C代码直接自动生成A2L文件,效率高。

    Level Set 图像分割的MFC实现

    找了很久没找到level set算法的c语言实现,就按照作者原文自己写了一个,效率不高,大图像处理慢 ps:程序是基于opencv的,vc6下mfc实现 ps2:写的时候opencv不是默认安装目录,下载下来要重新设置一下

    信息素养:效率提升与终身学习的新引擎信息素养:效率提升与终身学习的新引擎05-思维导图_113_113.pdf

    信息素养:效率提升与终身学习的新引擎信息素养:效率提升与终身学习的新引擎05-思维导图_113_113.pdf

    NSET/MSET算法代码

    NSET/MSET(Nonlinear State Estimation/Modeling and Predictive Diagnosis)是一种...在工业领域,它可以应用于复杂的制造过程控制和设备监测,提高生产效率和设备可靠性。在能源领域,它可以用于电力系统的运行状态

    myeclipse 自动添加get、set方法注释(含步骤和导入的xml文件)

    myeclipse自动添加get、set方法注释(含步骤和导入的xml文件)解决了生成构造方法、类等get set 时手动描述方法注释的繁琐操作、增加开发效率、便于解读 。

    List、Set、Map的特点及遍历方法

    List、Set、MapList与Set集合的区别List、Map、Set三个接口,存取元素...set检查元素效率低下,删除和插入的效率高,不会引起元素位置改变 list和数组相似,list可实现动态增长,查找元素效率高,插入和检查的效率低,会

    关于Django ForeignKey 反向查询中filter和_set的效率对比详解

    而当我们需要反向查询 A 中某个具体实例所关联的 B 时,可能会用到 A.B_set.all() 或 B.objects.filter(A) 这两种不同的方法。 不知道大家有没有也想过一个问题:当网站实际上线后,SEO强调页面加载速度,而当面对...

    javascript模拟map,set类,用起来挺方便的!!!

    1.可以用null,boolean,string,number,array,Date,自定义类的对象作键值,数组里的元素必须是实现equals方法的类型,而且数组里含有null,undefined,NaN会...2.数组维数尽量不要太多,程序里递归检查数组元素,会影响效率

    c++ STL库容器之集合set代码实例

    它底层使用平衡的搜索树——红黑树实现,插入删除操作时仅仅需要指针操作节点即可完成,不涉及到内存移动和拷贝,所以效率比较高。set,顾名思义是“集合”的意思,在set中元素都是唯一的,而且默认情况下会对元素...

    java集合类的效率测试

    我写的关于set集合和list集合相关性能测试,linkedList ArrayList HashSet 等类的增删改查性能测试

    ordered-set:记住条目顺序的可变集。 Python缺少的数据类型之一

    在OrderedSet中查找条目的索引,或通过其索引查找条目,效率很高。 为了帮助解决该用例, .add()方法返回添加项的索引,无论它是否已经在集合中。 >>> letters.index('r') 2 >>> letters[2] 'r' >>> letters.add('r...

    空间自适应的快速粒子Level Set方法 (2010年)

    快速粒子level set方法(FPLS)是一种改进的level set方法,既具有较高的界面追踪精度,又有较高的计算效率.将其与自适应网格结合起来,提出了一种基于树型结构空间自适应的快速粒子level set方法(SA-FPLS)通过在交...

    ES6中Set和Map数据结构,Map与其它数据结构互相转换操作实例详解

    本文实例讲述了ES6中Set和Map...①Array的indexOf方法比Set的has方法效率低下 ②Set不含有重复值(可以利用这个特性实现对一个数组的去重) ③Set通过delete方法删除某个值,而Array只能通过splice。两者的使用方便程度

    64-ia-32--instruction-set-reference-HTML.rar

    对于英语不太好的,或者一般的朋友来说,快速进入学习-入门,快速查阅搞清来龙去脉极为重要,因为学习也需要效率。转html实际有两个好处,第一,依然可以阅读英文版;第二,可以借助谷歌等浏览器翻译转换。 特意献...

    day016-list和set笔记以及代码.zip

    如果是不能存放重复的元素,用Set接口下的实现类 HashSet:如果没有任何排序要求,用HashSet,因为效率高 TreeSet: 如果有排序要求用TreeSet, 如果是自然排序,需要元素实现Comparable接口,重写compareTo方法 ...

Global site tag (gtag.js) - Google Analytics