前文已經(jīng)講述，字母全排列是個(gè)驚人的數(shù)字，即使只遍歷小寫字母和數(shù)字6個(gè)全排列也有36^6 = 2176782336，21億多個(gè)，7個(gè)排列36^7 = 78364164096，783億多，8個(gè)排列36^8 = 2821109907456，2.8萬(wàn)億多個(gè)，數(shù)字非常驚人。Md5反查是個(gè)string-string的映射，16-N個(gè)字符的映射，如果考慮hex模式的md5那就是32-N的映射，考慮映射人們最先想到的可能都是數(shù)據(jù)庫(kù)存儲(chǔ)方式，我也首先想到了用數(shù)據(jù)庫(kù)存儲(chǔ)，分別考察了一下sqlite和berkeleydb，但測(cè)試下來(lái)制造數(shù)據(jù)的速度很慢，sqlite加索引大概只能到5w條記錄/s，不加索引為10w條/s，berkeleydb用單條模式大概只能到4.5w條/s，這個(gè)速度已經(jīng)很慢了，更難于接受的是如果寫1000w對(duì)sqlite加索引來(lái)說(shuō)不是耗時(shí)200s，而是2000s了，也就是說(shuō)耗時(shí)隨單個(gè)數(shù)據(jù)文件記錄的條數(shù)增多幾乎成平方模式遞增，而不是簡(jiǎn)單的線性遞增，這是很要命的，就算制造1億條數(shù)據(jù)耗時(shí)也是驚人，我的實(shí)測(cè)中沒(méi)有測(cè)試過(guò)用sqlite制造1000w條以上的數(shù)據(jù)，在我心目中已經(jīng)否定了那種模式。雖然我知道很多號(hào)稱有多少億條數(shù)據(jù)的網(wǎng)站其實(shí)都是用的數(shù)據(jù)庫(kù)，我不知道他們花了多少時(shí)間制造數(shù)據(jù)，或者幾天，或者幾個(gè)月，或者更長(zhǎng)時(shí)間，反正我對(duì)采用普通數(shù)據(jù)庫(kù)模式制造數(shù)據(jù)完全持否定態(tài)度，嵌入式速度太慢，其他數(shù)據(jù)庫(kù)則不光速度慢而且也不適合分布式應(yīng)用，難道用戶每裝個(gè)點(diǎn)還要裝個(gè)mysql之類的數(shù)據(jù)庫(kù)，幾乎不可能啊。
下面說(shuō)說(shuō)我的方法，我本來(lái)第一版本是計(jì)劃先不做文件式數(shù)據(jù)庫(kù)的，第一版本來(lái)只規(guī)劃了做內(nèi)存數(shù)據(jù)，充分榨取每一個(gè)字節(jié)，關(guān)于內(nèi)存數(shù)據(jù)庫(kù)我實(shí)現(xiàn)了好幾個(gè)版本，下面分別介紹一下：
版本1：hash模式
用char key[16];做鍵，char pass[n];做內(nèi)容，由于hash桶占用了一些字節(jié)：
DWORD h, nKeyLen; //hash鍵值, 字符串長(zhǎng)度
DWORD tag; //私有值，默認(rèn)為0提供給外部使用
bucket *pListNext; //hash表雙鏈的下一個(gè)節(jié)點(diǎn)
bucket *pListPrev; //hash表雙鏈的上一個(gè)節(jié)點(diǎn)
bucket *pNext; //拉鏈的下一個(gè)節(jié)點(diǎn)
VALUE second; //具體數(shù)據(jù)
_Elem first[0]; //first鍵
用這個(gè)hash模式大概存儲(chǔ)一個(gè)6個(gè)字符的串的md5信息花了50個(gè)字節(jié)，花費(fèi)太多，結(jié)果自然存不了多少數(shù)據(jù)，該方案作為第一驗(yàn)證方案，除了花費(fèi)內(nèi)存太多還是個(gè)能通過(guò)的方案。
版本2：hash簡(jiǎn)化方案
在上述版本基礎(chǔ)上簡(jiǎn)化桶設(shè)計(jì)，拋棄作為標(biāo)準(zhǔn)桶的一些字段，精簡(jiǎn)之后如下:
DWORD h; //hash鍵值
bucket *pNext; //拉鏈的下一個(gè)節(jié)點(diǎn)
byte nKeyLen; //字符串長(zhǎng)度
VALUE second; //具體數(shù)據(jù)
_Elem first[0]; //first鍵
該版本存儲(chǔ)一個(gè)6個(gè)字符的串的md5信息需要31個(gè)字節(jié)，比版本1少了很多，進(jìn)步一些了。
方案1和方案2速度都很快。
版本3：vector方案
考慮到hash占用內(nèi)存較多，采用vector方案，直接存儲(chǔ)
Char mm[16];
Char pass[n];
存儲(chǔ)一個(gè)6個(gè)字符的串的md5信息需要22個(gè)字節(jié)，該方案排序速度太慢，查找速度肯定也比不上版本1和版本2，之后還測(cè)試過(guò)將vector里面存儲(chǔ)指針，那種模式每個(gè)6個(gè)字符的串的md5信息占用內(nèi)存26個(gè)，接近hash版本，排序速度比直接存儲(chǔ)數(shù)據(jù)的好一點(diǎn)，但也還是很慢，總之這個(gè)方案作為一個(gè)過(guò)度方案最終也被放棄了。
方案4：全文件Hash緊縮方案
以上這些方案的特點(diǎn)是都存儲(chǔ)了char mm[16]; 也就是說(shuō)存儲(chǔ)部分都有計(jì)算出來(lái)的md5，經(jīng)過(guò)思考之后覺(jué)得可以放棄存儲(chǔ)md5，不存儲(chǔ)md5是個(gè)很妙的想法，繼續(xù)發(fā)揮hash思想，也不保存根據(jù)md5計(jì)算出來(lái)的hash值本身，只將該md5和串的信息關(guān)聯(lián)到hash值的模所在的索引節(jié)點(diǎn)，這樣就將索引節(jié)點(diǎn)信息減少到極致：
size_t coffset; //content offset low
unsigned short a:12; //切分為12, 4
unsigned short b:4; //4，為下一個(gè)沖突值的索引序數(shù)，如果沒(méi)有就為0
size_t nextindex; //沖突條目的存儲(chǔ)序號(hào)，為0表示沒(méi)有沖突
使用該索引可讓單文件最多支持內(nèi)容16T，最多687億記錄，具體實(shí)現(xiàn)的時(shí)候由于全使用文件所以速度比較慢，速度退化到sqlite之類同一級(jí)別了，不過(guò)這個(gè)設(shè)計(jì)思想為方案5提供了借鑒，如果跟方案5一樣用大塊內(nèi)存輔助，速度大概可以上升一個(gè)級(jí)別，不過(guò)由于沒(méi)有具體實(shí)現(xiàn)，待研究之后再做評(píng)估。
方案5：hash緊縮內(nèi)存方案
學(xué)習(xí)方案4的設(shè)計(jì)思想，考慮僅在內(nèi)存里面實(shí)現(xiàn)一個(gè)緊湊型文件，由于只考慮內(nèi)存可表示的32位范圍，所以簡(jiǎn)化索引節(jié)點(diǎn)定義如下：
Size_t coffset; pass相對(duì)于內(nèi)容區(qū)首的偏移
Size_t nindex; 沖突節(jié)點(diǎn)下一個(gè)序，如果為0則表示沒(méi)有沖突
內(nèi)容區(qū)存儲(chǔ)更簡(jiǎn)單，每個(gè)字符串直接保存，最后的0也保存，這樣每個(gè)字符串自然分開(kāi)，對(duì)一個(gè)6個(gè)字符長(zhǎng)的串來(lái)說(shuō)，保存一個(gè)信息只需要15個(gè)字節(jié)，真的是省啊，1億個(gè)字符串也只要大約1.5g左右硬盤就夠了。此方案雖然很妙，但實(shí)現(xiàn)的時(shí)候卻費(fèi)了一些周折，具體做的時(shí)候也做過(guò)好幾個(gè)版本，由于考慮該方案的內(nèi)容和索引最后都可以直接保存到文件，所以該方案對(duì)位置的保存都用的是相對(duì)位置，也由于想讓索引節(jié)點(diǎn)信息簡(jiǎn)單，最初是讓沖突索引采用線性步長(zhǎng)跳躍方法，測(cè)試之后發(fā)現(xiàn)這個(gè)方法速度奇慢，而且還有個(gè)非常討厭的問(wèn)題，隨著數(shù)據(jù)量的增多沖突擴(kuò)散越來(lái)越厲害，耗時(shí)非線性的陡峭增長(zhǎng)。放棄這個(gè)實(shí)現(xiàn)之后還是回到了經(jīng)典的拉鏈法，拉鏈法速度就是快，但拉鏈法處理索引節(jié)點(diǎn)雖然容易，但要讓索引信息可直接保存卻要花一些腦子，最后采用先用內(nèi)存擴(kuò)展拉鏈，待全部索引構(gòu)造好之后再把拉鏈出來(lái)的部分重新填到原始索引區(qū)中的空區(qū)，并修正對(duì)應(yīng)索引相對(duì)位置。這個(gè)方法的精妙之處在于既省空間又有速度，最令人興奮的是采用該方法耗時(shí)隨著數(shù)據(jù)量的增大是線性增長(zhǎng)，最后的實(shí)現(xiàn)在我的筆記本上大概100w/s，1億條記錄從字母組合到最終生成索引文件也只要不到2分鐘的時(shí)間，制造了一些數(shù)據(jù)之后統(tǒng)計(jì)了一下，沖突節(jié)點(diǎn)比例大概占26%-35%，也就是說(shuō)有65%以上的數(shù)據(jù)只要一次hash就直接命中，平均拉鏈長(zhǎng)度1.2左右，最長(zhǎng)拉鏈10，總體還是很滿意的。
原本第一版沒(méi)有考慮這個(gè)可存儲(chǔ)的方案，但花了幾天就搞定了一個(gè)基本可用的存儲(chǔ)方案還是很令人興奮的，雖然該存儲(chǔ)方案還有一些問(wèn)題沒(méi)有徹底解決，但已經(jīng)有進(jìn)一步處理的辦法，待下一個(gè)相對(duì)空閑時(shí)間段再仔細(xì)研究一下，定會(huì)有更簡(jiǎn)潔的實(shí)現(xiàn)做出來(lái)，至于待解決的是什么問(wèn)題以及如何解決那些問(wèn)題還是等我代碼寫好了再寫出來(lái)吧。