十億數據量 判斷元素是否存在

核心是采用：bitMap

假設一個場景，要存0-7之內的數字[3,5,6,1,2]，盡量的節省空間。

傳統思路就是單純使用集合存儲：

使用redis的set集合存儲，但若是數據量放大到十億級別，集合的所占用的內存會很是大。並且，redis單個實例最大為2.5億。

另外一種思路是使用BitMap：

錶示[3,5,7,1,2]，咱們能够用8bit的空間來存儲，每一個數字都在對應的比特置中以1的方式錶示

比特置7	比特置 6	比特置 5	比特置 4	比特置 3	比特置 2	比特置 1	比特置 0
1	0	1	0	1	1	1	0

這樣，相當於每一比特只存儲了一個字符，只需要知道該下標是否為1，即可。

這裏是不是就會發現，存儲的數據必須為正整數，才可以使用bitMap進行存儲。

所以我們需要做的就是，把數據轉換成：正整數。

我們采用google開源的cityhash算法，先將string轉換為32比特整數，然後構建512MB的bitmap存儲這些整數。

為什麼是32比特呢，因為redis實現了bitMap算法，可以從用redis的setBit進行數據存儲。但是因為redis官方規定：setting bit number 2^32 -1；也就是說，存儲的正整數必須小於32比特。

有一個很好的工具類hutool，實現了cityhash算法，直接引用：

        <dependency>
            <groupId>cn.hutool</groupId>
            <artifactId>hutool-all</artifactId>
            <version>5.8.2</version>
        </dependency>

        String code="237021200005599";
        byte[] codebyte = code.getBytes();
        int codeInt = HashUtil.cityHash32(codebyte);
        System.out.println(codeInt);

 但是由於，HashUtil.cityHash32返回的是int，是一個整數，redis的bitMap僅支持正整數，存在差异性，所以我不會了。最好存進去的數就是一個32比特正整數。

還有一個辦法就是下面這個：不要使用redis的bitMap

RoaringBitmap 和 Roaring64Bitmap

32比特以下數據直接使用 RoaringBitmap；（包含負數）

64比特以下數據直接使用 Roaring64Bitmap；（包含負數）

使用hutool工具，轉換成64比特的整數，Roaring64Bitmap直接支持Long類型。

        <dependency>
            <groupId>org.roaringbitmap</groupId>
            <artifactId>RoaringBitmap</artifactId>
            <version>0.9.0</version>
        </dependency>

        //將字符串轉換成64比特bit
        String code="ddadsadsa";
        byte[] codebyte = code.getBytes();
        Long codeInt = HashUtil.cityHash64(codebyte);

        //將Long插入到bitMap中
        Roaring64Bitmap rr = Roaring64Bitmap.bitmapOf();
        rr.add(codeInt);

        long l = -4543844943551498834L;

        //判斷是否存在
        System.out.println(rr.contains(l));

參考文章：BitMap與RoaringBitmap、JavaEWAH - JavaShuo