`
美丽的小岛
  • 浏览: 309304 次
  • 性别: Icon_minigender_1
  • 来自: 大连
社区版块
存档分类
最新评论

Hash求不成功查找<转>

 
阅读更多

哈希表查找不成功怎么计算?

解答:先建好表,然后可以算出每个位置不成功时的比较次数之和,再除以表空间个数!
例如:散列函数为hash(x)=x MOD 13,用线性探测,建立了哈希表之后,如何求查找不成功时的平均查找长度!?

     地址: 0   1   2   3   4   5   6   7   8   9   10   11   12

     数据: 39  12  28  15  42  44   6  25       36      38

  成功次数: 1   3   1   2   2   1   1   9           1        1

不成功次数: 9   8   7   6   5   4   3   2   1   1    2   1    10

查找成功时的平均查找长度:ASL=(1+3+1+2+2+1+1+9+1+1)/10 =2.2

查找不成功时的平均查找长度:ASL=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54

说明:

n个位置不成功时的比较次数为,第n个位置到第1个没有数据位置的距离。

至少要查询多少次才能确认没有这个值。

1 查询hash(x)=0,至少要查询9次遇到表值为空的时候,才能确认查询失败。

2 查询hash(x)=1,至少要查询8次遇到表值为空的时候,才能确认查询失败。

3 查询hash(x)=2,至少要查询7次遇到表值为空的时候,才能确认查询失败。

4 查询hash(x)=3,至少要查询6次遇到表值为空的时候,才能确认查询失败。

5 查询hash(x)=4,至少要查询5次遇到表值为空的时候,才能确认查询失败。

6 查询hash(x)=5,至少要查询4次遇到表值为空的时候,才能确认查询失败。

7 查询hash(x)=6,至少要查询3次遇到表值为空的时候,才能确认查询失败。

8 查询hash(x)=7,至少要查询2次遇到表值为空的时候,才能确认查询失败。

9 查询hash(x)=8,至少要查询1次遇到表值为空的时候,才能确认查询失败。

10)查询hash(x)=9,至少要查询1次遇到表值为空的时候,才能确认查询失败。

11)查询hash(x)=10,至少要查询2次遇到表值为空的时候,才能确认查询失败。

12)查询hash(x)=11,至少要查询1次遇到表值为空的时候,才能确认查询失败。

13)查询hash(x)=12,至少要查询10次遇到表值为空(循环查询顺序表)的时候,才能确认查询失败。

http://hi.baidu.com/liumingkong/blog/item/c6a9fc8c97352d04b21bba60.html

 

哈希表查找不成功的平均查找长度怎么计算?
解答:先建好表,然后可以算出每个位置不成功时的比较次数之和,再除以表空间个数!

例如:散列函数为hash(x)=x MOD 11,用线性探测,建立了哈希表之后,如何求查找不成功时的平均查找长度!?

地址:0 1 2 3 4 5 6 7 8 9 10
数据:33 1 13 12 34 38 27 22

成功次数:1 1 1 3 4 1 2 8
不成功次数:9 8 7 6 5 4 3 2 1 1 1

查找成功时的平均查找长度:ASL=(1+1+1+3+4+1+2+8)/8 =47/8
查找不成功时的平均查找长度:ASL=(9+8+7+6+5+4+3+2+1+1+1)/11

(注:求查找不成功时的平均查找长度,一般情况下分母为表长,但精确地讲是表长的有效位个数。

例如对于字符串来说,散列函数为hash(x)=x/2x为字符的第一个字母在字母表的序号,表长即使为16,该分母也应取14,因为最大的hash(Z)=26/2=13,即只有0~1314个有效位置有效。)

说明

n个位置不成功时的比较次数为,第n个位置到第1个没有数据位置的距离。

如:第0个位置到第1个没有数据位置(8)的距离为9.

 

看严蔚敏的课本第261面中间:分析长度为M的哈西表中添装有N个纪录时查找不成功的平均查找长度这个问题,相当于在这个表中再添加第N+1个纪录时所需比较的次数的期望值。
比如:当你MOD11时,第N+1个数MOD后的值可能是0~10。当它是0时就要放在第一个位置,如果第一个位置有纪录,就要处理冲突,向后移到一个空位置,记住移动的位置数,就是在0位置上查找不成功的值,然后分别分析在1~10位置上的值,最后相加除以11。(注意:不是除表长M

http://blog.sina.com.cn/s/blog_8bad503d01011f6y.html

分享到:
评论

相关推荐

    redis常用命令

    - **命令**: `hmset &lt;key&gt; &lt;field1&gt; &lt;value1&gt; &lt;field2&gt; &lt;value2&gt; ...` - 批量设置哈希表中多个字段的值。 **增加哈希表中字段的整数值** - **命令**: `hincrby &lt;key&gt; &lt;field&gt; &lt;increment&gt;` - 增加哈希表中字段的...

    freemarker总结

    除了无法访问它的大小和不能使用索引来获得它的子变量:集合可以看作只能由&lt;#list...&gt;指令使用的受限sequences。 5、 方法:通过传递的参数进行计算,以新对象返回结果 方法变量通常是基于给出的参数计算值在数据...

    Java软件开发实战 Java基础与案例开发详解 11-3 Set接口实现类 共19页.pdf

    TreeSet&lt;Integer&gt; set4 = new TreeSet&lt;&gt;(new TreeSet&lt;&gt;(Arrays.asList(1, 2, 3))); // 添加有序集合元素 ``` **代码示例:** ```java import java.util.TreeSet; public class TreeSetTest { public static void...

    php 验证用户是否登录

    &lt;input type="text" id="username" name="username" required&gt;&lt;br&gt; &lt;label for="password"&gt;密码:&lt;/label&gt; &lt;input type="password" id="password" name="password" required&gt;&lt;br&gt; &lt;input type="submit" value=...

    数据结构实验六(二分查找、Hash查找)题目和源程序

    - 如果 `key == ST.elem[mid]`,则查找成功,返回 `mid`。 - 如果 `key &lt; ST.elem[mid]`,则在数组的左半部分重复步骤2和3。 - 如果 `key &gt; ST.elem[mid]`,则在数组的右半部分重复步骤2和3。 4. **终止条件:** ...

    哈希表查找成功和不成功的算法.pdf

    计算不成功查找的平均查找长度时,注意到每个位置不成功时的比较次数等于从当前位置到第一个空位置的距离。所以,我们可以得到不成功查找的平均查找长度为`(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54`。 在2010年的研究...

    binary_hash.rar_二分查找

    其基本思想是将数组分成两半,然后比较中间元素与目标值,如果目标值等于中间元素,则查找成功;如果目标值小于中间元素,则在左半部分数组中继续查找;如果目标值大于中间元素,则在右半部分数组中继续查找。这个...

    sas hash简介与实例.pdf

    * REF:如果查找关键字段成功则无操作,如果查找不成功则添加关键字段,相当于 find 和 add 的结合。 * SETCUR:规定一个关键字段,用于开始迭代。通常在对数据排序后使用。 * SUM:计算并返回相同 key 下指定计数...

    jQuery api (docs)1.1.2

    - **示例**: `var elem = $('&lt;div&gt;Hello World&lt;/div&gt;')` 将会创建一个新的 `&lt;div&gt;` 元素,并将其内容设置为 “Hello World”。 **2. $(Element | Array&lt;Element&gt; elems) returns jQuery** - **功能**: 此方法可以将...

    折半查找、二叉排序树、链式哈希表的建立与查找

    - 如果 `mid` 处的值等于目标值,则查找成功。 - 如果 `mid` 处的值小于目标值,则在 `[mid + 1, high]` 范围内继续查找。 - 如果 `mid` 处的值大于目标值,则在 `[low, mid - 1]` 范围内继续查找。 3. **循环...

    数据结构 查找

    if (target &lt; root-&gt;data) { return search(root-&gt;left, target); // 在左子树中查找 } else { return search(root-&gt;right, target); // 在右子树中查找 } } ``` **4.4 运行结果** 展示实际运行程序的结果...

    IT笔试面试--链地址Hash表的代码实现,运行正确+详细注释

    链地址Hash表是一种常用的Hash算法,它的优点在于可以快速查找数据,同时占用的内容空间也非常小。 链地址Hash表的实现可以分为四个步骤: 1. 定义Hash表和基本数据节点 在这里,我们定义了一个Hash表的结构体...

    hash函数学生信息管理

    cout &lt;&lt; "删除成功" &lt;&lt; endl; } else cout &lt;&lt; "未找到要删除的学生信息" &lt;&lt; endl; return P; } ``` #### 3.4 查找操作 查找操作也是基于哈希函数定位到链表,然后遍历链表查找匹配的节点: ```cpp Stu* ...

    Test_cpp:C ++测试代码

    由于性能优势,使用面广,有许多第三方类库提供了支持,如MSVC中的&lt;hash&gt;和Boost中的&lt;boost&gt;,后来Boost的unordered_map被吸纳进了C ++ 11标准。 (1)1.两数之和 译文描述:给你一个数组,要在多个中找到两个数字a...

    数据结构几种查找算法

    本主题将深入探讨几种常见的查找算法,包括二分查找(Binsearch)、二叉搜索树(BSTree)、哈希查找(Hash)以及顺序查找(Seqsearch)。这些算法在不同的场景下有着各自的优点和适用性,理解并掌握它们对于优化程序...

    数据结构-查找-实验报告.docx

    实验报告涵盖了三种主要的查找方法:顺序表查找、树表查找(包括二叉排序树查找与平衡二叉树查找)以及Hash表查找。通过这些实验,学生将能够熟练地使用C/C++语言来实现这些查找算法,并能够在实际应用场景中灵活...

    Comparing the Performance of Distributed Hash Tables Under Churn

    综上所述,本文通过构建一个统一的框架,成功地对不同DHT协议在面对成员变动时的性能进行了全面而深入的比较。这种比较有助于理解在动态网络环境中,如何有效地平衡查找时间和通信成本,以及哪些设计决策对提高整体...

    散列表C++实现(不同装载因子的开放寻址法和链表法比较)

    该程序显示了从开始到全部插入,再到全部成功查找,最后全部删除的过程,并统计和各项数据。 2.open_hash-onetime.exe:是使用开放地址法的散列程序,它是在n=80000,m=100000,即在装载因子是0.8的情况下测试的。该...

Global site tag (gtag.js) - Google Analytics