問題引入：
1.給40億個不重復的unsigned int的整數，沒排過序的，然後再給一個數，如何快速判斷這個數是否在那40億個數當中?
2.給定一個千萬級別數據量的整數集合，判斷哪些是重復元素。
3.給定一個千萬級別數據量的整形數組，對其進行排序。
4.在5億個整數中找出不重復的整數(注意，內存不足以容納這5億個整數)。
從數據量上看，使用常規的解法（普通排序算法，逐個比較等）明顯不合適，所以這裡我們引入一個新的解法，就是Bitmap。
Bitmap就是用一個bit位來標記某個元素對應的Value， 而Key即是該bit的位序。由於采用了Bit為單位來存儲數據，因此可以大大節省存儲空間。 bitmap通過1個位表示一個狀態，比如：int類型有2^32個數字，即4G個數字，那麼每個數字一個狀態，就是2^32個bit，即512 MB（也就是說，用512兆存儲空間就可以處理4G個數據，即40+億數據）。
下面是我用C++寫的一個bitmap類，可以通過構造對象時傳入數據規模，動態申請所需的內存，然後處理用戶的大量數據：
#include<iostream>
#include<fstream>
#include<ctime>
using namespace std;
const unsigned SIZE = 512000000;//512兆靜態存儲區可處理40.96億數據
class Bitmap {
typedef struct Byte {
unsigned char bit8;
static const unsigned char mask[9];//用來取得一個字節每一位的輔助數組
Byte()
{
bit8 = 0;
}
//設置該位，就是存儲該數
void set1(unsigned at)
{
bit8 |= mask[at];
}
//讀取該位是否有數
bool get1(unsigned at)
{
return bit8 & mask[at];
}
} Byte;
Byte *m_byte;
unsigned m_size;
public:
Bitmap(unsigned _size)
{
m_byte = new Byte[(_size+7)/8];
m_size = _size;
}
virtual ~Bitmap()
{
delete[] m_byte;
m_size = 0;
}
//存儲一個數據
bool push(unsigned data)
{
if(data>=m_size)
return false;
m_byte[data/8].set1(data%8);
return true;
}
//讀取一個數據是否存在
bool find(unsigned data)
{
return data>=m_size ? 0 : m_byte[data/8].get1(data%8);
}
//返回能存儲的數據個數
unsigned size()
{
return m_size;
}
//重載運算符實現常用功能
//存儲一個數據
bool operator>>(unsigned data)
{
return push(data);
}
//讀取一個數據是否存在
bool operator<<(unsigned data)
{
return find(data);
}
//訪問到某個數據塊
Byte& operator[](unsigned i)
{
if(i>=m_size/8)
throw "index out of range";
return m_byte[i];
}
};
const unsigned char Bitmap::Byte::mask[9] = {0x80,0x40,0x20,0x10,0x8,0x4,0x2,0x1};//用來取得一個字節每一位的輔助數組
int main()
{
Bitmap bitmap(8*SIZE);//可以存儲40+億數據
ifstream file("in.txt");//從文件內錄入一些整數
unsigned read, i=0, t1 = clock();
for(i=0; i<SIZE; ++i)
if(file>>read)
bitmap>>read;
else
break;
file.close();
cout<<"共存儲"<<i/10000<<"W 數據, "<<"耗時: "<<clock()-t1<<"ms"<<endl;
t1 = clock();
for(i=0; i<1000000; ++i)
if(bitmap<<i)
;
cout<<"訪問"<<i/10000<<"W 數據共耗時: "<<clock()-t1<<"ms"<<endl;
cout<<"請輸入需要檢索的數據:"<<endl;
while(cin>>read) {
if(bitmap<<read)
cout<<"已存儲"<<read<<endl;
else
cout<<"Error: 未存儲"<<read<<endl;
}
return 0;
}
運行結果如下：
在程序中，先讀取一個文本文件中隨機產生的6W個整數，存到這個bitmap中，然後測試了一下從這個建立好的bitmap中查找100W數據耗時情況（11ms左右），接下來的部分是用戶可以手動輸入一些整數，程序會自動檢索bitmap中是否已存儲該數據。
這樣就可以解決引入話題中的第一個問題了，把輸入的文本數據改為已知的40億數據就可以了（40億數據的錄入可能需要一會兒，大概1300秒）。
下面給出引入的剩余三個問題的解題思路。
問題2：先建立一個足夠大的Bitmap對象，然後依次錄入這些數據，如果錄入某數據前發現該位已經為1，則該數據重復，依次得到重復的數據即可。
問題3：先建立一個足夠大的Bitmap對象，然後依次錄入這些數據，從Bitmap開始位置起遍歷，如果某位不為0，則表示有該數據，依次輸出不為0的位的位序就是排序好的數組（輸出太多沒意義，可以將輸出轉換到寫入文件，那麼新文件中數據就是排序好的）。
問題4：方法1，建立2個足夠大的Bitmap對象，依次錄入數據，錄入前先判斷該數據在bitmap1中是否存在（即對應位是否為1），不存在則錄入到bitmap1中，存在就錄入到bitmap2中；全部錄入完後，依次遍歷bitmap1中每一位，如果某一位為1但是bitmap2中對應位不為1，則表示該數據只出現過一次，依次輸出即可。
方法2，建立一個足夠大的Bitmap對象，不過用兩位表示一個數據，00表示數據不存在，01數據出現一次，10表示數據出現多次。11呢？一邊涼快去吧，不要你了，哈哈。這樣依次錄入數據時，如果該對應位（其實是兩位）為00則改為01，01就改為10，10就不管了。錄入完成後，遍歷整個bitmap，找到01位就輸出。
好了，常見的大數據題目就通過bitmap這個神奇的結構給解決了，不過bitmap也不是萬能的，很明顯，它暫時只適合存儲整形數據，當然這裡只考慮了unsigned類型數據，如果是int類型的話，對應映射一下就可以了也是沒問題的。不過即使如此，也只能處理10億級別的數據，如果數據量更大、類型不只是整形呢？
比如：需要寫一個網絡蜘蛛（web crawler）。由於網絡間的鏈接錯綜復雜，蜘蛛在網絡間爬行很可能會形成“環”。為了避免形成“環”，就需要知道蜘蛛已經訪問過哪那些URL。給一個URL，怎樣知道蜘蛛是否已經訪問過？
不難想到如下幾種方案：
1. 將訪問過的URL全部保存到數據庫；
2. 用HashSet將訪問過的URL保存起來。那只需接近O(1)的代價就可以查到一個URL是否被訪問過；
3. URL經過MD5或SHA-1等單向哈希後再保存到HashSet或數據庫。
4. Bit-Map方法。建立一個BitSet，將每個URL經過一個哈希函數映射到某一位。
方法1~3都是將訪問過的URL完整保存，方法4則只標記URL的一個映射位。
以上方法在數據量較小的情況下都能完美解決問題，但是當數據量變得非常龐大時問題就來了。
方法1：數據量變得非常龐大後關系型數據庫查詢的效率會變得很低。而且每來一個URL就啟動一次數據庫查詢是不是太小題大做了？
方法2：太消耗內存。隨著URL的增多，占用的內存會越來越多。就算只有1億個URL，每個URL只算50個字符，就需要5GB內存。
方法3：由於字符串經過MD5處理後的信息摘要長度只有128Bit，SHA-1處理後也只有160Bit，因此方法3比方法2節省了好幾倍的內存。
方法4：消耗內存是相對較少的，但缺點是單一哈希函數發生沖突的概率太高。還記得數據結構課上學過的Hash表沖突的各種解決方法麼？若要降低沖突發生的概率到1%，就要將BitSet的長度設置為URL個數的100倍。
但是我們可以考慮如果在一定程度上忽略誤判的情況，那麼是不是可以通過改進方法4實現這一功能？其實這就是Bloom Filter的算法 的思想：Bloom Filter是由Bloom在1970年提出的一種多哈希函數映射的快速查找算法。通常應用在一些需要快速判斷某個元素是否屬於集合，但是並不嚴格要求100%正確的場合。其思想就是在方法4基礎上做了一些改進，不是映射到一位，而是通過K個哈希函數映射到K位上，這樣只有當新的URL計算得到的K位都為1時才判斷為該URL已經訪問過（有誤判的可能性，不過有相關研究證明，取得合適的K值和bitmap位數時可以讓誤判率很小以至於可以忽略，參見細節）
當然，還可以通過map-reduce來處理，畢竟人家mapreduce可是行家，專業的大數據處理技術嘛！
