Подпишитесь на официальную учетную запись: ИТ-брат, получите вопросы для интервью BAT, 27 комплектов видеоуроков по практическим проектам Java, полный набор видеоуроков по Java от базового до продвинутого, шаблоны резюме, последние маршруты обучения Java и т. д.

Основная идея Bit-map состоит в том, чтобы использовать бит для обозначения Value, соответствующего элементу, а Key — это элемент. Поскольку данные хранятся в битах, можно значительно сэкономить место для хранения. (P.S. сосредоточьтесь наЭкономьте место для хранения)

Предположим, есть такое требование: выяснить, существует ли определенное число m среди 2 миллиардов случайных целых чисел, и предположим, что 32-битная операционная система, 4G памяти

В Java int занимает 4 байта, 1 байт = 8 бит (1 байт = 8 бит)

Если каждое число хранится в int, то есть 2 миллиарда int, то занятое пространство составляет около (2000000000*4/1024/1024/1024)≈7.45 G

Если побитовое хранение отличается, 2 миллиарда чисел составляют 2 миллиарда бит, а занятое пространство составляет около (2000000000/8/1024/1024/1024)≈0.23 G

Суждение сделано, нет необходимости говорить больше

Итак, вопрос в том, как представить число?

Как я только что сказал, каждый бит представляет собой число, 0 означает, что оно не существует, а 1 означает, что оно существует, что в точности соответствует двоичному коду.

Таким образом, мы можем легко представить числа {1, 2, 4, 6}:

рисунок

Наименьшая единица выделения компьютерной памяти — это байты, т. е. 8 бит.Что, если вы хотите представить {12, 13, 15}?

Конечно, он представлен на другом 8-битном:

рисунок

В этом случае он кажется двумерным массивом.

1 int занимает 32 бита, тогда нам нужно только подать заявку на массив int с длиной int tmp[1+N/32] для хранения, где N представляет максимальное значение этих чисел для сохранения, поэтому:

tmp[0]: может представлять 0~31

tmp[1]: может представлять 32~63

tmp[2]: может представлять 64~95

. . .

Таким образом, если задано любое целое число M, то M/32 получает нижний индекс, а M%32 знает, где оно находится в этом нижнем индексе.

Добавить к

Здесь есть проблема, как мы поместим в нее число? Например, если вы хотите вставить в него цифру 5, как вы это сделаете?

Прежде всего, 5/32=0, 5%32=5, значит он должен быть на 5-й позиции tmp[0], затем сдвигаем 1 влево на 5 бит, а затем побитовое ИЛИ

рисунок

Преобразовать его в двоичный

рисунок

Это эквивалентно 86 | 32 = 118.

86 | (1<<5) = 118

b[0] = b[0] | (1<<5)

То есть, чтобы вставить число, сдвиньте 1 влево с цифрой, представляющей число, а затем выполните побитовую операцию ИЛИ с исходным числом.

Упрощенно это 86 + (5/8) | (1

Таким образом, формулу можно резюмировать следующим образом: p + (i/8)|(1

Чисто

Вышесказанное, чтобы добавить, что мне делать, если я хочу очистить его?

Или приведенный выше пример, предположим, мы хотим удалить 6, как это сделать?

рисунок

На картинке просто установите позицию числа на 0

1 сдвигается влево на 6 бит, чтобы достичь бита, представленного числом 6, затем побитовая инверсия и, наконец, побитовое И с исходным числом, так что позиция устанавливается в 0

b[0] = b[0] & (~(1<<6))

b[0] = b[0] & (~(1<<(i%8)))

найти

Ранее мы также говорили, что каждая цифра представляет собой число, 1 означает «да» (или существование), а 0 означает «нет» (или несуществование). Установив значение 1 или 0, чтобы добиться добавления и удаления парня, затем суждение о том, существует ли число или нет, означает, что бит, в котором находится число, равен 0 или 1.

Предположим, мы хотим знать, присутствует ли 3, тогда нам нужно только судить о b[0] & (1

Чем хорош битмап?

Быстрая сортировка, поиск и дедупликация больших объемов данных

быстрая сортировка

Предположим, мы хотим отсортировать 5 элементов (4, 7, 2, 5, 3) в пределах 0-7 (при условии, что эти элементы здесь не повторяются), мы можем использовать метод Bit-map для достижения цели сортировки.

Для представления 8 чисел нам нужно только 8 бит (1 байт).Сначала мы открываем пространство размером 1 байт, устанавливаем все биты в этих пространствах в 0, а затем устанавливаем соответствующую позицию в 1.

Наконец, пройдите через битовую область и выведите номер бита, равный единице (2, 3, 4, 5, 7), чтобы цель сортировки была достигнута, а временная сложность была O (n).

преимущество:

• Высокая эффективность работы, нет необходимости сравнивать и перекладывать;

• Занимайте меньше памяти, например, N=10000000; нужно занимать только память как N/8=1250000Byte=1,25M

недостаток:

• Все данные не могут быть повторены. То есть невозможно отсортировать и найти повторяющиеся данные.

• Преимущество только тогда, когда данные плотнее

быстрая дедупликация

Найдите количество уникальных целых чисел среди 2 миллиардов целых чисел, и памяти недостаточно для хранения этих 2 миллиардов целых чисел.

Прежде всего, согласно «недостаточно памяти для хранения этих 0,5 миллиарда целых чисел», мы можем быстро связать Bit-map. Ключевой вопрос ниже заключается в том, как спроектировать нашу растровую карту для представления состояния этих 2 миллиардов чисел. На самом деле проблема очень проста: есть только три состояния числа: небытие, только одно и повторение. Следовательно, нам нужно всего 2 бита для хранения состояния числа.Предположим, мы устанавливаем число равным 00, если оно не существует, 01, если оно существует один раз, и 11, если оно существует дважды или более. Тогда нам, вероятно, потребуется около 2 ГБ дискового пространства.

Следующая задача состоит в том, чтобы поместить (хранить) эти 2 миллиарда чисел.Если соответствующий бит состояния равен 00, измените его на 01, указывая на то, что он существует один раз, если соответствующий бит состояния равен 01, измените его на 11, указав, что существует уже один, то есть несколько вхождений; если оно равно 11, соответствующий бит состояния остается неизменным, указывая на несколько вхождений.

Наконец, путем подсчета количества битов состояния как 01 получается количество неповторяющихся чисел, а временная сложность равна O(n).

быстрый поиск

Это то, о чем мы говорили ранее, элемент в массиве int имеет размер 4 байта и занимает 32 бита, затем разделите на 32, чтобы узнать индекс элемента, и найдите остаток (%32) от 32, чтобы узнать, где он находится. бит равен 1, значит присутствует.

Резюме и обзор

Растровое изображение в основном используется для быстрого получения статуса ключевых слов. Обычно ключевое слово должно быть непрерывной последовательностью (или ключевое слово представляет собой большую часть непрерывной последовательности). В самом простом случае 1 бит используется для представления статуса ключевого слова. ключевое слово (два состояния), но 2bit (представляющее 4 состояния) и 3bit (представляющее 8 состояний) также могут использоваться по мере необходимости.

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

На 32-битной машине целое число, такое как int a=1, занимает в памяти 32 бита, что необходимо для удобства компьютерных операций. Но для некоторых сценариев приложений это огромная трата, потому что мы можем использовать соответствующие 32-битные биты для хранения десятичных чисел 0-31, а это основная идея Bit-map. Алгоритм Bit-map использует эту идею для сортировки, запросов и дедупликации больших объемов данных.

Дополнение 1

При условии, что число не переполняется, как для положительных, так и для отрицательных чисел сдвиг на один бит влево эквивалентен умножению на 2 в степени 1, сдвиг влево на n бит эквивалентен умножению в степени 2, а сдвиг на один бит вправо эквивалентен умножению на степень 2. Деление на 2 и сдвиг вправо на n бит эквивалентно делению на 2 в степени n.

>> Сдвиг вправо, эквивалентный делению на 2 в энной степени, например: 64>>3 эквивалентно 64÷8=8

^ XOR, эквивалентно нахождению остатка, например: 48^32 эквивалентно 48%32=16

Дополнение 2

Поменять местами значения двух переменных без использования сторонних переменных

`// 方式一`
`a = a + b;`
`b = a - b;`
`a = a - b;`
`// 方式二`
`a = a ^ b;`
`b = a ^ b;`
`a = a ^ b;`

BitSet

BitSet реализует битовый вектор, который может увеличиваться по мере необходимости. Каждый бит имеет логическое значение. Биты BitSet могут быть проиндексированы неотрицательными целыми числами (PS: это означает, что каждый бит может представлять неотрицательное целое число). Бит можно найти, установить и очистить. Содержимое другого BitSet может быть изменено логическими операторами. По умолчанию все биты имеют значение по умолчанию false.

рисунок

рисунок

рисунок

рисунок

рисунок

Как видите, это почти то же самое, что мы думали раньше

Используйте длинный массив для хранения, начальная длина 64, когда установленное значение сначала сдвигается вправо на 6 бит (эквивалентно делению на 64), чтобы вычислить, где находится массив, а затем изменить бит состояния

Неважно, что вы ничего не понимаете, достаточно понять эти два предложения:

`int wordIndex = wordIndex(bitIndex);`
`words[wordIndex] |= (1L << bitIndex);`

Bloom Filters

рисунок

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

За счет эффективной вставки и запроса фильтр Блума представляет собой вероятностную структуру данных: он может только сказать нам, что элемент определенно не входит в набор или может быть в наборе.

Базовая структура данных фильтра Блума представляет собой битовый вектор (который можно понимать как массив).

Он в основном используется в сценариях, не требующих точной фильтрации по крупномасштабным данным, таких как проверка спам-адресов, дедупликация URL-адресов поисковых роботов, решение проблем с проникновением в кэш и т. д.

Если вы хотите определить, находится ли элемент в наборе, общая идея состоит в том, чтобы сохранить все элементы в наборе, а затем определить их путем сравнения. Связный список, дерево, хеш-таблица (хеш-таблица) и другие структуры данных — все это идея, но по мере увеличения количества элементов в коллекции требуемое пространство для хранения становится все больше и больше; в то же время скорость поиска становится все медленнее и медленнее, а время поиска становится все медленнее и медленнее Сложность O (n), O (log n), O (1) соответственно.

Принцип фильтра Блума заключается в том, что когда элемент добавляется в набор, элемент сопоставляется с K точками в битовом массиве (Bit array) через K хеш-функций, и им присваивается значение 1. При извлечении вам нужно только увидеть, все ли эти точки равны 1, чтобы узнать, находится ли элемент в наборе; если какая-либо из этих точек имеет 0, проверенный элемент не должен присутствовать; если все они равны 1, проверенный элемент скорее всего, будет в (другое Таким образом, высказывание «может» является наличием ошибки).

Процесс BloomFilter

1. Во-первых, требуется k хеш-функций, и каждая функция может хэшировать ключ в целое число;

2. При инициализации требуется массив длиной n бит, и каждый бит инициализируется 0;

3. При добавлении ключа в набор используются k хеш-функций для вычисления k хэш-значений, и соответствующая битовая позиция в массиве устанавливается в 1;

4. При оценке того, находится ли ключ в наборе, используйте k хеш-функций для вычисления k хэш-значений и запросите соответствующие биты в массиве.Если все биты равны 1, считается, что он находится в наборе.

рисунок

`<dependency>`
 `<groupId>com.google.guava</groupId>`
 `<artifactId>guava</artifactId>`
 `<version>28.1-jre</version>`
`</dependency>`

Подпишитесь на официальную учетную запись: ИТ-брат, получите вопросы для интервью BAT, 27 комплектов видеоуроков по практическим проектам Java, полный набор видеоуроков по Java от базового до продвинутого, шаблоны резюме, последние маршруты обучения Java и т. д.

безумный принц