目錄
- 演算法原理
- 優點和缺點
- 演算法實作（C#）
- 演算法應用
- 參考文章
演算法原理
BitMap的基本思想就是用一個bit位來標記某個元素對應的Value，而Key即是該元素，由于采用了Bit為單位來存盤資料，因此可以大大節省存盤空間，
BitMap可以看成一種資料結構，
假設有這樣一個需求：在20億個隨機整數中找出某個數m是否存在其中，并假設32位作業系統，4G記憶體，
在Java中，int占4位元組，1位元組=8位（1 byte = 8 bit），
如果每個數字用int存盤，那就是20億個int，因而占用的空間約為 (2000000000*4/1024/1024/1024)≈7.45G
如果按位存盤就不一樣了，20億個數就是20億位，占用空間約為 (2000000000/8/1024/1024/1024)≈0.233G
優點和缺點
優點：由于采用了Bit為單位來存盤資料并建立映射關系來查找位置，因此可以大大減少存盤空間，加快在大量資料中查詢的時間，（有點哈希表的意思，但哈希中的value值資料型別可以豐富多樣，而BitMap最終查到的value只能表示簡單的幾種狀態，）
缺點：BitMap中的查詢結果（value）能表達的狀態有限，且所有的資料不能重復，即不可對重復的資料進行排序和查找，
演算法實作（C#）
.NET中已經實作了BitMap的資料結構——BitArray，建議使用BitMap演算法解決問題時直接使用官方的BitArray，
我參照.NET原始碼實作了一個簡化版的BitMap，以int陣列存盤位值（最多存21億個位值），代碼如下：
class BitMap
{
public int Length{ get{ return m_length;}
}
private int[] m_array;
private int m_length;
public BitMap(int length): this(length, false) { }
//索引根據需求添加
public bool this[int index]
{
get
{
return Get(index);
}
set
{
Set(index,value);
}
}
//分配空間以容納長度位值, 位陣列中的所有值都設定為defaultValue，
public BitMap(int length, bool defaultValue)
{
if (length < 0) {
throw new ArgumentOutOfRangeException("length", "長度值不能小于0");
}
int arrayLength = length > 0 ? (((length - 1) / 32) + 1) : 0;
m_array = new int[arrayLength];
m_length = length;
int fillValue = https://www.cnblogs.com/timefiles/p/defaultValue ? unchecked(((int)0xffffffff)) : 0;
for (int i = 0; i < m_array.Length; i++) {
m_array[i] = fillValue;
}
}
//回傳位置索引處的位值，
public bool Get(int index) {
if (index < 0 || index >= Length) {
throw new ArgumentOutOfRangeException("index", "索引值超出范圍");
}
return (m_array[index / 32] & (1 << (index % 32))) != 0;
}
//將位置索引處的位值設定為value，
public void Set(int index, bool value) {
if (index < 0 || index >= Length) {
throw new ArgumentOutOfRangeException("index", "索引值超出范圍");
}
if (value) {
m_array[index / 32] |= (1 << (index % 32));
} else {
m_array[index / 32] &= ~(1 << (index % 32));
}
}
}
演算法應用
問題1：給40億個不重復的unsigned int的整數，沒有排過序，然后再給一個數，如果快速判斷這個數是否在那40億個數當中，（解決海量資料中的查詢問題）
問題1解法：建立一個位集合，全部初始化為0，遍歷40億個不重復的整數，通過上述提供的一種映射（每個不重復的整數映射到給定的位）找到其位的位置，標記為1，判斷這個數是否在大整數集合中，即通過映射關系計算此整數的位位置，檢查是否為1，若為1，則存在，若為0，則不存在
問題2：資料庫里存了很多800電話號碼，數量特別大，以至于記憶體放不下，如何排序，時間比空間更重要？電話號碼類似于800-810-5555，（高效排序）
問題2解法：其實就是不重復的任意7位數及其之內的排序問題，我們用1位來表示電話是否出現，遍歷整個電話號序列，設定相應的位，遍歷位圖收集位被設定的號碼即可，查看上述的實作代碼
參考文章
演算法系列-bitmap演算法詳解和實作——CSDN
Bitmap簡介——博客園
經典演算法系列之(一) - BitMap——簡書
BitArray——.NET原始碼
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/1621.html
標籤：C#
下一篇：設計模式之配接器模式