1.前言

有許多方法可以用來(lái)去重，比如使用列表、集合等等，但這些方法通常只適用于一般情況。然而，當(dāng)涉及到大量數(shù)據(jù)去重時(shí)，常見(jiàn)的 Java Set、List，甚至是 Java 8 的新特性 Stream 流等方式就顯得不太合適了。在處理大量數(shù)據(jù)的需求場(chǎng)景下，我們不得不提及 BitMap。

2.什么是BitMap？有什么用？

2.1.基本概念

位圖（BitMap），基本思想就是用一個(gè)bit來(lái)標(biāo)記元素，bit是計(jì)算機(jī)中最小的單位，也就是我們常說(shuō)的計(jì)算機(jī)中的0和1，這種就是用一個(gè)位來(lái)表示的。

所謂位圖，其實(shí)就是一個(gè)bit數(shù)組，即每一個(gè)位置都是一個(gè)bit，其中的取值可以是0或者1

像上面的這個(gè)位圖，可以用來(lái)表示1，4，6：

如果不用位圖的話，我們想要記錄1，4，,6 這三個(gè)整型的話，就需要用三個(gè)unsigned int，已知每個(gè)unsigned int占4個(gè)字節(jié)，那么就是3_4 = 12個(gè)字節(jié)，一個(gè)字節(jié)有8 bit，那么就是 12_8 = 96 個(gè)bit。

所以，位圖最大的好處就是節(jié)省空間。

位圖有很多種用途，特別適合用在去重、排序等場(chǎng)景中，著名的布隆過(guò)濾器就是基于位圖實(shí)現(xiàn)的。

2.2.位圖的優(yōu)勢(shì)

• 空間效率優(yōu)勢(shì)：極大的節(jié)省了存儲(chǔ)空間，對(duì)于大量稀疏數(shù)據(jù)，特別是當(dāng)元素?cái)?shù)量遠(yuǎn)大于實(shí)際存在的項(xiàng)時(shí)，相比較于使用傳統(tǒng)的列表、集合等數(shù)據(jù)結(jié)構(gòu)，位圖的空間占用極小。
• 查詢速度：由于內(nèi)存訪問(wèn)時(shí)按字節(jié)或字進(jìn)行的。因此對(duì)單個(gè)元素的存在性檢查時(shí)間復(fù)雜度為O(1)，即常量時(shí)間，非?？焖佟?/li>
• 批量操作高效：對(duì)于批量插入、刪除和查詢操作，尤其是統(tǒng)計(jì)范圍內(nèi)元素的數(shù)量，位圖表現(xiàn)出優(yōu)秀的性能。

2.3.位圖的劣勢(shì)

但是位圖也有著一定的限制，那就是他只能表示0和1，無(wú)法存儲(chǔ)其他的數(shù)字。所以他只適合這種能表示true or false的場(chǎng)景。

3.BitMap和Int的區(qū)別

以Java中的int為例，來(lái)對(duì)比觀察BitMap的優(yōu)勢(shì)，再Java中，int類型通常需要32位，而BitMap使用1位就可以來(lái)標(biāo)識(shí)此元素是否存在，所以可以認(rèn)為BitMap占用的空間大小只有int類型的1/32，所以有大量數(shù)據(jù)判重時(shí)，使用BitMap也可以實(shí)現(xiàn)。

了解了什么是BitMap，那么我們就可以使用BitMap來(lái)解決大量數(shù)據(jù)去重的問(wèn)題

4.使用場(chǎng)景

假設(shè)我們有40億個(gè)無(wú)符號(hào)整數(shù)數(shù)據(jù)，并且都是10位的話，如果直接使用內(nèi)存來(lái)存儲(chǔ)，大約需要14.9GB 的空間。

