楔子:
問題:假設一個文件中有9億條不重復的9位整數，現在要求對這個文件進行排序。
一般解題思路:
1、將數據導入到內存中
2、將數據進行排序 （比如插入排序、快速排序）
3、將排序好的數據存入文件
難題:
一個整數為4個字節
即使使用數組也需要900,000,000 * 4byte = 3.4G內存
對于32位系統，訪問2G以上的內存非常困難，而且一般設備也沒有這么多的物理內存
將數據完全導入到內存中的做法不現實
其他解決辦法:
1、導入數據庫運算
2、分段排序運算
3、使用bit位運算
解決方案一:數據庫排序
將文本文件導入到數據庫，讓數據庫進行索引排序操作后提取數據到文件
優點：操作簡單
缺點：運算速度慢，而且需要數據庫設備。
解決方案二:分段排序
操作方式：
規定一個內存大小，比如200M，200M可以記錄52428800條記錄，我們可以每次提取5000萬條記錄到文件進行排序，要裝滿9位整數需要20次，所以一共要進行20次排序，需要對文件進行20次讀操作
缺點：
編碼復雜，速度也慢(至少20次搜索)
關鍵步驟：
先將整個9位整數進行分段，億條數據進行分成20段，每段5000萬條
在文件中依次搜索0~5000萬，50000001~1億……
將排序的結果存入文件
解決方案三:bit位操作
思考下面的問題:
一個最大的9位整數為999999999
這9億條數據是不重復的
可不可以把這些數據組成一個隊列或數組，讓它有0~999999999(10億個)元素
數組下標表示數值，節點中用0表示這個數沒有，1表示有這個數
判斷0或1只用一個bit存儲就夠了
聲明一個可以包含9位整數的bit數組(10億)，一共需要10億/8=120M內存
把內存中的數據全部初始化為0
讀取文件中的數據，并將數據放入內存。比如讀到一個數據為341245909這個數據，那就先在內存中找到341245909這個bit，并將bit值置為1
遍歷整個bit數組，將bit為1的數組下標存入文件
關鍵代碼
檢查是某一個char里面(first)的第second位中存儲的數據是否為1
bool CompareBit (unsigned char first, int second)
{
const static int mark_buf[] = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};
if (second > 8)
return false;
return (first & mark_buf[second]) == mark_buf[second];
}
將某一個char(Desc)中的第source位置為1
bool WriteToBit (unsigned char *Desc, int source)
{
const static int mark_buf[] = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};
if (source > 8)
return false;
Desc[0] |= mark_buf[source];
return true;
}
案例
在某個項目中，我們需要對2億條手機號碼刪除重復記錄(過濾號碼黑名單同樣有效)
工作難點就在于如何處理這2億條電話號碼,直接用哈希表存放手機號碼不大現實,即使經過優化,用一個unsigned int存放一條記錄,那也得需要2億*4=8億byte,遠超過32位系統的尋址能力
解決方案:
將電話號碼由12位單個數字組成的字符串轉換為一個unsigned int型數據(這個完全可能,手機號碼由前三位數字和后面八位數字組成,后面八位需要占到1~1000萬的空間,而前面用0~100的數字存儲已經足夠)
為簡單起見,默認為0~4G的數字都有可能分布號碼,為此我們分配4G/32=512M的內存
將這2億個號碼整理成unsigned int類型后按上述辦法存放在這塊內存中(比如13512345678我們整理后為112345678,我們找到內存中112345678bit的下標,并將此bit值設為1)
遍歷整個bit數組,記錄下所有的號碼,這些號碼即是不重復的手機號碼
總結
建立一個足夠大的bit數組當作hash表
以bit數組的下標來表示一個整數
以bit位中的0或1來表示這個整數是否在這個數組中存在
適用于無重復原始數據的搜索
原來每個整數需要4byte空間變為1bit，空間壓縮率為32倍
擴展后可實現其他類型（包括重復數據）的搜索
注意
由于操作系統和編程語言本身的限制,有可能內存足夠,但無法分配一塊連續大內存的情況,這樣的話可以申請多塊稍微小一點的內存,然后用鏈表或其他的方式連接起來使用
參考資料