C# 位圖BitArray的使用

更新時(shí)間：2021年06月28日 11:04:07 作者：有態(tài)度的馬甲

如果我們著重處理一個(gè)以位為單位的數(shù)據(jù)時(shí)，就可以考慮使用位數(shù)組。本文就介紹了C# 位圖BitArray的使用，感興趣的可以了解一下

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

位圖

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

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

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

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

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

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

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

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

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

常用屬性

Count BitArray中包含實(shí)例的個(gè)數(shù)

IsReadOnly 獲取一個(gè)值，該值指示BitArray是否為只讀

Item 獲取或設(shè)置BitArray中特定位置的值

Length 獲取或設(shè)置BitArray中元素的數(shù)目

常用的方法

And 和指定的BitArray中相應(yīng)的元素做and運(yùn)算

Or 按位或運(yùn)算

Xor 按位異或運(yùn)算

Not 取反所有元素

Get 獲取特定位置處的值

Set 設(shè)定特定位置處的值

SetAll 將BitArray中所有的元素設(shè)定為指定的值

public sealed class BitArray : ICollection, IEnumerable, ICloneable
{
    public BitArray(BitArray bits); //用已有的BitArray給新的BitArray初始化
    
    public BitArray(bool[] values); //用布爾數(shù)組初始化
    
    public BitArray(byte[] bytes);  //用字節(jié)數(shù)組初始化
    
    public BitArray(int length);    //初始化并設(shè)置位數(shù)值，此值會(huì)在使用中自動(dòng)增長(zhǎng)
    
    public BitArray(int[] values);  //用int數(shù)組初始化
    
    public BitArray(int length, bool defaultValue); //初始化并設(shè)置默認(rèn)值
    
    public int Count { get; }   //位數(shù)組中現(xiàn)存的位的個(gè)數(shù)
    
    public bool IsReadOnly { get; } //確定位數(shù)組是否只讀

    public bool IsSynchronized { get; } //是否同步對(duì)此BitArray的操作，用在線程安全上
    
    public int Length { get; set; }   //位數(shù)組的位數(shù)

    public object SyncRoot { get; }
    
    public bool this[int index] { get; set; } //索引器，利用索引讀位值
    
    public BitArray And(BitArray value);  //按位與

    public object Clone();  //創(chuàng)建BitArray 的淺表副本。
    
    public void CopyTo(Array array, int index);  //將BitArray拷貝到其他數(shù)組中
    
    public bool Get(int index);    //按下標(biāo)讀取位值

    public IEnumerator GetEnumerator(); //返回循環(huán)訪問(wèn)BitArray 的枚舉數(shù)

    public BitArray Not();  //按位非

    public BitArray Or(BitArray value);  //按位或
    
    public void Set(int index, bool value);  //按位設(shè)置值
    
    public void SetAll(bool value); //設(shè)置所有位為指定值

    public BitArray Xor(BitArray value);  //按位異或
}

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

using System;
using System.Collections;

namespace Bitmap
{
    class Program
    {
        static void Main(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}");
            }
        }
        public static BitArray InitBitMap()
        {
            var myBA1 = new BitArray(10000);
            var arr1 = new int[] { 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命名空間。

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

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

using System;
using System.Collections;

namespace Bitmap
{
    class Program
    {
        static void Main(string[] args)
        {
            var bitmap = InitBitMap();
            for (int i = 0; i < bitmap.Length; i++)
            {
                if(bitmap[i] == true)
                {
                    Console.WriteLine(i);
                }
            }
        }
        public static BitArray InitBitMap()
        {
            var myBA1 = new BitArray(10000);
            var myBA2 = new BitArray(10000);
            var arr1 = new int[] { 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天然支持位圖