1.前言

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

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

2.1.基本概念

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

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

像上面的這個位圖，可以用來表示1，4，6：

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

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

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

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

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

2.3.位圖的劣勢

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

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

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

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

4.使用場景

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

每個無符號整數(shù)通常占用4個字節(jié)（32位），因此40億個無符號整數(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)這個功能可以借助BitMap。

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

40億無符號整數(shù)數(shù)據(jù)的總字節(jié)數(shù)是4000000000 字節(jié)，在位圖中1個10位的無符號整數(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來說，大大的節(jié)省了很多空間。

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

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

5.BitMap在Java中的使用

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

import java.util.BitSet;
 
public class BitmapExample {
    public static void main(String[] args) {
        // 創(chuàng)建一個BitSet實(shí)例
        BitSet bitmap = new BitSet();
 
        // 設(shè)置第5個位置為1，表示第5個元素存在
        bitmap.set(5);
 
        // 檢查第5個位置是否已設(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ū)間
 
        // 計算bitset中所有值為1的位的數(shù)量，相當(dāng)于計算設(shè)置了的元素個數(shù)
        int count = bitmap.cardinality();
        System.out.println("Number of set bits: " + count);
 
        // 清除第5個位置
        bitmap.clear(5);
 
        // 判斷位圖是否為空
        boolean isEmpty = bitmap.isEmpty();
        System.out.println("Is the bitset empty after clearing some bits? " + isEmpty);
    }
}

6.總結(jié) 

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

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

最新評論