全文预览已结束
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
基于英文单词的快速HASH索引算法因为有项目需要,要做一个类似ispell的软件,其中会产生大量的对单词的查找操作,于是经过一翻研究,得出以下HASH算法,经过验证比一般的查表的FNV HASH算法产生的分布曲线基本没什么两样,并且在大部分的不同字典下,本算法要比查表的FNV HASH算法表现出速度更快,分布更均匀。但是因为是实验结果,所以暂时还没得出有效的数学推论,但是从大量的不同的字典测试数据来看,此算法确实效率不错。由于以前没有涉及过相关的纯算法的设计,所以刚刚开始的时候,打算随便选用一种HASH,比如说用%除大质数,然后借此搭建一个比较强壮的测试环境,然后打算根据测试结果来改进HASH算法的模型。最开始,我的HASH函数是这样的:unsigned int hash_func(char *str, int len) register unsigned int sum = 0; register char *p = str; while(p - str len) sum += *(p+); return sum % MAX_PRIME_LESS_THAN_HASH_LEN;非常简单,但是这是绝对不可取的,通过这个函数,我选取了一个23w词的字典做为测试,当HASH SIZE=1024的时候,得到了以下的图象:看得出震荡幅度相当大,那么如何来改进呢?首先想到可能产生的冲突的是这种情况:abcd和acbd,对于这两种单词来说,如果用上面的HASH函数,就一定会发生碰撞,为什么呢?因为每个字符少了关于它自己的位置信息,于是第一次改进版本的HASH函数就给每个字符加上了它的位置信息,将上面所描述的函数改进为:unsigned int hash_func(char *str, int len) register unsigned int sum = 0; register char *p = str; while(p - str len) sum += *(p+) * (pstr); return sum % MAX_PRIME_LESS_THAN_HASH_LEN; 得到以下图象:某种程度上来说,比不带位置信息产生的分布图要好多了,但是仍然非常的不均匀。那么接来分析产生分布不均匀的原因,因为是用的乘法,所以仍然太过于依赖字母产生的结果了。于是改用XOR操作,选用以下函数:unsigned int hash_func(char *str, int len) register unsigned int sum = 0; register char *p = str; while(p - str len) sum += (*(p+) * (pstr) sum; return sum % MAX_PRIME_LESS_THAN_HASH_LEN; 得到以下图象: 上图虽然震荡幅度比较,不过做出来的regression line明显比上两张图片平得多了。但是结果仍然非常不好,从800到100的range太大。原因还是因为数据分布得不够均匀,于是思考单独的用加法来算是不是不太好,根据其他查表类HASH算法的过程,发现其大多都用了高低位来组合成最后的结果,于是我也采用了他们的方法:unsigned int hash_func(char *str, int len) register unsigned int sum = 0; register unsigned int h = 0; register unsigned short *p = (unsigned short *)str; register unsigned short *s = (unsigned short *)str; while(p - s len) register unsigned short a = *(p+) * (p-s); sum += sum a; h += a; return (sum 16) | h) % MAX_PRIME_LESS_THAN_HASH_LEN;得到最终近似完美的图象: 最后得出结论,不用查表的方法,而通过字符串本身的位置对字符本身进行修正的方法也能得到结果相当满意的HASH函数,之
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 气管切开术后伤口护理规范化培训
- 涂料调配工岗前成果考核试卷含答案
- 衡器装配调试工岗前安全培训效果考核试卷含答案
- 油料计量员8S执行考核试卷含答案
- 经编钳针工安全生产基础知识评优考核试卷含答案
- 运动神经元病康复护理大纲
- 拍卖运营师岗前基础管理考核试卷含答案
- 预拌混凝土中控工安全专项竞赛考核试卷含答案
- 活性炭干燥工工作水平评优考核试卷含答案
- 饮料制作工核心竞赛考核试卷含答案
- 职业素养培训课件教学
- 癌症病人的康复护理
- 学校拒绝症家庭疗法系统解读
- 铝扣板吊顶施工合同
- 计算机导论(第5版) 课件 袁方 第1-3章 计算机发展简史、计算机专业知识体系、计算机中的数据表示
- 《课程理论-课程的基础、原理与问题》施良方
- 基础验收自评报告
- 生猪屠宰兽医卫生检验人员理论考试题库及答案
- 2024年银屑病诊疗指南(修订版)解读课件
- DZ∕T 0221-2006 崩塌、滑坡、泥石流监测规范(正式版)
- 高考作文标准方格纸-A4-可直接打印
评论
0/150
提交评论