我們前面已經寫了一篇文章剖析eSNACC哈希結構的設計和實現(xiàn) 剖析eSNACC哈希結構的設計和實現(xiàn) ，而本篇我們專門剖析eSNACC中的hash函數(shù)。
我們先看看eSNACC求hash函數(shù)的實現(xiàn)：
看到這個代碼，我想先請問讀者您有什么想法？如果您沒來得及總結，可以參考我下面給的選項：
1、一定是本人粗心大意，copy代碼時弄錯了。
2、寫這個代碼的人是不是臨時工？基本的語法都沒過關。
3、大師，不愧為大師！
4、雕蟲小巧，小菜一碟，一目了然嘛~
=============================Please give your answers first=================
好了，我對您的選項作答：
1、我保證我做事一絲不茍、嚴謹踏實。此代碼是一字一句來自于源碼（除了空格的調整），如假包換、假一罰十！
2、我不能確定他是不是臨時工，但是我保證語法完全正確。
3、maybe...
4、那我只能說我太佩服您了！因為至少我是第一次看到case套在do-while里面的寫法。對您這樣的高人前來，有失遠迎，萬請恕罪！
==================================================================
好了，作為技術研究，我們下面就要深入剖析這個hash函數(shù)了。
首先，為了清楚，我把頭文件中的typedef也移到了代碼前。eSNACC的hash值用unsigned int表示。
然后，在說明代碼邏輯之前，我們不妨先看看函數(shù)的注釋：作者說本函數(shù)來自于sdbm，其中的修改就是把原來的magic number 65599改為了65587，因為他說明：65599 nice ,65587 even better.哪個魔數(shù)是better，我們就不在本文討論了。我們只研究算法。
既然是來自于sdbm，那么sdbm是什么呢？我的另一篇博客專門轉錄了這些信息，有興趣可以參見hash函數(shù)——djb2、sdbm、lose lose 。
這里只簡單介紹一下sdbm：
sdbm哈希函數(shù)的算法：對一個字符串str，分別求出hash(i) = hash(i - 1) * 65599 + str[i]，hash值就是所有hash(i)的和。其實現(xiàn)為：
static unsigned long sdbm( unsigned char *str)
{
unsigned long hash = 0;
int c;
while (c = *str++)
hash = c + (hash << 6) + (hash << 16) - hash;
return hash;
}
然后我們再回到eSNACC中的MakeHash函數(shù)，看那種讓人崩潰的代碼是不是就是這個算法：
先看這個宏#define HASHC n = *str++ + 65587 * n，這好像表達的就是hash(i) = hash(i - 1) * 65599 + str[i]，只是65599->65587.這個讓我們很滿意，那么后面的switch等是不是就是一個遍歷呢？
loop = (len + 8 - 1) >> 3 ==> loop=(len+8-1)/8 ==> loop=(len-1)/8 + 1 ：其實算出來的loop就是len除以8的值，如果有余數(shù)，那值加1。
len & (8 - 1) ：這里算出來的恰恰就是len%8的值。
我們再仔細分析switch-case和do-while結構：
其算法是這樣的：比如len=28，
1.計算loop=4.
2.算出len%8的值，然后先執(zhí)行該值次數(shù)的HASHC；本例中l(wèi)en%8=4，那么在switch時會到case 4:然后依次執(zhí)行了4次HASHC；
3.進while，--loop,這樣這個do-while還會執(zhí)行3次，每次HASHC會運行8次。
所以，最終就是3*8 + 4 =28，也就是說這與上面的sdbm的算法時完全一樣的!只是魔數(shù)變了，然后寫法上有些匪夷所思了。
/***********************************休息一下**************************************
好了，對MakeHash函數(shù)的分析是完成了，但是我覺得很有必要來思考一下這個函數(shù)的效率。
我們設計hash函數(shù)，一方面希望使函數(shù)產生的哈希值盡量分散減少沖突，另一方面就是希望保證這個函數(shù)效率很高，因為每次加入值，查找值時都要計算hash，如果函數(shù)效率不高，對整個系統(tǒng)也會是一種負擔。
結合這兩個因素，第一、我們發(fā)現(xiàn)作者將65599改成65587，他說明這樣生成hash的效果更好。但是第二條就實在無法讓人樂觀了！我們看到hash函數(shù)——djb2、sdbm、lose lose 中給的hash函數(shù)都為了提高性能都已經把對魔數(shù)的運算改成了移位操作，但是在MakeHash中，就是死硬的乘法！對字符串的每一個字節(jié)算一次乘法！說實話，想起如果字符串比較長，我真有點毛骨悚然...
所以，就讓我們就仿照sdbm中的實現(xiàn)，把乘法優(yōu)化掉來做一個MakeHash的優(yōu)化版吧：
Hash MakeHashOpt (const char *str, size_t len)
{
register Hash n = 0;
#define HASHCOPT n = *str++ + (n << 16) + (n << 5) + (n << 4) + (n << 1) + n
if (len > 0)
{
int loop;
loop = (len + 8 - 1) >> 3;
switch (len & (8 - 1))
{
case 0:
do
{
HASHCOPT;
case 7: HASHCOPT;
case 6: HASHCOPT;
case 5: HASHCOPT;
case 4: HASHCOPT;
case 3: HASHCOPT;
case 2: HASHCOPT;
case 1: HASHCOPT;
} while (--loop);
}
}
return n;
}
最后，讓我們來分析一下作者設計成這種看起來很別扭的實現(xiàn)形式的目的吧。
正如前面的分析，這樣做事先求出len對8的倍數(shù)，然后除了需要對余數(shù)做switch-case判斷來宏調用1-8次以為，其他的就是每次固定做8次宏調用。我認為：他這樣做，就是希望減少用while或for遍歷串的判斷次數(shù)，因為那樣要判斷l(xiāng)en+1次。現(xiàn)在就只要len/8 + 1 + len%8次了。
好了，對eSNACC的hash函數(shù)剖析就到此了。