C#位圖BitArray 小試牛刀

前面聊了布隆過濾器，回歸認(rèn)識一下位圖BitMap，閱讀前文的同學(xué)應(yīng)該發(fā)現(xiàn)了布隆過濾器本身就是基于位圖，是位圖的一種改進(jìn)。

難纏的布隆過濾器，這次終于通透了

位圖

先看一個問題， 假如有1千萬個整數(shù)，整數(shù)范圍在1到1億之間，如何快速確定某個整數(shù)是否在這個1千萬個整數(shù)中呢？

乍一看是一個查找問題，循環(huán)、二分查找都是常規(guī)思路。

一個好的答案是數(shù)據(jù)結(jié)構(gòu)和算法的完美結(jié)合， 基于題干上的特征和條件，我們是否有其他思路。

對于題干我們使用高中排列組合的思維：有1億個按順序編號的空籃子，我們拿出這1千萬個有數(shù)字的球，放進(jìn)對應(yīng)的籃子。

最后，所有的籃子有兩種狀態(tài)：有球/無球，我們要確定某個數(shù)字是否存在，就看對應(yīng)籃子是否為空。

什么是位圖？每一位存放某種狀態(tài)，適用于海量數(shù)據(jù)，通常用于判斷數(shù)據(jù)是否存在。位圖的空間由數(shù)據(jù)的最大值決定。

位圖這種數(shù)據(jù)結(jié)構(gòu)來大大節(jié)省內(nèi)存的使用量。

我們只需要構(gòu)造一個長度為1億的bit數(shù)組，將有球位置標(biāo)記為1，無球位置默認(rèn)記為0；這樣我們就將數(shù)字轉(zhuǎn)換成了一個被壓縮緊致的數(shù)組索引，1億bit數(shù)組不到16M空間。

確定某位置有球，O(1)的時間復(fù)雜度。

C# 有專業(yè)的位圖數(shù)組：BitArray

usingSystem;usingSystem.Collections;namespaceBitmap{classProgram{staticvoidMain(string[] args){var input =Console.ReadLine();var num =int.Parse(input);var bitmap =InitBitMap();if(bitmap.Get(num)){Console.WriteLine($"找到數(shù)字{num}");}else{Console.WriteLine($"未找到數(shù)字{num}");}}publicstaticBitArrayInitBitMap(){var myBA1 =newBitArray(10000);var arr1 =newint[]{1,2,4,6,77,77,88,99,100,500,600,700,999,8888};foreach(int element in arr1){                myBA1[element]=true;}return myBA1;}}}

BitArray是管理位值的緊湊數(shù)組，用布爾值表示，其中true表示位是開啟的(1)，false表示位是關(guān)閉的(0)， 是引用類型，位于System.Collections命名空間。

以上只是小試牛刀，我們針對原題再發(fā)散一下，如何找到以上1千萬整數(shù)中重復(fù)的數(shù)字？

還是籃子中放球的思路，這次我們要兩排籃子，也就是兩個BitMap，利用位AND運算(同時為True，結(jié)果才是True）找到兩排籃子中均有球的位置。

usingSystem;usingSystem.Collections;namespaceBitmap{classProgram{staticvoidMain(string[] args){var bitmap =InitBitMap();for(int i =0; i < bitmap.Length; i++){if(bitmap[i]==true){Console.WriteLine(i);}}}publicstaticBitArrayInitBitMap(){var myBA1 =newBitArray(10000);var myBA2 =newBitArray(10000);var arr1 =newint[]{1,2,4,6,77,77,88,99,100,500,600,700,999,8888};foreach(int element in arr1){if(myBA1[element]==false){                    myBA1[element]=true;}else{                    myBA2[element]=true;}}            myBA1 = myBA1.And(myBA2);return myBA1;}}}

最后提醒各位：寶藏組件Redis天然支持位圖

我是有態(tài)度的馬甲， 不追熱點，原創(chuàng)輸出#八股文#硬核干貨#職場心得#，歡迎關(guān)注。