此前我們了解過二叉樹算法，哈希算法，二分法等等，其中由最常用的二叉樹算法演變過來的哈希算法乃是從剛開始就學過的，此次因為一些項目的需要，要做一個類似ispell 的軟件，其中會產生大量的對單詞的查找操作，于是經(jīng)過一翻研究，得出以下HASH算法，經(jīng)過驗證比一般的查表的FNV HASH算法產生的分布曲線基本沒什么兩樣，并且在大部分的不同字典下，本算法要比查表的FNV HASH算法表現(xiàn)出速度更快，分布更均勻。但是因為是實驗結果，所以暫時還沒得出有效的數(shù)學推論，但是從大量的不同的字典測試數(shù)據(jù)來看，此算法確實效率不錯。
由于以前沒有涉及過相關的純算法的設計，所以剛剛開始的時候，打算隨便選用一種HASH，比如說用%除大質數(shù)，然后借此搭建一個比較強壯的測試環(huán)境，然后打算根據(jù)測試結果來改進HASH算法的模型。

最開始，我的HASH函數(shù)是這樣的：
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;
}
非常簡單，但是這是絕對不可取的，通過這個函數(shù)，我選取了一個23w詞的字典做為測試，當HASH SIZE=1024的時候，震蕩幅度相當大，那么如何來改進呢？首先想到可能產生的沖突的是這種情況：abcd和acbd，對于這兩種單詞來說，如果用上面的HASH函數(shù)，就一定會發(fā)生碰撞，為什么呢？因為每個字符少了關于它自己的位置信息，于是第一次改進版本的HASH函數(shù)就給每個字符加上了它的位置信息，將上面所描述的函數(shù)改進為：

unsigned int hash_func(char *str, int len)
{
register unsigned int sum = 0;
register char *p = str;

while(p - str < len)
sum += *(p++) * (p–str);

return?sum % MAX_PRIME_LESS_THAN_HASH_LEN;
}

某種程度上來說，比不帶位置信息產生的分布圖要好多了，但是仍然非常的不均勻。那么接來分析產生分布不均勻的原因，因為是用的乘法，所以仍然太過于依賴字母產生的結果了。于是改用XOR操作，選用以下函數(shù)：

unsigned int hash_func(char *str, int len)
{
register unsigned int sum = 0;
register char *p = str;

while(p - str < len)
sum += (*(p++) * (p–str)) ^ sum;

return?sum % MAX_PRIME_LESS_THAN_HASH_LEN;
}

雖然震蕩幅度比較，不過做出來的regression line明顯比上兩張圖片平得多了。但是結果仍然非常不好，從800到100的range太大。原因還是因為數(shù)據(jù)分布得不夠均勻，于是思考單獨的用加法來算是不是不太好，根據(jù)其他查表類HASH算法的過程，發(fā)現(xiàn)其大多都用了高低位來組合成最后的結果，于是我也采用了他們的方法：

unsigned int hash_func(char *str, int len)
{
register unsigned int sum = 0;?
register unsigned int h = 0;
register char *p =?str;

while(p - s < len)?
{
register unsigned short a = *(p++);
sum ^=? a * (p - str);?
h ^= a?/ (p - str);
}
return?((sum << 16) | h) % MAX_PRIME_LESS_THAN_HASH_LEN;
}

最后得出結論，不用查表的方法，而通過字符串本身的位置對字符本身進行修正的方法也能得到結果相當滿意的HASH函數(shù)，之后換了幾個大小不同的字典進行測試，得出的圖象都大致和上圖一致，非常令人滿意。對于這個項目，包括如何檢查單詞錯誤，和自動修正等等相關的內容，會隨著項目的完成一一在整理成文檔，希望大家支持。

ice

收藏 海報分享