海量數據去重

一個文件中有40億條數據，每條數據是一個32位的數字串，設計算法對其去重，相同的數字串僅保留一個，內存限制1G.

方法一：排序

對所有數字串進行排序，重復的數據傳必然相鄰，保留第一個，去除后面重復的數字串即可。

缺點是排序時間復雜度太高，并且顯然是需要內排序+外排序一起的。優化的方法有掃雪機模型。

方法二：哈希表 + 文件分割

當然還有一種方法，取32位的前n位做一個哈希，然后把哈希值一樣的數據串放到一個文件里面。然后每次將一個文件load到內存中，然后對這個文件中的數據做個排序 or 哈希去重即可。

這樣的缺點是磁盤IO較多。

方法三：位圖

用512MB的unsigned int數組來記錄文件中數字串的存在與否，形成一個bitmap。

然后從0到2^32-1開始遍歷，如果flag為1，表明該數存在。這樣就自動實現了去重。

這個思路很好了。