導(dǎo)語(yǔ)：

位圖（Bitmap）是一種高效存儲(chǔ)和操作大量布爾值的數(shù)據(jù)結(jié)構(gòu)。本文將從基礎(chǔ)概念講起，逐步深入位圖的原理、應(yīng)用場(chǎng)景及Java實(shí)現(xiàn)，助你輕松掌握這一高頻面試知識(shí)點(diǎn)。

一、什么是位圖？

位圖（Bitmap） 是一種利用二進(jìn)制位（0或1）來(lái)存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。每個(gè)二進(jìn)制位代表一個(gè)狀態(tài)，常用于高效處理存在性判斷、去重、簽到統(tǒng)計(jì)等場(chǎng)景。

傳統(tǒng)方案 vs 位圖

• 傳統(tǒng)方案：使用boolean數(shù)組存儲(chǔ)數(shù)據(jù)，每個(gè)元素占1字節(jié)（8位）。

• 位圖方案：每個(gè)元素僅占1位，空間利用率提升8倍！

示例：存儲(chǔ)1000萬(wàn)個(gè)用戶的簽到狀態(tài)

• boolean[]需要約10MB（10000000 / 1024 / 1024 ≈ 9.54MB）

• 位圖僅需約1.25MB（10000000 / 8 / 1024 / 1024 ≈ 1.19MB）

二、位圖核心原理

1. 存儲(chǔ)結(jié)構(gòu)

• 使用連續(xù)的內(nèi)存塊（如int[]或long[]數(shù)組）存儲(chǔ)位數(shù)據(jù)。

• 計(jì)算位置：確定元素在數(shù)組中的索引和偏移量。

  • 索引：元素值 / 32（int占32位）

  • 偏移：元素值 % 32

2. 核心操作

• 設(shè)置位：將指定位置為1

• 清除位：將指定位置為0

• 查詢位：判斷指定位置是否為1

三、位圖應(yīng)用場(chǎng)景

1. 用戶簽到統(tǒng)計(jì)

• 用位圖的每一位代表用戶某天是否簽到。

• 每月簽到僅需31位，全年僅需365位。

2. 數(shù)據(jù)去重

• 快速判斷元素是否存在，避免重復(fù)插入。

3. 布隆過(guò)濾器

• 位圖是布隆過(guò)濾器實(shí)現(xiàn)的基礎(chǔ)結(jié)構(gòu)，用于高效判斷元素可能存在或絕對(duì)不存在。

四、Java位圖實(shí)現(xiàn)

1. 使用BitSet類

Java內(nèi)置的BitSet類提供了位圖操作API。

import java.util.BitSet;

public class BitSetDemo {
    public static void main(String[] args) {
        BitSet bitmap = new BitSet(100); // 初始化100位的位圖
        
        // 設(shè)置第5位為1（簽到）
        bitmap.set(5);
        
        // 檢查第5位是否為1
        System.out.println("第5天是否簽到：" + bitmap.get(5)); // true
        
        // 清除第5位
        bitmap.clear(5);
        System.out.println("清除后：" + bitmap.get(5)); // false
    }
}

2. 手動(dòng)實(shí)現(xiàn)位圖

通過(guò)int[]數(shù)組和位運(yùn)算手動(dòng)實(shí)現(xiàn)位圖：

public class CustomBitmap {
    private int[] bits; // 存儲(chǔ)位數(shù)據(jù)
    
    public CustomBitmap(int capacity) {
        // 計(jì)算需要多少個(gè)int來(lái)存儲(chǔ)capacity位
        bits = new int[(capacity >> 5) + 1]; // capacity/32 +1
    }
    
    // 設(shè)置位
    public void set(int pos) {
        int index = pos >> 5;       // 計(jì)算數(shù)組索引（等價(jià)于pos/32）
        int offset = pos & 0x1F;    // 計(jì)算偏移量（等價(jià)于pos%32）
        bits[index] |= (1 << offset); // 將指定位置1
    }
    
    // 清除位
    public void clear(int pos) {
        int index = pos >> 5;
        int offset = pos & 0x1F;
        bits[index] &= ~(1 << offset); // 將指定位清0
    }
    
    // 查詢位
    public boolean get(int pos) {
        int index = pos >> 5;
        int offset = pos & 0x1F;
        return (bits[index] & (1 << offset)) != 0;
    }

    public static void main(String[] args) {
        CustomBitmap bitmap = new CustomBitmap(100);
        bitmap.set(10); // 設(shè)置第10位
        System.out.println("第10位狀態(tài)：" + bitmap.get(10)); // true
        bitmap.clear(10);
        System.out.println("清除后：" + bitmap.get(10)); // false
    }
}

五、注意事項(xiàng)與優(yōu)化

1. 稀疏數(shù)據(jù)處理

• 當(dāng)數(shù)據(jù)非常稀疏時(shí)（如存儲(chǔ)1和1,000,000兩個(gè)值），位圖可能浪費(fèi)空間。

• 解決方案：使用壓縮位圖（如Roaring Bitmap）。

2. 線程安全

• BitSet非線程安全！多線程環(huán)境下需使用Collections.synchronized包裝或自定義鎖。

3. 動(dòng)態(tài)擴(kuò)容

• BitSet自動(dòng)擴(kuò)容，手動(dòng)實(shí)現(xiàn)的位圖需處理數(shù)組擴(kuò)容邏輯。

六、總結(jié)

位圖通過(guò)將每個(gè)元素壓縮到1位，大幅節(jié)省存儲(chǔ)空間，尤其適合處理海量布爾值場(chǎng)景。合理使用位圖，可顯著提升程序性能。但需根據(jù)數(shù)據(jù)分布選擇合適方案，避免空間浪費(fèi)。

到此這篇關(guān)于Java位圖Bitmap從入門到實(shí)戰(zhàn)應(yīng)用的文章就介紹到這了,更多相關(guān)Java位圖Bitmap詳解內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論