- 浏览: 297176 次
- 性别:
- 来自: 大连
文章分类
- 全部博客 (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 629http://blog.csdn.net/lizhengn ... -
编辑距离算法
2014-08-14 00:02 930字符串编辑距离: 是一种字符串之间相似度计算的方法。给定两个 ... -
八叉树及K-D树的应用和实现
2014-07-31 19:51 20961. 八叉树、k-d树的原理 2. 八叉树、k-d树的应用 ... -
四叉树与八叉树
2014-07-31 19:37 1343前序 四叉树或四元树也被称为Q树(Q-Tree)。四叉树 ... -
自行车往哪个方向行驶? <转>
2013-05-09 12:57 870文章转自: http://www.ma ... -
01虫子问题<转>
2013-05-09 12:26 707来自:http://www.cs.cmu.ed ... -
求数组中重复出现次数大于数组总个数一半的数
2013-04-17 21:39 1356变量设计,一个变量,存数num,另一个存这个数出现的次数ti ... -
约瑟夫环(时间复杂度为n)
2013-04-17 21:20 1767一、 题目描述: 约瑟夫环是一个数学的应用问 ... -
不用除法运算符的除法
2013-04-04 09:53 1772题目描述: 给定一数组a[N],我们希望构造数组b [N] ... -
泊松分酒趣题<转>
2013-03-24 11:40 777有一个12品脱(pint)的酒 ... -
二进制与三进制的那些趣题<转>
2013-03-24 11:20 14101. 小明是个卖苹果的 ... -
r-组合
2012-10-29 18:14 966算法描述而下(来自组合数学): 从r-组合a1a2...ar ... -
全排列的实现(C)
2012-10-24 16:42 1087找工作,笔试经常会出现一个题,怎样生成一个集合内所有元素的全排 ... -
智力题
2012-09-06 16:17 1096不管是找工作还是考公 ... -
插入、堆排序
2012-08-21 21:15 0排序的最初数据结构是在线性表的基础上的,线性表这个东西就好像很 ... -
排序方法比较<转>
2012-08-21 20:50 798根据排序的原则,内排序可以分为: 插入排序 交换排序 ... -
基于二进制的集合(c语言)
2012-08-17 17:20 983用C去操作集合,有时候觉得十分的麻烦,不过,集合又一定要用。苦 ... -
位运算<转>
2012-08-15 20:40 937什么是位运算? ... -
位运算求解N皇后的过程
2012-08-14 21:14 11308皇后可以用位运算来求,有点好奇的,不过,位运算这个强大的逻 ... -
一些hash函数实现<转>
2012-08-14 11:53 1276/** * Hash算法大全<br> * ...
相关推荐
<br> /// </summary><br> <br> [DllImport("User32.dll",EntryPoint="SendMessage")]<br> private static extern int <br> SendMessage(<br> int hWnd, // handle to destination window<br> int Msg, // ...
除了无法访问它的大小和不能使用索引来获得它的子变量:集合可以看作只能由<#list...>指令使用的受限sequences。 5、 方法:通过传递的参数进行计算,以新对象返回结果 方法变量通常是基于给出的参数计算值在数据...
基本思想是:首先将给定值key与表中中间位置记录的关键字相比较,若二者相等,则查找成功,否则根据比较的结果确定下次查找的范围是在中间记录的前半部分还是后半部分,然后在新的查找范围内进行同样的查找,如此...
二叉排序树是动态树表,查找不成功时插入新结点时,会引起树的重新分裂和组合 B.对二叉排序树进行层序遍历可得到有序序列 C.用逐点插入法构造二叉排序树时,若先后插入的关键字有序,二叉排序树的深度最大 D.在...
#include<stdio.h> #include<stdlib.h> typedef struct node { int data; struct node *next; }node; init_hash(node **A,int n) { int i; for(i=0;i<n;i++) { A[i]=(node *)malloc(sizeof(node)); A[i]->data=0...
由于性能优势,使用面广,有许多第三方类库提供了支持,如MSVC中的<hash>和Boost中的<boost>,后来Boost的unordered_map被吸纳进了C ++ 11标准。 (1)1.两数之和 译文描述:给你一个数组,要在多个中找到两个数字a...
(4)查找元素:查找哈希表中的元素,分为查找成功和查找不成功。 (5)插入元素:在哈希表中,插入一个元素,分为插入成功和失败。 (6)删除元素:在已有的数据中,删除一个元素。 (7)退出系统:退出程序。 涉及的数据...
该程序显示了从开始到全部插入,再到全部成功查找,最后全部删除的过程,并统计和各项数据。 2.open_hash-onetime.exe:是使用开放地址法的散列程序,它是在n=80000,m=100000,即在装载因子是0.8的情况下测试的。该...
table[bucketIndex] = new Entry<>(hash, key, value, e); size++; } 当调用 addEntry 写入 Entry 时需要判断是否需要扩容。 如果需要就进行两倍扩充,并将当前的 key 重新 hash 并定位。 而在 createEntry 中会...
if(p) cout<<"查找成功!"<<endl; else cout<<"查找失败!"<<endl; break; case 4: cout<<endl<<"请输入要插入的关键字:"; cin>>R; p=InsertHash(H,R); if(p) cout<<"插入成功!"...
int HashSearch(HashTable T,KeyType K,int *pos) { //在散列表T[0..m-1]中查找K,成功时返回1。失败有两种情况:找到一个开放地址 //时返回0,表满未找到时返回-1。 *pos记录找到K或找到空结点时表中的位置 ...
使用哈希函数:H(k)=3*k...试对输入的关键字序列构造哈希表,哈希表长度为length,求等概率情况下查找成功的平均查找长度,并设计构造哈希表的完整的算法。本题给出部分代码,请补全Hash函数和解决冲突的collison函数。
* 指定key值(支持key值hash查找,提高效率) * 数据库合并 * 导出数据库到外部文件 * 从外部文件导入数据库 * 关键过程性能打点(毫秒级耗时统计) * 数据库统计显示(包括数据规模\占用内存等) * 格式化打印 ----...
else if (UnicodeChar >= 110 && UnicodeChar <= 122) //对字符进行解密 { UnicodeChar = UnicodeChar - 13; } else if (UnicodeChar >= 65 && UnicodeChar <= 77) //对字符进行加密 { UnicodeChar = UnicodeChar + ...
a<>0 改为 a>0 or a<0 a<>’’ 改为 a>’’ IS NULL 或IS NOT NULL 一般是不会应用索引的,因为B-tree索引是不索引空值的。 推荐方案:用其它相同功能的操作运算代替,如: a is not null 改为 a>0 或...
4.二分查找. (代码可在五行以内) 5.叉乘、判线段相交、然后写个凸包. 6.BFS、DFS,同时熟练hash表(要熟,要灵活,代码要简) 7.数学上的有:辗转相除(两行内),线段交点、多角形面积公式. 8. 调用系统的qsort...
基本思想是:首先将给定值key与表中中间位置记录的关键字相比较,若二者相等,则查找成功,否则根据比较的结果确定下次查找的范围是在中间记录的前半部分还是后半部分,然后在新的查找范围内进行同样的查找,如此...
TYPE key 返回某个key元素的数据类型 ( none:不存在,string:字符,list,set,zset,hash) KEYS pattern 返回匹配的key列表 (KEYS foo*:查找foo开头的keys) RANDOMKEY 随机获得一个已经存在的key,如果当前数据库为空,...
ZRANGEBYSCORE key min max 返回所有符合score >= min和score <= max的成员 ZCARD key 返回有序集合的元素数量 ZSCORE key element 返回指定成员的SCORE值 ZREMRANGEBYSCORE key min max 删除符合 score >= min 和 ...