Bitmap 簡介

1.  BitMap

Bit-map 的基本思想就是用一個 bit 位來標記某個元素對應的 Value,而 Key 即是該元素。由於採用了 Bit 爲單位來存儲數據,因此在存儲空間方面,可以大大節省。(PS:劃重點 節省存儲空間

假設有這樣一個需求:在 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.2****33G

高下立判,無需多言

那麼,問題來了,如何表示一個數呢?

剛纔說了,每一位表示一個數,0 表示不存在,1 表示存在,這正符合二進制

這樣我們可以很容易表示 {1,2,4,6} 這幾個數:

計算機內存分配的最小單位是字節,也就是 8 位,那如果要表示 {12,13,15} 怎麼辦呢?

這樣的話,好像變成一個二維數組了

1 個 int 佔 32 位,那麼我們只需要申請一個 int 數組長度爲 int tmp[1+N/32] 即可存儲,其中 N 表示要存儲的這些數中的最大值,於是乎:

tmp[0]:可以表示 0~31

tmp[1]:可以表示 32~63

tmp[2]:可以表示 64~95

。。。

如此一來,給定任意整數 M,那麼 M/32 就得到下標,M%32 就知道它在此下標的哪個位置

添加

這裏有個問題,我們怎麼把一個數放進去呢?例如,想把 5 這個數字放進去,怎麼做呢?

首先,5/32=0,5%32=5,也是說它應該在 tmp[0] 的第 5 個位置,那我們把 1 向左移動 5 位,然後按位或

換成二進制就是

這就相當於 86 | 32 = 118

86 | (1<<5) = 118

b[0] = b[0] | (1<<5)

也就是說,要想插入一個數,將 1 左移帶代表該數字的那一位,然後與原數進行按位或操作

化簡一下,就是 86 + (5/8) | (1<<(5%8))

因此,公式可以概括爲:p + (i/8)|(1<<(i%8)) 其中,p 表示現在的值,i 表示待插入的數

清除 

以上是添加,那如果要清除該怎麼做呢?

還是上面的例子,假設我們要 6 移除,該怎麼做呢?

從圖上看,只需將該數所在的位置爲 0 即可

1 左移 6 位,就到達 6 這個數字所代表的位,然後按位取反,最後與原數按位與,這樣就把該位置爲 0 了

b[0] = b[0] & (~(1<<6))

b[0] = b[0] & (~(1<<(i%8)))

查找 

前面我們也說了,每一位代表一個數字,1 表示有(或者說存在),0 表示無(或者說不存在)。通過把該爲置爲 1 或者 0 來達到添加和清除的小夥,那麼判斷一個數存不存在就是判斷該數所在的位是 0 還是 1

假設,我們想知道 3 在不在,那麼只需判斷 b[0] & (1<<3) 如果這個值是 0,則不存在,如果是 1,就表示存在

2.  Bitmap 有什麼用

大量數據的快速排序、查找、去重

快速排序

假設我們要對 0-7 內的 5 個元素 (4,7,2,5,3) 排序(這裏假設這些元素沒有重複), 我們就可以採用 Bit-map 的方法來達到排序的目的。

要表示 8 個數,我們就只需要 8 個 Bit(1Bytes),首先我們開闢 1Byte 的空間,將這些空間的所有 Bit 位都置爲 0,然後將對應位置爲 1。

最後,遍歷一遍 Bit 區域,將該位是一的位的編號輸出(2,3,4,5,7),這樣就達到了排序的目的,時間複雜度 O(n)。

優點:

缺點:

快速去重

20 億個整數中找出不重複的整數的個數,內存不足以容納這 20 億個整數。 

首先,根據 “內存空間不足以容納這 05 億個整數” 我們可以快速的聯想到 Bit-map。下邊關鍵的問題就是怎麼設計我們的 Bit-map 來表示這 20 億個數字的狀態了。其實這個問題很簡單,一個數字的狀態只有三種,分別爲不存在,只有一個,有重複。因此,我們只需要 2bits 就可以對一個數字的狀態進行存儲了,假設我們設定一個數字不存在爲 00,存在一次 01,存在兩次及其以上爲 11。那我們大概需要存儲空間 2G 左右。

接下來的任務就是把這 20 億個數字放進去(存儲),如果對應的狀態位爲 00,則將其變爲 01,表示存在一次;如果對應的狀態位爲 01,則將其變爲 11,表示已經有一個了,即出現多次;如果爲 11,則對應的狀態位保持不變,仍表示出現多次。

最後,統計狀態位爲 01 的個數,就得到了不重複的數字個數,時間複雜度爲 O(n)。

快速查找

這就是我們前面所說的了,int 數組中的一個元素是 4 字節佔 32 位,那麼除以 32 就知道元素的下標,對 32 求餘數(%32)就知道它在哪一位,如果該位是 1,則表示存在。

小結 & 回顧

Bitmap 主要用於快速檢索關鍵字狀態,通常要求關鍵字是一個連續的序列(或者關鍵字是一個連續序列中的大部分), 最基本的情況,使用 1bit 表示一個關鍵字的狀態(可標示兩種狀態),但根據需要也可以使用 2bit(表示 4 種狀態),3bit(表示 8 種狀態)。

Bitmap 的主要應用場合:表示連續(或接近連續,即大部分會出現)的關鍵字序列的狀態(狀態數 / 關鍵字個數  越小越好)。

32 位機器上,對於一個整型數,比如 int a=1 在內存中佔 32bit 位,這是爲了方便計算機的運算。但是對於某些應用場景而言,這屬於一種巨大的浪費,因爲我們可以用對應的 32bit 位對應存儲十進制的 0-31 個數,而這就是 Bit-map 的基本思想。Bit-map 算法利用這種思想處理大量數據的排序、查詢以及去重。

補充 1

在數字沒有溢出的前提下,對於正數和負數,左移一位都相當於乘以 2 的 1 次方,左移 n 位就相當於乘以 2 的 n 次方,右移一位相當於除 2,右移 n 位相當於除以 2 的 n 次方。

<< 左移,相當於乘以 2 的 n 次方,例如:1<<6   相當於 1×64=64,3<<4 相當於 3×16=48

右移,相當於除以 2 的 n 次方,例如:64>>3 相當於 64÷8=8

^  異或,相當於求餘數,例如:48^32 相當於 48%32=16

補充 2

不使用第三方變量,交換兩個變量的值

1 // 方式一
2 a = a + b;
3 b = a - b;
4 a = a - b;
5 
6 // 方式二
7 a = a ^ b;
8 b = a ^ b;
9 a = a ^ b;

3.  BitSet

BitSet 實現了一個位向量,它可以根據需要增長。每一位都有一個布爾值。一個 BitSet 的位可以被非負整數索引(PS:意思就是每一位都可以表示一個非負整數)。可以查找、設置、清除某一位。通過邏輯運算符可以修改另一個 BitSet 的內容。默認情況下,所有的位都有一個默認值 false。

可以看到,跟我們前面想的差不多

用一個 long 數組來存儲,初始長度 64,set 值的時候首先右移 6 位(相當於除以 64)計算在數組的什麼位置,然後更改狀態位

別的看不懂不要緊,看懂這兩句就夠了:

1 int wordIndex = wordIndex(bitIndex);
2 words[wordIndex] |= (1L << bitIndex);

4.  Bloom Filters

Bloom filter 是一個數據結構,它可以用來判斷某個元素是否在集合內,具有運行快速,內存佔用小的特點。

而高效插入和查詢的代價就是,Bloom Filter 是一個基於概率的數據結構:它只能告訴我們一個元素絕對不在集合內或可能在集合內。

Bloom filter 的基礎數據結構是一個 比特向量(可理解爲數組)。

主要應用於大規模數據下不需要精確過濾的場景,如檢查垃圾郵件地址,爬蟲 URL 地址去重,解決緩存穿透問題等

如果想判斷一個元素是不是在一個集合裏,一般想到的是將集合中所有元素保存起來,然後通過比較確定。鏈表、樹、散列表(哈希表)等等數據結構都是這種思路,但是隨着集合中元素的增加,需要的存儲空間越來越大;同時檢索速度也越來越慢,檢索時間複雜度分別是 O(n)、O(log n)、O(1)。

布隆過濾器的原理是,當一個元素被加入集合時,通過 K 個散列函數將這個元素映射成一個位數組(Bit array)中的 K 個點,把它們置爲 1 。檢索時,只要看看這些點是不是都是 1 就知道元素是否在集合中;如果這些點有任何一個 0,則被檢元素一定不在;如果都是 1,則被檢元素很可能在(之所以說 “可能” 是誤差的存在)。

BloomFilter 流程

  1. 首先需要 k 個 hash 函數,每個函數可以把 key 散列成爲 1 個整數;
  2. 初始化時,需要一個長度爲 n 比特的數組,每個比特位初始化爲 0;
  3. 某個 key 加入集合時,用 k 個 hash 函數計算出 k 個散列值,並把數組中對應的比特位置爲 1;
  4. 判斷某個 key 是否在集合時,用 k 個 hash 函數計算出 k 個散列值,並查詢數組中對應的比特位,如果所有的比特位都是 1,認爲在集合中。

1 <dependency>
2     <groupId>com.google.guava</groupId>
3     <artifactId>guava</artifactId>
4     <version>28.1-jre</version>
5 </dependenc

com.google.common.hash.BloomFilter

5.  文檔

http://llimllib.github.io/bloomfilter-tutorial/zh_CN/

https://www.cnblogs.com/geaozhang/p/11373241.html

https://www.cnblogs.com/huangxincheng/archive/2012/12/06/2804756.html

https://www.cnblogs.com/DarrenChan/p/9549435.html

本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源https://www.cnblogs.com/cjsblog/p/11613708.html