Как работает битовая карта?

Как работает битовая карта

Битовая карта (bitmap) — это эффективная структура данных для хранения информации о наличии/отсутствии элементов. Это один из классических примеров оптимизации памяти в программировании.

Основной принцип

Битовая карта использует один бит для хранения одного булевого значения (есть/нет, 0/1). В отличие от массива boolean, где каждый элемент занимает минимум 1 байт (8 бит), битовая карта экономит память в 8 раз.

Концептуально:

Обычный массив boolean: [true, false, true, false, true]
Память: 5 байт (40 бит) → 11010... в памяти

Битовая карта: 11010 (в одном байте)
Память: 1 байт (8 бит)

Реализация в Java

Используем массив целых чисел (обычно long):

public class BitMap {
    private long[] bits;
    private int size;
    
    public BitMap(int size) {
        this.size = size;
        // Каждый long содержит 64 бита
        this.bits = new long[(size + 63) / 64]; // Округляем вверх
    }
    
    // Установить бит в 1 (set)
    public void set(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        int wordIndex = index / 64;  // Какой long
        int bitIndex = index % 64;   // Какой бит внутри long
        bits[wordIndex] |= (1L << bitIndex);
    }
    
    // Установить бит в 0 (clear)
    public void clear(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        int wordIndex = index / 64;
        int bitIndex = index % 64;
        bits[wordIndex] &= ~(1L << bitIndex);
    }
    
    // Проверить значение бита
    public boolean get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        int wordIndex = index / 64;
        int bitIndex = index % 64;
        return (bits[wordIndex] & (1L << bitIndex)) != 0;
    }
}

Пример использования

BitMap bitmap = new BitMap(100);

// Отметить присутствие элементов 5, 10, 99
bitmap.set(5);
bitmap.set(10);
bitmap.set(99);

// Проверить
System.out.println(bitmap.get(5));   // true
System.out.println(bitmap.get(6));   // false
System.out.println(bitmap.get(99));  // true

// Удалить
bitmap.clear(10);
System.out.println(bitmap.get(10));  // false

Битовые операции

Операции, на которых это основано:

// Побитовое ИЛИ (OR) — установить бит
long word = 0b0000_0000;
word |= (1L << 3);  // Установить 3-й бит
// word = 0b0000_1000

// Побитовое И (AND) с инверсией — очистить бит
word &= ~(1L << 3); // Очистить 3-й бит
// word = 0b0000_0000

// Побитовое И для проверки
boolean isBitSet = (word & (1L << 3)) != 0;

Реальные применения

1. Фильтр Блума — вероятностная структура для быстрой проверки наличия элемента

public class BloomFilter {
    private BitMap bitMap;
    private int[] hashes;
    
    public void add(String element) {
        for (int h : hash(element)) {
            bitMap.set(h % bitMap.size());
        }
    }
    
    public boolean contains(String element) {
        for (int h : hash(element)) {
            if (!bitMap.get(h % bitMap.size())) {
                return false; // Определённо нет
            }
        }
        return true; // Вероятно да
    }
}

2. Кеширование и индексирование:

• Быстрая проверка, какие страницы в памяти
• Отслеживание занятых блоков на диске

3. Представление множества:

• Вместо HashSet можно использовать битовую карту, если элементы — небольшие целые числа

// Вместо Set<Integer> для чисел 0-1000000
BitMap set = new BitMap(1000001);
set.set(5);
set.set(100);
// В 1000 раз меньше памяти!

Преимущества и недостатки

Преимущества:

• ✅ Минимальное потребление памяти (1 бит на элемент)
• ✅ O(1) операции set/clear/get
• ✅ Быстрые побитовые операции для массовых проверок

Недостатки:

• ❌ Работает только с небольшим диапазоном целых чисел
• ❌ Не гибкая для больших разреженных множеств
• ❌ Требует предварительного знания размера

Java BitSet класс

Java уже предоставляет встроенный класс:

BitSet bitSet = new BitSet(100);
bitSet.set(5);
bitSet.set(10);
bitSet.set(99);

System.out.println(bitSet.get(5));    // true
System.out.println(bitSet.cardinality()); // 3 — количество установленных битов

// Операции с множествами
BitSet other = new BitSet(100);
other.set(5);
other.set(6);
bitSet.and(other);   // Пересечение
bitSet.or(other);    // Объединение
bitSet.xor(other);   // Исключающее ИЛИ

Битовая карта — это красивый пример того, как глубокое понимание битовых операций и структур данных позволяет написать крайне эффективный код.