基于英文单词的快速
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
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
sum += *(p++) * (p
–
str);
return sum % MAX_PRIME_LESS_THAN_HASH_LEN;
}
得到以下图象：