- 浏览: 308328 次
- 性别:
- 来自: 大连
文章分类
- 全部博客 (272)
- java (42)
- c (49)
- 算法 (29)
- 汇编语言 (3)
- 字符集 (3)
- error (3)
- 搜索引擎 (2)
- 互联网 (18)
- linux (12)
- 网络 (20)
- VMWare (1)
- 面试 (7)
- c++ (55)
- 设计模式 (3)
- db (9)
- office (2)
- FS (1)
- rest (3)
- Ajax (2)
- Spring (2)
- Hibernate (3)
- matlab (1)
- load balancing (8)
- 分布式计算 (2)
- 易语言 (1)
- apache tomcat (1)
- 测试 (1)
- 数据结构 (5)
- 数学 (13)
- 服务器 (9)
- 读后感 (4)
- 好书介绍 (1)
- script (3)
- wordpress (2)
- delphi (21)
- pascal (8)
- xml (3)
- 趣味 (1)
- PHP (3)
- python (13)
- DLL (4)
- openGL (8)
- windows (2)
- QT (28)
- django (7)
- jquery (1)
- 数据挖掘 (7)
- nginx (1)
- js (1)
- mac (1)
- hadoop (3)
- 项目管理 (1)
- 推荐系统 (1)
- html (1)
最新评论
-
晴天1234:
related remove:attention.ibus和u ...
UBUNTU的默认root密码是多少,修改root密码 -
美丽的小岛:
美丽的小岛 写道如上配置好就得了。提示没有OpenGl.dll ...
OpenGL学习入门之VS2010环境配置 [转] -
美丽的小岛:
如上配置好就得了。提示没有OpenGl.dll之类的,再增加入 ...
OpenGL学习入门之VS2010环境配置 [转] -
美丽的小岛:
主要是理清哪两个对象之间的关系,是信号与所有槽的关系或者是槽与 ...
QT之DisConnect -
美丽的小岛:
LPCTSTR类型:L表示long指针 这是为了兼容Windo ...
QString与各种字符串之间的转化
哈希表查找不成功怎么计算?
解答:先建好表,然后可以算出每个位置不成功时的比较次数之和,再除以表空间个数!
例如:散列函数为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/2,x为字符的第一个字母在字母表的序号,表长即使为16,该分母也应取14,因为最大的hash(Z)=26/2=13,即只有0~13的14个有效位置有效。)
说明:
第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
发表评论
-
Apriori算法
2014-12-15 12:56 667http://blog.csdn.net/lizhengn ... -
编辑距离算法
2014-08-14 00:02 975字符串编辑距离: 是一种字符串之间相似度计算的方法。给定两个 ... -
八叉树及K-D树的应用和实现
2014-07-31 19:51 21531. 八叉树、k-d树的原理 2. 八叉树、k-d树的应用 ... -
四叉树与八叉树
2014-07-31 19:37 1408前序 四叉树或四元树也被称为Q树(Q-Tree)。四叉树 ... -
自行车往哪个方向行驶? <转>
2013-05-09 12:57 915文章转自: http://www.ma ... -
01虫子问题<转>
2013-05-09 12:26 732来自:http://www.cs.cmu.ed ... -
求数组中重复出现次数大于数组总个数一半的数
2013-04-17 21:39 1390变量设计,一个变量,存数num,另一个存这个数出现的次数ti ... -
约瑟夫环(时间复杂度为n)
2013-04-17 21:20 1828一、 题目描述: 约瑟夫环是一个数学的应用问 ... -
不用除法运算符的除法
2013-04-04 09:53 1818题目描述: 给定一数组a[N],我们希望构造数组b [N] ... -
泊松分酒趣题<转>
2013-03-24 11:40 813有一个12品脱(pint)的酒 ... -
二进制与三进制的那些趣题<转>
2013-03-24 11:20 14451. 小明是个卖苹果的 ... -
r-组合
2012-10-29 18:14 1001算法描述而下(来自组合数学): 从r-组合a1a2...ar ... -
全排列的实现(C)
2012-10-24 16:42 1129找工作,笔试经常会出现一个题,怎样生成一个集合内所有元素的全排 ... -
智力题
2012-09-06 16:17 1131不管是找工作还是考公 ... -
插入、堆排序
2012-08-21 21:15 0排序的最初数据结构是在线性表的基础上的,线性表这个东西就好像很 ... -
排序方法比较<转>
2012-08-21 20:50 833根据排序的原则,内排序可以分为: 插入排序 交换排序 ... -
基于二进制的集合(c语言)
2012-08-17 17:20 1021用C去操作集合,有时候觉得十分的麻烦,不过,集合又一定要用。苦 ... -
位运算<转>
2012-08-15 20:40 970什么是位运算? ... -
位运算求解N皇后的过程
2012-08-14 21:14 11578皇后可以用位运算来求,有点好奇的,不过,位运算这个强大的逻 ... -
一些hash函数实现<转>
2012-08-14 11:53 1312/** * Hash算法大全<br> * ...
相关推荐
- **命令**: `hmset <key> <field1> <value1> <field2> <value2> ...` - 批量设置哈希表中多个字段的值。 **增加哈希表中字段的整数值** - **命令**: `hincrby <key> <field> <increment>` - 增加哈希表中字段的...
除了无法访问它的大小和不能使用索引来获得它的子变量:集合可以看作只能由<#list...>指令使用的受限sequences。 5、 方法:通过传递的参数进行计算,以新对象返回结果 方法变量通常是基于给出的参数计算值在数据...
TreeSet<Integer> set4 = new TreeSet<>(new TreeSet<>(Arrays.asList(1, 2, 3))); // 添加有序集合元素 ``` **代码示例:** ```java import java.util.TreeSet; public class TreeSetTest { public static void...
<input type="text" id="username" name="username" required><br> <label for="password">密码:</label> <input type="password" id="password" name="password" required><br> <input type="submit" value=...
- 如果 `key == ST.elem[mid]`,则查找成功,返回 `mid`。 - 如果 `key < ST.elem[mid]`,则在数组的左半部分重复步骤2和3。 - 如果 `key > ST.elem[mid]`,则在数组的右半部分重复步骤2和3。 4. **终止条件:** ...
计算不成功查找的平均查找长度时,注意到每个位置不成功时的比较次数等于从当前位置到第一个空位置的距离。所以,我们可以得到不成功查找的平均查找长度为`(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54`。 在2010年的研究...
其基本思想是将数组分成两半,然后比较中间元素与目标值,如果目标值等于中间元素,则查找成功;如果目标值小于中间元素,则在左半部分数组中继续查找;如果目标值大于中间元素,则在右半部分数组中继续查找。这个...
* REF:如果查找关键字段成功则无操作,如果查找不成功则添加关键字段,相当于 find 和 add 的结合。 * SETCUR:规定一个关键字段,用于开始迭代。通常在对数据排序后使用。 * SUM:计算并返回相同 key 下指定计数...
- **示例**: `var elem = $('<div>Hello World</div>')` 将会创建一个新的 `<div>` 元素,并将其内容设置为 “Hello World”。 **2. $(Element | Array<Element> elems) returns jQuery** - **功能**: 此方法可以将...
- 如果 `mid` 处的值等于目标值,则查找成功。 - 如果 `mid` 处的值小于目标值,则在 `[mid + 1, high]` 范围内继续查找。 - 如果 `mid` 处的值大于目标值,则在 `[low, mid - 1]` 范围内继续查找。 3. **循环...
if (target < root->data) { return search(root->left, target); // 在左子树中查找 } else { return search(root->right, target); // 在右子树中查找 } } ``` **4.4 运行结果** 展示实际运行程序的结果...
链地址Hash表是一种常用的Hash算法,它的优点在于可以快速查找数据,同时占用的内容空间也非常小。 链地址Hash表的实现可以分为四个步骤: 1. 定义Hash表和基本数据节点 在这里,我们定义了一个Hash表的结构体...
cout << "删除成功" << endl; } else cout << "未找到要删除的学生信息" << endl; return P; } ``` #### 3.4 查找操作 查找操作也是基于哈希函数定位到链表,然后遍历链表查找匹配的节点: ```cpp Stu* ...
由于性能优势,使用面广,有许多第三方类库提供了支持,如MSVC中的<hash>和Boost中的<boost>,后来Boost的unordered_map被吸纳进了C ++ 11标准。 (1)1.两数之和 译文描述:给你一个数组,要在多个中找到两个数字a...
本主题将深入探讨几种常见的查找算法,包括二分查找(Binsearch)、二叉搜索树(BSTree)、哈希查找(Hash)以及顺序查找(Seqsearch)。这些算法在不同的场景下有着各自的优点和适用性,理解并掌握它们对于优化程序...
实验报告涵盖了三种主要的查找方法:顺序表查找、树表查找(包括二叉排序树查找与平衡二叉树查找)以及Hash表查找。通过这些实验,学生将能够熟练地使用C/C++语言来实现这些查找算法,并能够在实际应用场景中灵活...
综上所述,本文通过构建一个统一的框架,成功地对不同DHT协议在面对成员变动时的性能进行了全面而深入的比较。这种比较有助于理解在动态网络环境中,如何有效地平衡查找时间和通信成本,以及哪些设计决策对提高整体...
该程序显示了从开始到全部插入,再到全部成功查找,最后全部删除的过程,并统计和各项数据。 2.open_hash-onetime.exe:是使用开放地址法的散列程序,它是在n=80000,m=100000,即在装载因子是0.8的情况下测试的。该...