每個(gè)無(wú)符號(hào)整數(shù)通常占用4個(gè)字節(jié)（32位），因此40億個(gè)無(wú)符號(hào)整數(shù)所需要的總字節(jié)數(shù)位4*4000000000字節(jié)。 總字節(jié)數(shù)轉(zhuǎn)換為GB：4*4000000000 / 1024 / 1024 /1024 = 14.9 GB

考慮到其中有一些重復(fù)的數(shù)據(jù)，即使這樣1G的空間基本上也是不夠的。所以想要實(shí)現(xiàn)這個(gè)功能可以借助BitMap。

如果使用位圖的話，40億萬(wàn)所需要的內(nèi)存大概也就是 476M

40億無(wú)符號(hào)整數(shù)數(shù)據(jù)的總字節(jié)數(shù)是4000000000 字節(jié)，在位圖中1個(gè)10位的無(wú)符號(hào)整數(shù)可以使用1 bit表示，然后1 字節(jié) = 8 位（bit）。 4000000000 bit * 1/8 求出字節(jié)數(shù)，再 / 1024得到占用的KB數(shù)，最后/ 1024得到占用的MB數(shù) 4000000000 * 1 /8 /1024/1024 = 476M

這樣相比于之前的14.9G來(lái)說(shuō)，大大的節(jié)省了很多空間。

比如要把數(shù)據(jù)"714771310"放到BitMap中，就需要找到第714771310這個(gè)位置，然后把他設(shè)置成1就可以了。

這樣，把40億個(gè)數(shù)字都放到BitMap之后，所有位置上是1的表示存在，不為1的表示不存在，相同的數(shù)據(jù)只需要設(shè)置一次1就可以了，那么，最終就把所有是1的數(shù)字遍歷出來(lái)就行了。

5.BitMap在Java中的使用

BitMap在Java中的具體實(shí)現(xiàn)時(shí)java.util中的BitSet，BitSet是一個(gè)可變大小的位向量，能夠動(dòng)態(tài)增長(zhǎng)以容納更多的數(shù)據(jù)，以下是BitSet基本使用示例：

import java.util.BitSet;
 
public class BitmapExample {
    public static void main(String[] args) {
        // 創(chuàng)建一個(gè)BitSet實(shí)例
        BitSet bitmap = new BitSet();
 
        // 設(shè)置第5個(gè)位置為1，表示第5個(gè)元素存在
        bitmap.set(5);
 
        // 檢查第5個(gè)位置是否已設(shè)置
        boolean exists = bitmap.get(5);
        System.out.println("Element at position 5 exists: " + exists);  // 輸出: Element at position 5 exists: true
 
        // 設(shè)置從索引10到20的所有位置為1
        bitmap.set(10, 21);  // 參數(shù)是包含起始點(diǎn)和不包含終點(diǎn)的區(qū)間
 
        // 計(jì)算bitset中所有值為1的位的數(shù)量，相當(dāng)于計(jì)算設(shè)置了的元素個(gè)數(shù)
        int count = bitmap.cardinality();
        System.out.println("Number of set bits: " + count);
 
        // 清除第5個(gè)位置
        bitmap.clear(5);
 
        // 判斷位圖是否為空
        boolean isEmpty = bitmap.isEmpty();
        System.out.println("Is the bitset empty after clearing some bits? " + isEmpty);
    }
}

6.總結(jié) 

本文簡(jiǎn)單的講解了如何使用BitMap進(jìn)行大量數(shù)據(jù)的去重，BitMap的空間占用極小，對(duì)單個(gè)元素的存在性檢查時(shí)間復(fù)雜度為O(1)，非?？焖?，除了BitMap外，我們也可以采取布隆過(guò)濾器來(lái)完成去重，但是布隆過(guò)濾器存在誤判問(wèn)題，可以根據(jù)實(shí)際場(chǎng)景來(lái)分析使用哪種方案

以上就是Java中利用BitMap位圖實(shí)現(xiàn)海量級(jí)數(shù)據(jù)去重的詳細(xì)內(nèi)容，更多關(guān)于Java BitMap數(shù)據(jù)去重的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論