1 Java位集合

前幾天剛學習了Redis中位操作命令，今天順便學下java中位集合

1.1 Bit-Map

1.1.1 簡介

Bit-map的基本思想就是用一個bit位來標記某個元素對應的Value，而Key即是該元素。由于采用了Bit為單位來存儲數據，因此在存儲空間方面，可以大大節(jié)省。（即：節(jié)省存儲空間 ）

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

Bitmap的主要應用場合：表示連續(xù)（或接近連續(xù)，即大部分會出現）的關鍵字序列的狀態(tài)（狀態(tài)數/關鍵字個數 越小越好）。
32位機器上，對于一個整型數，比如int a=1 在內存中占32bit位(一個字寬即4Byte)，這是為了方便計算機的運算。但是對于某些應用場景而言，這屬于一種巨大的浪費，因為我們可以用對應的32bit位對應存儲十進制的0-31個數，而這就是Bit-map的基本思想。Bit-map算法利用這種思想處理大量數據的排序、查詢以及去重。

假設有這樣一個需求：

在20億個隨機整數中找出某個數m是否存在其中，并假設32位操作系統(tǒng)，4G內存
在Java中，int占4字節(jié)，1字節(jié)=8位（1 byte = 8 bit）
如果每個數字用int存儲，那就是20億個int，因而占用的空間約為 (2000000000*4/1024/1024/1024)≈7.45 G如果按位存儲就不一樣了，20億個數就是20億位，占用空間約為 (2000000000/8/1024/1024/1024)≈0.233 G

Bit-Map的每一位表示一個數，0表示不存在，1表示存在，這正符合二進制，這樣我們可以很容易表示{1,2,4,6}這幾個數：

計算機內存分配的最小單位是字節(jié)，也就是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就知道它在此下標的哪個位置

1.1.2 添加

這里有個問題，我們怎么把一個數放進去呢？例如，想把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表示待插入的數

1.1.3 清除

以上是添加，那如果要清除該怎么做呢？

還是上面的例子，假設我們要6移除，該怎么做呢？

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

首先把1左移6位，就到達6這個數字所代表的位，然后按位取反，最后與原數按位與，這樣就把該位置為0了

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

1.1.4 查找

前面我們也說了，每一位代表一個數字，1表示有（或者說存在），0表示無（或者說不存在）。通過把該為置為1或者0來達到添加和清除的效果，那么判斷一個數存不存在就是判斷該數所在的位是0還是1

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

1.2 Bitmap應用

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

1.2.1 快速排序

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

要表示8個數，我們就只需要8個Bit（1Bytes），首先我們開辟1Byte的空間，將這些空間的所有Bit位都置為0，然后將對應位置為1。

最后，遍歷一遍Bit區(qū)域，將該位是一的位的編號輸出（2，3，4，5，7），這樣就達到了排序的目的，時間復雜度O(n)。

優(yōu)點:

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

缺點:

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

1.2.2 快速去重

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

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

接下來的任務就是把這20億個數字放進去（存儲），如果對應的狀態(tài)位為00，則將其變?yōu)?1，表示存在一次；如果對應的狀態(tài)位為01，則將其變?yōu)?1，表示已經有一個了，即出現多次；如果為11，則對應的狀態(tài)位保持不變，仍表示出現多次。

最后，統(tǒng)計狀態(tài)位為01的個數，就得到了不重復的數字個數，時間復雜度為O(n)。

1.2.3 快速查找

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

1.3 BitSet

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

public class BitSet implements Cloneable, java.io.Serializable {
    /*
     * BitSets are packed into arrays of "words."  Currently a word is
     * a long, which consists of 64 bits, requiring 6 address bits.
     * The choice of word size is determined purely by performance concerns.
     */
    private final static int ADDRESS_BITS_PER_WORD = 6;
    private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
    private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;

    /* Used to shift left or right for a partial word mask */
    private static final long WORD_MASK = 0xffffffffffffffffL;

    /**
     * @serialField bits long[]
     *
     * The bits in this BitSet.  The ith bit is stored in bits[i/64] at
     * bit position i % 64 (where bit position 0 refers to the least
     * significant bit and 63 refers to the most significant bit).
     */
    private static final ObjectStreamField[] serialPersistentFields = {
        new ObjectStreamField("bits", long[].class),
    };

    /**
     * The internal field corresponding to the serialField "bits".
     */
    private long[] words;

    /**
     * The number of words in the logical size of this BitSet.
     */
    private transient int wordsInUse = 0;

    /**
     * Given a bit index, return word index containing it.
     */
    private static int wordIndex(int bitIndex) {
        return bitIndex >> ADDRESS_BITS_PER_WORD;
    }
    /**
     * Creates a new bit set. All bits are initially {@code false}.
     */
    public BitSet() {
        initWords(BITS_PER_WORD);
        sizeIsSticky = false;
    }

