江苏龙网

  1. 主页 > 生活百科 > >

java散列实现( 二 )

java散列


操作remove(key)使用于检索操作相同逻辑查找探测序列 。如果找到key，他就将该位置标记为可用 。
操作add(key,value)使用与检索操作类似的逻辑查找探测序列，但它也记录遇到的第一个处于可用状态位置的索引就，如果key未找到，则使用这个位置放置新元素 。
聚集 用线性探测处理冲突导致散列表中成组的连续位置被占用，每个组成为一个聚群，这种现象陈给一次聚集 随着聚群长度的增加，他们可能合并为更大的聚群 。
二次探测开放定址
&emsb;给定的查找键散列到索引k，线性探测将查看从索引k开始的连续位置，而二次探测则另辟途径，考虑索引k + j 2 ( j ≥ 0 ) k+j^2(jgeq0)k+j
2
(j≥0)处的位置，换句话说，它使用索引k、k+1、k+4、k+9…
&emsb;尽管二次探测避免了一次聚集，它可能导致另一种不同的聚集，成为二次聚集 但二次聚集通常不是一个严重的问题 。
二次探测
对于j ≥ 0 jgeq0j≥0 检查散列表中位于原来的散列索引加上j 2 j^2j
2
处的位置，已解决散列过程中的冲突；
如果散列表的长度时素数，则可达到散列表中一半的位置；
避免了一次聚集但可导致二次聚集 。
双散列开放定址
使用第二个散列函数，以依赖于查找键的方式计算这些增量，因此既避免了一次聚集又避免了二次聚集 。
双散列
散列过程中处理冲突的方法为，检查散列表中位于初始散列索引加上由第二个散列函数生成的增量处的位置 。第二个散列函数应该：与第一个散列函数不同；依赖于查找键；具有非0值；
+如果散列表的长度是素数，则可探测到散列表中所有位置 。
+既避免了一次聚集又避免了二次聚集 。
开放定址存在的问题
&ensb;前三种处理冲突的开放定址方案假定每个散列表都处于三种状况之一：被占据、空闲或可用，其中只有空闲位置才含有null 。频繁的插入或删除可能导致散列表中的每一个位置或引用一个当前位置，或引用一个以前的位置 。也就是说散列中只含有少量的词典元素，却没有null的位置 。
链地址
&ensb;使每个位置可以表示不只一个值 。这样的位置称为桶 。一旦新的查找键被映射到一个特定位置，就简单的将这个键和他相关联的值放入桶中 。为了找到这个键进行散列，找到桶，然后查看桶中的键-值对 。在删除一个元素时，从它的桶中找到并删除 。
链地址提供了一种高效且简单的处理冲突的方法，然而因为改变了散列的结构，所以链地址比开放定址需要更多的内存 。

【java散列实现】


推荐阅读


上一篇：土家族哭嫁的文化内涵 土家族有哪些民俗风情

下一篇：如何安全地对电脑系统进行优化，使电脑运行速度变快