免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 5038 | 回复: 11

[算法] 【请问】关于散列的一个应用的原理 [复制链接]

论坛徽章:
0
发表于 2009-02-26 20:56 |显示全部楼层
最近在学习《数据结构,c实现》
在看散列那一章的总结时,对于散列的应用,有这样一段话:

散列的另一个用途是在线拼写检查程序,如果错拼检测(与正确性相比)更重要,那么整个目录可以再被散列,单词则可以在常数时间内被检测,散列表很适合这项工作,因为字母顺序排列单词并不重要,而以它们在文件中出现的顺序显示出错误拼写当然是可以接受的。

小女子愚钝,对于这个原理是想啊想,也没想明白,请各位同学帮忙点拨下,谢谢大家,o(∩_∩)o...

论坛徽章:
0
发表于 2009-02-26 21:00 |显示全部楼层
hash 就是一对一,老女子我也说不清楚o(∩_∩)o...
hash 解决冲突的一个方法就是 再hash

论坛徽章:
0
发表于 2009-02-27 08:48 |显示全部楼层

回复 #2 prolj 的帖子

谢谢,对于散列的原理比较清楚,就是和这个应用不知道怎么对应上

论坛徽章:
0
发表于 2009-02-27 09:08 |显示全部楼层
原帖由 lqseu 于 2009-2-26 20:56 发表
最近在学习《数据结构,c实现》
在看散列那一章的总结时,对于散列的应用,有这样一段话:

散列的另一个用途是在线拼写检查程序,如果错拼检测(与正确性相比)更重要,那么整个目录可以再被散列,单词则可 ...

这应该是翻译的吧,这段话怎么看的这么别扭啊
愣是没看懂
找找原版比较一下

论坛徽章:
0
发表于 2009-02-27 09:10 |显示全部楼层
大概意思就是说,单词表作为一个Hash,把每个单词作为Key,查找Hash,如果找不到,则表示拼写错误了

这样拼写错误查找时间就是O(1)了。

论坛徽章:
0
发表于 2009-02-27 09:26 |显示全部楼层
我认为:散列原理是空间换时间,以空间换取查询等操作的高效率。 理想情况下是每个hash函数值对应的键都是一样多。
比如,把一堆写好号的球放入n个桶里,每个桶又有编号,你要找每个球只需先找在哪个桶里,因为找桶只需要进行一次计算就可以,所以马上你就能知道你要找的球在哪个桶里,然后你在桶里继续找你要的球,因为如果你的hash函数好的话,每个桶的球是较为平均的,所以你只需要查找平均查找(m / n)次就能找到这个球。 不晓得我说的行不行

论坛徽章:
4
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11IT运维版块每日发帖之星
日期:2016-08-11 06:20:00IT运维版块每日发帖之星
日期:2016-08-15 06:20:00
发表于 2009-02-27 10:35 |显示全部楼层

回复 #6 rt77789 的帖子

>>所以你只需要查找平均查找(m / n)次就能找到这个球。
说法不够准确。m < n,至少查找1次;m >= n,平均查找(m / n)次。

论坛徽章:
0
发表于 2009-02-27 10:41 |显示全部楼层

回复 #7 happy_fish100 的帖子

...呃,确实不够严格。

论坛徽章:
0
发表于 2009-02-27 12:47 |显示全部楼层

回复 #6 rt77789 的帖子

恩 挺有道理的,换取的效率就是散列函数设计时要考虑的问题吧。

ps:签名档很帅 o(∩_∩)o...

论坛徽章:
0
发表于 2009-02-27 12:48 |显示全部楼层

回复 #5 雨过白鹭洲 的帖子

恩 我觉得差不多是你说的这个意思  就是这个单词表会很大吧
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP