BitMap — очень часто используемая структура данных.Его идеи и принципы лежат в основе многих алгоритмов.Конечно, он широко используется в индексировании, сжатии данных и обработке больших объемов данных.
1. Введение
BitMap — очень распространенная структура данных, и ее идеи и принципы лежат в основе многих алгоритмов, таких как фильтр Блума.
Основной принцип BitMap — использовать бит для хранения определенного состояния (если вы не можете понять это, вы можете оглянуться назад, прочитав следующий текст), что подходит для крупномасштабных данных, но данных не так много состояния. Обычно он используется, чтобы определить, существуют ли определенные данные или нет.
Одной из его главных особенностей является то, что он занимает очень мало памяти, поэтому его часто оптимизируют для использования в больших данных.
Почему говорят, что он занимает меньше памяти? На самом деле подсказку можно увидеть из названия.В дословном переводе это называется битмап,но в графике это не битмап.Ключевое словоBit. Например, бит используется для представления int определенным образом, так что память полностью сжимается до 1/32 (1 int = 4 байта = 32 бита, PS: только теоретический расчет, 1/32 не будет на практике. Преувеличение, будет объяснено ниже), поэтому данные, которые изначально требовали 8G памяти, теперь требуют только 256M, разве это не весело? Конечно, некоторые концепции алгоритма будут подробно объяснены ниже.
2. Первый взгляд на BitMap
1. Концептуальное понимание
В так называемом BitMap битовый бит используется для обозначения значения, соответствующего элементу, а ключ — это элемент. Поскольку единица бит используется для хранения данных, это может значительно сэкономить место для хранения.
Например, есть массив int [2,6,1,7,3], который содержит 5 элементов, а размер памяти 5 * 32 = 160 бит.При выборке используйте индекс элемента, чтобы получить соответствующий бит.элемент.
Но если подумать по-другому, значение элемента используется как нижний индекс, и каждый бит нижнего индекса помечен битом.Если есть значение, то оно равно 1, иначе — 0. нужно открыть один в памяти.последовательные битыпространство, длина равна 8 (поскольку самый большой элемент приведенных выше данных равен 7, но начальную точку нижнего индекса необходимо рассматривать как 0), его можно выразить как:
Описание: Инициализировать BitMap длиной 8, начальное значение равно 0, а затем заполнить [2, 6, 1, 7, 3] в соответствующие индексы, синее поле на рисунке выше, то есть эти индексы Значение at установлено равным 1, поэтому оно выражается как:1 1 0 0 1 1 1 0. Объем памяти, занимаемый в это время, составляет 8 бит, в то время как исходный — 160 бит (кстати, объясните упомянутую выше 1/32, потому что мы открываем непрерывное пространство содержимого, поэтому будет избыточность).
2. Описание случая
① Случай 1: все еще указанный выше массив, требуется запросить, находится ли элемент 6 в массиве. Изначально нам нужно пройти весь массив, временная сложность O(n); Теперь нам нужно только проверить, равен ли байт с индексом 6 0 или 1. Если он равен 1, значит, он существует, и временная сложность напрямую сводится к O(1). Поэтому самый прямой сценарий применения: проверка дублирования данных.
② Случай 2: Есть два массива, определите повторяющиеся элементы в этих двух массивах. Первоначальный и наиболее очевидный подход заключается в использовании двухуровневого цикла for для оценки и сравнения. Но теперь вам нужно только И два конвертированных BirMaps, например: 11001110B & 10100000B = 10000000B, все результаты получены, повторяется только элемент 7. Конечно,Наиболее прямые сценарии применения:У каждого клиента своя метка.Если вам нужно найти клиентов, которые соответствуют как метке a, так и метке b, вам нужно только найти клиентов с меткой a и меткой b и выполнить описанные выше шаги.И операцияВот и все.
3. Дополнительные инструкции
① При фактическом использовании длина не будет произвольно установлена равной 8, как указано выше, а обычно устанавливается равной 32 (тип int) или 64 (тип long), по причине, см. исходный код BitSet ниже.
② В дополнение к операции И, упомянутой выше, конечно, допустимы операции логического ИЛИ и логического XOR.
③ Каждый бит может быть только 0 или 1, поэтому он может представлять только истину или ложь.Когда мы хотим сделать небольшое количество статистики, мы можем использовать 2-BitMap, то есть мы можем использовать 00, 01, 10, 11 для каждого бита.Соответственно представлять число 0, 1, 2, 11 вообще бессмысленно в это время.
3. Исходный код BitSet
1. Краткое описание
Для классической структуры данных BitMap в языке Java уже существует соответствующая реализация класса структуры данных java.util.BitSet(***@since***JDK1.0), и базовый принцип BitSet на самом деле заключается в использовании массива типа long для хранения элементов, поэтому, оглядываясь назад на упомянутую выше причину, когда он фактически используется, длина обычно обычная, потому что здесь используется long. type, а 1 long = 64 бита, поэтому размер данных будет целым числом, кратным 64.
/**
* The internal field corresponding to the serialField "bits".
*/
private long[] words;
Что касается того, почему BitSet в Java использует длинный массив вместо массива int, я думаю, что это должно быть из-за производительности языка Java, потому что в процессеРяд битовых операций, таких как логические иКогда необходимо выполнять битовые операции над элементами в двух массивах один за другим, одним из преимуществ использования long является то, что длина массива уменьшается, а также уменьшается количество обходов.
Короче говоря, это связано со сценой.Абстрактная концепция немного похожа на алгоритм сопоставления строк (indexOf) в Java, который использует алгоритм BF (извлечение методом грубой силы).Почему бы не использовать лучшее решение? Это не потому, что лучшее решение — это то, которое отстает в случае небольшого объема данных.
2. Переменные-члены
3. Метод строительства
Параметр параметризованной конструкции представляет собой длину элемента, а не размер массива, например, при передаче параметров 1 и 64 длина массива равна 1, а весь размер равен 64. передан параметр 65, длина массива равна 2, а размер равен 128, поскольку массив имеет тип long, а long может хранить 64-битные элементы.
4. функция initWords
Эта функция вызывается только в двух конструкторах для инициализации массива, а длина массива получается как workIndex(nbits-1) + 1.
5. функция wordIndex
Этот метод очень важен, он используется для получения индекса определенного числа в массиве слов, используемый алгоритм состоит в том, чтобы сдвинуть число вправо на 6 бит, почему? Потому что bitIndex >> 6 == bitIndex / (2^6) == bitIndex /64, а long составляет 64 байта.
6. Функция обеспечения емкости
Это еще один очень важный метод, который используется для динамического расширения, потому что во время инициализации мы не знаем, сколько данных нужно будет хранить в будущем.
7. Функции размера и длины
Метод size хорошо понятен, и то, что он возвращает, на самом деле является размером пространства массива, то естьДлина массива*64. Метод длины, глядя на исходный код, на самом деле немного неясен (qu) вяжущий (qiao), короче говоря, он возвращает «логический размер» BitSet, то естьИндекс самого установленного бита в BitSet увеличивается на 1.
Например, BitSet хранит два элемента, 10 и 50, а в это время BitMap: размер = 64, длина = 51.
8. Отступление
Остальные методы set, get и другие пока повторяться не будем.Одним словом, если вы хотите глубоко разобраться в исходном коде BitSet, вам необходимо иметь определенный уровень владения бинарными вычислениями. Я должен признать, что исходный код BitSet, дизайн многих деталей слишком деликатный.
4. Расширение
Если мы хотим обсудить расширение, либо высокоуровневое применение сцены, либо неадекватность алгоритма, вот балл для каждого:
①недостаточный: проблема с разреженными данными, например три элемента (1, 100, 10000000), длина, которую необходимо инициализировать, составляет 10000000, что очень неразумно. В настоящее время вы можете использоватьRoaring BitMapАлгоритмы для решения, и программы Java могут использовать **EWAHCompressedBitmap** Google для решения.
②расширять: проблема конфликта данных. Например, упомянутый выше сценарий приложения сканера заключается в хешировании URL-адреса и последующем сохранении хеш-значения в BitMap, но он должен столкнуться с затруднительной ситуацией, то есть с конфликтом хэшей иАлгоритм Блума(Bloom Filter) может решить эту проблему, почему он расширен? Потому что это алгоритм сортировки на основе BitMap.
Оригинальный адрес:woohoo.jet chen.talent/algorithm-no…