    /**
     * Creates a bit set whose initial size is large enough to explicitly
     * represent bits with indices in the range {@code 0} through
     * {@code nbits-1}. All bits are initially {@code false}.
     *
     * @param  nbits the initial size of the bit set
     * @throws NegativeArraySizeException if the specified initial size
     *         is negative
     */
    public BitSet(int nbits) {
        // nbits can't be negative; size 0 is OK
        if (nbits < 0)
            throw new NegativeArraySizeException("nbits < 0: " + nbits);

        initWords(nbits);
        sizeIsSticky = true;
    }
 private void initWords(int nbits) {
        words = new long[wordIndex(nbits-1) + 1];
    }

用一個long數組來存儲，初始長度64，set值的時候首先右移6位（相當于除以64）計算在數組的什么位置，然后更改狀態(tài)位

別的看不懂不要緊，看懂這兩句就夠了：

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

1.4 Bloom Filters

1.4.1 簡介

Bloom filter 是一個數據結構，它可以用來判斷某個元素是否在集合內，具有運行快速，內存占用小的特點。
而高效插入和查詢的代價就是，Bloom Filter 是一個基于概率的數據結構：它只能告訴我們一個元素絕對不在集合內或可能在集合內。
Bloom filter 的基礎數據結構是一個 比特向量（可理解為數組）。
主要應用于大規(guī)模數據下不需要精確過濾的場景，如檢查垃圾郵件地址，爬蟲URL地址去重，解決緩存穿透問題等

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

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

1.4.2 BloomFilter 流程

BloomFilter 流程：

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

1.4.3 應用場景

布隆過濾器因為他的效率非常高，所以被廣泛的使用，比較典型的場景有以下幾個：

• 網頁爬蟲： 爬蟲程序可以使用布隆過濾器來過濾掉已經爬取過的網頁，避免重復爬取和浪費資源。
• 緩存系統(tǒng)： 緩存系統(tǒng)可以使用布隆過濾器來判斷一個查詢是否可能存在于緩存中，從而減少查詢緩存的次數，提高查詢效率。布隆過濾器也經常用來解決緩存穿透的問題。
• 分布式系統(tǒng)： 在分布式系統(tǒng)中，可以使用布隆過濾器來判斷一個元素是否存在于分布式緩存中，避免在所有節(jié)點上進行查詢，減少網絡負載。
• 垃圾郵件過濾： 布隆過濾器可以用于判斷一個郵件地址是否在垃圾郵件列表中，從而過濾掉垃圾郵件。
• 黑名單過濾： 布隆過濾器可以用于判斷一個IP地址或手機號碼是否在黑名單中，從而阻止惡意請求。

1.4.4 如何使用

Java中可以使用第三方庫來實現布隆過濾器，常見的有Google Guava庫和Apache Commons庫以及Redis。

如Guava:

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class BloomFilterExample {
    public static void main(String[] args) {
        // 創(chuàng)建布隆過濾器，預計插入100個元素，誤判率為0.01
        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(), 100, 0.01);
        // 插入元素
        bloomFilter.put("Lynn");
        bloomFilter.put("666");
        bloomFilter.put("八股文");
        // 判斷元素是否存在
        System.out.println(bloomFilter.mightContain("Lynn")); // true
        System.out.println(bloomFilter.mightContain("張三"));  // false
    }
}

Apache Commons:

import org.apache.commons.lang3.StringUtils;
import org.apache.commons.collections4.BloomFilter;
import org.apache.commons.collections4.functors.HashFunctionIdentity;
public class BloomFilterExample {
    public static void main(String[] args) {
        // 創(chuàng)建布隆過濾器，預計插入100個元素，誤判率為0.01
        BloomFilter<String> bloomFilter = new BloomFilter<>(HashFunctionIdentity.hashFunction(StringUtils::hashCode), 100, 0.01);
        // 插入元素
        bloomFilter.put("Lynn");
        bloomFilter.put("666");
        bloomFilter.put("八股文");
        // 判斷元素是否存在
        System.out.println(bloomFilter.mightContain("Lynn")); // true
        System.out.println(bloomFilter.mightContain("張三"));  // false
    }
}

Redis中可以通過Bloom模塊來使用，使用Redisson可以：

首先創(chuàng)建一個RedissonClient對象，然后通過該對象獲取一個RBloomFilter對象，使用tryInit方法來初始化布隆過濾器，指定了最多能添加的元素數量為100，誤判率為0.01。

然后，使用add方法將元素"犬小哈"、"666"和"八股文"添加到布隆過濾器中，使用contains方法來檢查元素是否存在于布隆過濾器中。

Config config = new Config();
config.useSingleServer().setAddress("redis://127.0.0.1:6379");
RedissonClient redisson = Redisson.create(config);
RBloomFilter<String> bloomFilter = redisson.getBloomFilter("myfilter");
bloomFilter.tryInit(100, 0.01);
bloomFilter.add("Lynn");
bloomFilter.add("666");
bloomFilter.add("八股文");
System.out.println(bloomFilter.contains("Lynn"));
System.out.println(bloomFilter.contains("張三"));
redisson.shutdown();

或者Jedis也可以：

Jedis jedis = new Jedis("localhost");
jedis.bfCreate("myfilter", 100, 0.01);
jedis.bfAdd("myfilter", "Lynn");
jedis.bfAdd("myfilter", "666");
jedis.bfAdd("myfilter", "八股文");
System.out.println(jedis.bfExists("myfilter", "Lynn"));
System.out.println(jedis.bfExists("myfilter", "張三"));
jedis.close();

總結 

到此這篇關于Java位集合之BitMap、BitSet和布隆過濾器的文章就介紹到這了,更多相關Java位集合BitMap、BitSet和布隆過濾器內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論