《基于英文单词的快速hash索引算法》由会员分享，可在线阅读，更多相关《基于英文单词的快速hash索引算法（3页珍藏版）》请在金锄头文库上搜索。
1、基于英文单词的快速基于英文单词的快速 HASH 索引算法索引算法 选择自 tarkey 的 Blog 因为有项目需要，要做一个类似 ispell 的软件，其中会产生大量的对单词的查找操作，于是经过一翻 研究，得出以下 HASH 算法，经过验证比一般的查表的 FNV HASH 算法产生的分布曲线基本没什么两样， 并且在大部分的不同字典下，本算法要比查表的 FNV HASH 算法表现出速度更快，分布更均匀。但是因为 是实验结果，所以暂时还没得出有效的数学推论，但是从大量的不同的字典测试数据来看，此算法确实效 率不错。由于以前没有涉及过相关的纯算法的设计，所以刚刚开始的时候，打算随便选用一种 HAS
2、H，比如说用% 除大质数，然后借此搭建一个比较强壮的测试环境，然后打算根据测试结果来改进 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
3、=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 += *
4、(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+) * (pst
5、r) 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 =
6、 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 函数，之后换了几个大小不同的字典进行测试，得出的图象都大致和上图一致，非常令 人满意。对于这个项目，包括如何检查单词错误，和自动修正等等相关的内容，会随着项目的完成一一在 整理成文档，希望大家支持。作者作者 Blog：http:/ 网友 ( 2004-12-07) 最后一个算法有问题，应该在函数开始的时候把 len 除以 2，否则会计算两倍于字符串长度的内存空间
