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.233G

高下立判,無需多言

 

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

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

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

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

當然是在另一個8位上表示了:

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

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)。

優點

  • 運算效率高,不需要進行比較和移位;
  • 占用內存少,比如N=10000000;只需占用內存為N/8=1250000Byte=1.25M

缺點

  • 所有的數據不能重復。即不可對重復的數據進行排序和查找。
  • 只有當數據比較密集時才有優勢

快速去重

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/

http://www.afvbyw.live/geaozhang/p/11373241.html

http://www.afvbyw.live/huangxincheng/archive/2012/12/06/2804756.html

http://www.afvbyw.live/DarrenChan/p/9549435.html

 

posted @ 2019-10-14 09:51 廢物大師兄 閱讀(...) 評論(...) 編輯 收藏
ag二分彩