這里是碼農充電第一站，回復“666”，獲取一份專屬大禮包
作者：廢物大師兄
來源：www.cnblogs.com/cjsblog/p/11613708.html1、BitMap
Bit-map的基本思想就是用一個bit位來標記某個元素對應的Value，而Key即是該元素。由于采用了Bit為單位來存儲數(shù)據(jù)，因此在存儲空間方面，可以大大節(jié)省。（PS：劃重點 節(jié)省存儲空間）剛才說了，每一位表示一個數(shù)，0表示不存在，1表示存在，這正符合二進制這樣我們可以很容易表示{1,2,4,6}這幾個數(shù)：計算機內存分配的最小單位是字節(jié)，也就是8位，那如果要表示{12,13,15}怎么辦呢？1個int占32位，那么我們只需要申請一個int數(shù)組長度為 int tmp[1+N/32] 即可存儲，其中N表示要存儲的這些數(shù)中的最大值，于是乎：如此一來，給定任意整數(shù)M，那么M/32就得到下標，M%32就知道它在此下標的哪個位置。添加
這里有個問題，我們怎么把一個數(shù)放進去呢？例如，想把5這個數(shù)字放進去，怎么做呢？首先，5/32=0，5%32=5，也是說它應該在tmp[0]的第5個位置，那我們把1向左移動5位，然后按位或也就是說，要想插入一個數(shù)，將1左移帶代表該數(shù)字的那一位，然后與原數(shù)進行按位或操作化簡一下，就是 86 + (5/8) | (1<<(5%8))因此，公式可以概括為：p + (i/8)|(1<<(i%8)) 其中，p表示現(xiàn)在的值，i表示待插入的數(shù)。清除
1左移6位，就到達6這個數(shù)字所代表的位，然后按位取反，最后與原數(shù)按位與，這樣就把該位置為0了b[0] = b[0] & (~(1<<(i%8)))查找
前面我們也說了，每一位代表一個數(shù)字，1表示有（或者說存在），0表示無（或者說不存在）。通過把該為置為1或者0來達到添加和清除的小伙，那么判斷一個數(shù)存不存在就是判斷該數(shù)所在的位是0還是1。假設，我們想知道3在不在，那么只需判斷 b[0] & (1<<3) 如果這個值是0，則不存在，如果是1，就表示存在。2、Bitmap有什么用
大量數(shù)據(jù)的快速排序、查找、去重。快速排序
假設我們要對0-7內的5個元素(4,7,2,5,3)排序（這里假設這些元素沒有重復）,我們就可以采用Bit-map的方法來達到排序的目的。要表示8個數(shù)，我們就只需要8個Bit（1Bytes），首先我們開辟1Byte的空間，將這些空間的所有Bit位都置為0，然后將對應位置為1。最后，遍歷一遍Bit區(qū)域，將該位是一的位的編號輸出（2，3，4，5，7），這樣就達到了排序的目的，時間復雜度O(n)。- 占用內存少，比如N=10000000；只需占用內存為N/8=1250000Byte=1.25M
- 所有的數(shù)據(jù)不能重復。即不可對重復的數(shù)據(jù)進行排序和查找。
- 只有當數(shù)據(jù)比較密集時才有優(yōu)勢
快速去重
20億個整數(shù)中找出不重復的整數(shù)的個數(shù)，內存不足以容納這20億個整數(shù)。首先，根據(jù)“內存空間不足以容納這05億個整數(shù)”我們可以快速的聯(lián)想到Bit-map。下邊關鍵的問題就是怎么設計我們的Bit-map來表示這20億個數(shù)字的狀態(tài)了。其實這個問題很簡單，一個數(shù)字的狀態(tài)只有三種，分別為不存在，只有一個，有重復。因此，我們只需要2bits就可以對一個數(shù)字的狀態(tài)進行存儲了，假設我們設定一個數(shù)字不存在為00，存在一次01，存在兩次及其以上為11。那我們大概需要存儲空間2G左右。接下來的任務就是把這20億個數(shù)字放進去（存儲），如果對應的狀態(tài)位為00，則將其變?yōu)?1，表示存在一次；如果對應的狀態(tài)位為01，則將其變?yōu)?1，表示已經有一個了，即出現(xiàn)多次；如果為11，則對應的狀態(tài)位保持不變，仍表示出現(xiàn)多次。最后，統(tǒng)計狀態(tài)位為01的個數(shù)，就得到了不重復的數(shù)字個數(shù)，時間復雜度為O(n)。快速查找
這就是我們前面所說的了，int數(shù)組中的一個元素是4字節(jié)占32位，那么除以32就知道元素的下標，對32求余數(shù)（%32）就知道它在哪一位，如果該位是1，則表示存在。小結&回顧
Bitmap主要用于快速檢索關鍵字狀態(tài)，通常要求關鍵字是一個連續(xù)的序列（或者關鍵字是一個連續(xù)序列中的大部分）， 最基本的情況，使用1bit表示一個關鍵字的狀態(tài)（可標示兩種狀態(tài)），但根據(jù)需要也可以使用2bit（表示4種狀態(tài)），3bit（表示8種狀態(tài)）。Bitmap的主要應用場合：表示連續(xù)（或接近連續(xù)，即大部分會出現(xiàn)）的關鍵字序列的狀態(tài)（狀態(tài)數(shù)/關鍵字個數(shù) 越小越好）。32位機器上，對于一個整型數(shù)，比如int a=1 在內存中占32bit位，這是為了方便計算機的運算。但是對于某些應用場景而言，這屬于一種巨大的浪費，因為我們可以用對應的32bit位對應存儲十進制的0-31個數(shù)，而這就是Bit-map的基本思想。Bit-map算法利用這種思想處理大量數(shù)據(jù)的排序、查詢以及去重。補充1
在數(shù)字沒有溢出的前提下，對于正數(shù)和負數(shù)，左移一位都相當于乘以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^ 異或，相當于求余數(shù)，例如：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實現(xiàn)了一個位向量，它可以根據(jù)需要增長。每一位都有一個布爾值。一個BitSet的位可以被非負整數(shù)索引（PS：意思就是每一位都可以表示一個非負整數(shù)）?？梢圆檎?、設置、清除某一位。通過邏輯運算符可以修改另一個BitSet的內容。默認情況下，所有的位都有一個默認值false。用一個long數(shù)組來存儲，初始長度64，set值的時候首先右移6位（相當于除以64）計算在數(shù)組的什么位置，然后更改狀態(tài)位1 int wordIndex = wordIndex(bitIndex);
2 words[wordIndex] |= (1L << bitIndex);
4、Bloom Filters
主要應用于大規(guī)模數(shù)據(jù)下不需要精確過濾的場景，如檢查垃圾郵件地址，爬蟲URL地址去重，解決緩存穿透問題等。如果想判斷一個元素是不是在一個集合里，一般想到的是將集合中所有元素保存起來，然后通過比較確定。鏈表、樹、散列表（哈希表）等等數(shù)據(jù)結構都是這種思路，但是隨著集合中元素的增加，需要的存儲空間越來越大；同時檢索速度也越來越慢，檢索時間復雜度分別是O(n)、O(log n)、O(1)。布隆過濾器的原理是，當一個元素被加入集合時，通過 K 個散列函數(shù)將這個元素映射成一個位數(shù)組（Bit array）中的 K 個點，把它們置為 1 。檢索時，只要看看這些點是不是都是1就知道元素是否在集合中；如果這些點有任何一個 0，則被檢元素一定不在；如果都是1，則被檢元素很可能在（之所以說“可能”是誤差的存在）。BloomFilter 流程
- 首先需要 k 個 hash 函數(shù)，每個函數(shù)可以把 key 散列成為 1 個整數(shù)；
- 初始化時，需要一個長度為 n 比特的數(shù)組，每個比特位初始化為 0；
- 某個 key 加入集合時，用 k 個 hash 函數(shù)計算出 k 個散列值，并把數(shù)組中對應的比特位置為 1；
- 判斷某個 key 是否在集合時，用 k 個 hash 函數(shù)計算出 k 個散列值，并查詢數(shù)組中對應的比特位，如果所有的比特位都是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.BloomFilterhttp://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
