利用Java里的BitSet位集合實(shí)現(xiàn)：

有四十億個(gè)扣扣號(hào)，拿來一個(gè)扣扣號(hào)，最快速查找？

一、問題描述：

??1.在42億個(gè)qq號(hào)碼中，如何使用O(1)時(shí)間復(fù)雜度去查找一個(gè)QQ號(hào)是否存在。

??2.qq號(hào)的位數(shù)小于13位，存儲(chǔ)著42億QQ號(hào)的內(nèi)存不得超過600MB.

二、位圖排序思想

??由于待排序的數(shù)據(jù)記錄較多，我們單純地使用常見的排序方法時(shí)間效率較低，運(yùn)行時(shí)間會(huì)很長(zhǎng)。而且內(nèi)存空間有限（限制為1MB左右），所以我們不能同時(shí)把所有整數(shù)讀入內(nèi)存（如果每個(gè)整數(shù)使用7個(gè)字節(jié)來存儲(chǔ)，那么1MB內(nèi)存空間只能存大約143000個(gè)數(shù)字）。當(dāng)然我們可以多次讀取輸入文件，多次排序，但是更好的方案是使用位圖排序，可以使用有限的1MB內(nèi)存空間并只進(jìn)行一趟排序。

??????1.根據(jù)待排序集合中最大的數(shù)，開辟一個(gè)位數(shù)組，用來表示待排序集合中的整數(shù)；//這里可能被問大數(shù)據(jù)TOPK

??????2.待排序集合中的數(shù)字在位數(shù)組中的對(duì)應(yīng)位置置1，其他的置0；

??????例如，待排序集合{1,2,3,5,8,13}可以表示為：0-1-1-1-0-1-0-0-1-0-0-0-0-1

??????這樣排序過程自然可以分為三步：

??????第一步：將所有的位都置為0；

??????第二步：通過讀入文件中的每個(gè)整數(shù)，將每個(gè)對(duì)應(yīng)的位都置為1；

??????第三步：檢驗(yàn)每一位，如果該位為1，輸出對(duì)應(yīng)的整數(shù)。

??????注意：位圖排序是使用一個(gè)二進(jìn)制位而不是一個(gè)整數(shù)來表示0或1，這樣可以大大地減少所需要的內(nèi)存空間。使用位圖排序的前提是要知道待排序序列中的最大數(shù)。位圖排序的缺點(diǎn)是有些數(shù)沒有出現(xiàn)過，仍要為其保留一個(gè)位。故位圖排序比較適合關(guān)鍵字密集的序列，例如一個(gè)QQ號(hào)碼。

/*Phase 1: initialize set to empty*/
?
? for
i = [0, n)
?
? ? bit[i] = 0
?
/*Phase 2: insert present elements into the set*/
?
? for
each i in the input file
?
? ? bit[i] = 1
?
/*Phase 3: write sorted output*/
?
? for
i = [0, n)
?
? ? if
bit[i] == 1
?
? ? ? write i on the output file
三、使用位圖排序的方法

??????位圖排序時(shí)，我們需要考慮：給出一個(gè)數(shù)，如何找到其對(duì)應(yīng)位圖的位置，方法就是首先找到該數(shù)對(duì)應(yīng)的字節(jié)，然后在找到該數(shù)對(duì)應(yīng)的位。例如一個(gè)QQ號(hào)是：983262245，則將bit的98326625位進(jìn)行標(biāo)記。bitset是C++提供的一種位集合的數(shù)據(jù)結(jié)構(gòu)，它讓我們可以像使用數(shù)組一樣使用位，可以訪問指定下標(biāo)的bit位。因此將通過bitset容器進(jìn)行存儲(chǔ)42個(gè)qq號(hào)碼。由于一個(gè)字節(jié)可以存放8個(gè)QQ號(hào)碼，則4200000000/8/1014/1024 = 500.679Mb，內(nèi)存合適，通過bit位下表來判斷QQ號(hào)碼是否存在。

#include<iostream>
#include<bitset>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const unsigned int MAX = 4200000010;
typedef unsigned int UT;
bitset<MAX> bit;
int main(){
?? ?//開始存儲(chǔ)QQ
?? ?for(UT i=1;i<10;i++){
?? ??? ?UT qq;
?? ??? ?printf("請(qǐng)輸入第%d個(gè)QQ號(hào):",i);
?? ??? ?scanf("%d",&qq);?
?? ??? ?bit.set(qq);
?? ?}?
?? ?UT qq;
?? ?printf("請(qǐng)輸入:");
?? ?while(scanf("%d",&qq)!=0){
?? ??? ??? ?
?? ??? ?if(bit.test(qq)){
?? ??? ??? ?printf("Yes\n");
?? ??? ?}
?? ??? ?printf("請(qǐng)輸入:");
?? ?}
?? ?return 0;
}?
存儲(chǔ)：空間占用大約500Mb

查找：時(shí)間復(fù)雜度為O(1)

通過位排序的方法，在實(shí)現(xiàn)內(nèi)存內(nèi)，實(shí)現(xiàn)在O(1)時(shí)間復(fù)雜度內(nèi)進(jìn)行一個(gè)QQ號(hào)碼的查找。
?

---

package bitmap;import java.math.BigInteger; import java.util.BitSet; import java.util.Scanner;public class BitMap {private static final int MAX = 420000010;public static void main(String[] args) {BitSet bitSet = new BitSet(MAX);int[] qq = {111111111,222222222,333333333,444444444,555555555};for(int i = 0;i<qq.length;i++){bitSet.set(qq[i]);}Scanner scanner = new Scanner(System.in);while(scanner.hasNext()){int num = scanner.nextInt();if(bitSet.get(num)){System.out.println("在");}else{System.out.println("不在");}}}}

總結(jié)

以上是生活随笔為你收集整理的海量数据处理：BitMap的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。