Введение в алгоритм больших данных

Во-первых, фильтр Buron
1.1 концепция
Фильтр Buron похож наХэш-таблицаСтруктура данных по сути представляет собой двоичный массив. Судя по его поведению, быстро найдите и вставьте его как хэш-таблицу: вы можете вставить фрагмент данных, чтобы определить, существуют ли эти данные уже.

Рисунок 1 Структура веревочного фильтра
1.2 вставка
Теперь нам нужно вставить данные в фильтр Buron, такие какСтрока "baidu". Если это общая хэш-таблица, то что вам нужно сделать, это ввести строку "baidu", вычислить соответствующее хэш-значение с помощью хэш-функции, которая является КЛЮЧЕВЫМ значением хэш-таблицы, с помощью этого ключевого значения "Baidu", сопоставленного с соответствующим местоположением. Очевидно, что при большом объеме данных используйте этот способКонфликт хэшейЯвление: Несколько целевых объектов одинаковы, хэш-значение хэш-функции одинаковое; традиционная хэш-таблица будет использовать некоторые варианты конфликта хэшей, обычно используемые: открытая линия, линейный опрос, вторичный опрос . , , Но независимо от того, какой метод является просто средством устранения, он все еще не решает конфликт хэшей фундаментально. Более того, использование различных средств защиты может привести к значительной экономии времени на доступ к хэш-таблице. Когда конфликт хэшей возникает часто, он воплощает преимущество хэш-таблицы в производительности. Таким образом, большой объем данных, очевидно, не подходит для использования традиционной хэш-таблицы, поэтому мы вводим фильтр Buron. Далее давайте посмотрим, как работает фильтр Buron:
Сначала вам нужно использовать несколько хэш-функций для сопоставления строки "baidu", вы получаете несколько хэш-значений и устанавливаете значение массива соответствующего хэш-значения равным 1, процесс показан ниже:

Рисунок 2 Вставка фильтра веревки
1.3 поиск
Найдите целевое поле для фильтра Burulum, напримерСтрока "tencent"Аналогично, множественные хэш-функции будут сопоставлены множеству хэш-значений, а затем будет проверен соответствующий индекс в фильтре Buron. Если у всех элементов позиции нижнего индекса всех хэш-значений равно 1, считается, что целевое поле существует. В фильтре Buron; он перевернут, нет существования. Как показано ниже:

Рисунок 3 Нахождение веревочного фильтра