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