[Алгоритм и сеанс структуры данных] Базовый код операции Реализация алгоритма BitMap

Java задняя часть алгоритм

В прошлой статье мы говорили о том, как BitMap хранит данные, если вы не видели, то можете взглянуть.【Алгоритм и структура данных】Введение в алгоритм BitMap

В этой статье поговорим о кодовой реализации структуры данных BitMap.

Пересмотреть принцип хранения данных

Двоичный бит соответствует неотрицательному числу n. Если n существует, значение соответствующего двоичного бита равно 1, иначе — 0.

На этот раз наш первый вопрос:

Когда мы используем byte, int, short, long и другие типы данных для хранения данных, все они занимают как минимум один байт памяти, то есть 8 бит, то есть минимальная единица операции составляет 8 бит. Не существует типа данных, которым можно манипулировать бит за битом.

В реализации BitMaP в Java для хранения используются длинные данные. Тип long занимает 8 байт, то есть 64 бита, поэтому в long может храниться 64 числа. Например, если arr является массивом типа long, в arr[0] можно хранить значения от 0 до 63, в arr[1] можно хранить от 64 до 127 и т. д.

Однако давайте воспользуемся массивом байтов для его хранения. Один байт занимает один байт, то есть 8 бит, в которых можно хранить 8 чисел.

Конечно, вы также можете использовать длинный массив для его хранения. Реализация, можно сказать, та же.

Например, когда мы хотим сохранить (1,3,5,7,8,10), их память выглядит так.

Теперь давайте немного поговорим о том, как оперировать.

Как добавить значение в растровое изображение

Давайте сначала поговорим о том, как добавить значение к растровому изображению, например, мы хотим добавить n=14.

На самом деле это очень просто, мы сначала находим нижний индекс n в массиве arr, очевидно, что index = 1. Затем найдите позицию n в arr[index], очевидно, здесь position = 6.

Здесь по-прежнему легко найти формулы для индекса и позиции. который

индекс = n / 8 = n >> 3.

позиция = n % 8 = n & 0x07.

Далее мы перемещаем 1 вправо на позиционные биты, а затем выполняем операцию «или (или)» с результатом и arr[index]. Как показано ниже

Здесь есть момент, на который следует обратить внимание: при рисовании для удобства мы используем бит слева какнизкий, правый бит принимается завысокоНу давай же. Однако в реальной памяти левая сторона хранит старшие биты, а правая — младшие. Таким образом, в нашей реализации кода то, что мы называем сдвигом вправо, соответствует сдвигу кода влево.

Код

//添加数据的操作

public void add(int n){
    //用>>的操作是，运算会比较快
    int index = n >> 3;
    int position = n & 0x07;
    //把1右移和做or操作两步一起
    //即 << 对应上图的右移，实际上<<是左移符。
    arr[index] |= 1 << position;
}

Зная операцию добавления, другие операции почти аналогичны.

Конечно, операция добавления, которую мы реализовали, — это всего лишь простая реализация, и если вы хотите реализовать ее строго, вам все равно потребуется много ненормальных суждений. Например, определение того, является ли число неотрицательным, определение того, не выходит ли нижний индекс массива arr за пределы, расширение емкости и т. д. Те, кто заинтересован, могут реализовать его неукоснительно.

удалить операцию.

Нам просто нужно изменить соответствующий бинарный 1 на 0.

Мы можем инвертировать результат после сдвига 1 вправо (соответствующий сдвиг влево в коде), а затем выполнить операцию «И» с arr[index]. код показывает, как показано ниже:

public void delete(int n){
    int index = n >> 3;
    int position = n & 0x07;
    arr[index] &= ~(1 << position);
}

Определить, есть ли операция

После того, как мы сдвинули 1 вправо, мы выполняем операцию И с результатом и arr[index].Если результат не равен 0, это доказывает, что он существует, иначе он не существует.

public boolean contain(int n){
    int index = n >> 3;
    int position = n & 0x07;
    return (arr[index] & (1 << position)) != 0;
}

В основном реализованы три самых основных операционных кода.

Я надеюсь, что каждый сможет это практиковать.

Полный код:

public class BitMap {
    private byte[] arr;
    //容量，即最多能够存多少个数据
    private int capacity;

    public BitMap(int capacity) {
        this.capacity = capacity;
        //一个byte可以存8个数据，capacity实际上指的是多少个bit
        arr = new byte[(capacity / 8 + 1)];
    }

    //添加数据的操作

    public void add(int n){
        //用>>的操作是，运算会比较快
        int index = n >> 3;
        int position = n & 0x07;
        //把1右移和做or操作两步一起
        //即 << 对应上图的右移，实际上<<是左移符。
        arr[index] |= 1 << position;
    }

    public void delete(int n){
        int index = n >> 3;
        int position = n & 0x07;
        arr[index] &= ~(1 << position);
    }

    public boolean contain(int n){
        int index = n >> 3;
        int position = n & 0x07;
        return (arr[index] & (1 << position)) != 0;
    }
}

вопрос

После прочтения приведенного выше кода вы обнаружили какие-либо проблемы?

Например, если мы сохраняем только 1 число в растровом изображении, а сохраненное значение равно 2000000000, мы изменим 0 на 1 в 2000000000-м двоичном файле. То есть размер массива arr не менее 2000000000/8+1. Но в это время в предыдущих двоичных битах нет данных, разве это не супер-трата ресурсов?

Таким образом, то, как мы пишем это выше, можно сказать, чтоНасилиеСпособ написания не подвергся никакой оптимизации, на самом деле в битмапе, который поставляется с Java, есть много оптимизаций, и он не будет тратить ресурсы места, как код, который мы реализовали выше. Желающие могут изучить его.

Что касается того, как оптимизировать, я расскажу об этом в следующей статье, ждите с нетерпением.

получить большеоригинальныйСтатья, можете обратить внимание на мой публичный номер:трудолюбивый кодер, я буду время от времени делиться некоторыми ресурсами и программным обеспечением. Фоновый ответподарочный пакетОтправьте вам подарочный пакет популярных ресурсов и спасибо за то, что вы представили статью большему количеству нуждающихся

Категории