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