1. Проблемный сценарий

Если интервьюер спросит вас, веб-сайт имеет 10 миллиардов URL-адресов в черном списке, и каждый URL-адрес в среднем составляет 64 байта. Как сохранить этот черный список? Если вы введете URL-адрес в это время, как определить, находится ли URL-адрес в этом черном списке?

Что касается первого вопроса, если черный список рассматривается как набор и хранится в хэш-карте, он кажется слишком большим и требует 640G, что явно ненаучно.

так что мне теперь делать? Хорошо, теперь пришло время представить главного героя сегодняшнего дня — фильтр Блума может решить такую ​​проблему.

Прежде всего, что такое фильтр Блума? Википедия объясняет это так:

Фильтр Блума Filter) был предложен Блумом в 1970 году. На самом деле это длинный двоичный вектор и ряд функций случайного отображения. Фильтры Блума можно использовать для определения того, находится ли элемент в коллекции. Его преимущество заключается в том, что эффективность использования пространства и время запроса намного больше, чем у общего алгоритма, а недостаток заключается в том, что существует определенная частота неправильного распознавания и сложность удаления.

Хорошо читать официальное заявление.Если вы не поняли его, ничего страшного.Это не сложно.

2. Подробное введение

Фильтр Блума на самом деле представляет собой длинный двоичный вектор и серию функций случайного отображения.

«Длинный двоичный вектор»: это очень длинный массив, какой это тип массива? Массив битового типа также называется битами (1 байт = 8 бит, 1 КБ = 1024 байт).

«Серия функций случайного отображения»: существует несколько хеш-функций. Так что же такое хэш-функция? В JDK есть метод вычисления хеш-значения, то есть хэш-функция.

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

Разве это не решит нашу первоначальную проблему? Итак, как это решается?

3. Процесс разрешения

Далее я объясню общий процесс.Детали могут быть непонятны сначала.Важно понять процесс.Я добавлю детали позже.

Предположим, что длина массива битового типа равна m, значение каждого элемента равно 0 и имеется k хеш-функций.

Во-первых, когда URL-адрес вводится, URL-адрес будет обработан k хеш-функциями для получения нескольких хеш-значений (v1,v2,...,vk). Затем получите эти хэш-значения, соответствующие позициям индексов массива, и, наконец, установите элементы этих индексов в 1.

Итак, как определить, что URL-адрес находится в черном списке? Введите URL-адрес, и после вышеуказанной обработки он получит позиции индекса нескольких массивов. Если значение элемента этих индексов уже равно 1, это означает, что он находится в черном списке, в противном случае - нет.

Общий процесс выглядит следующим образом. Вот вопросы, которые могут у вас возникнуть:

1. Как построить массив битового типа

2. После получения хеш-значений v1,v2,...,vk, как получить позицию нижнего индекса массива и установить ее в 1?

Позвольте мне говорить о двух вопросах вместе, в Java нет такого типа, как бит, как его построить? - Несложно, мы можем использовать int, int 32 бита.

//创建了一个 100 * 32bit 的数组
int[] arr = new int[100]; 
// 代表 bit 数组 0-31 位的元素
arr[0];

Следовательно, выше будет сказано «соответственно разделить эти хеш-значения на длину m массива и по модулю m, чтобы получить эти хеш-значения, соответствующие позициям индексов массива».

В частности, мы можем взять данные хеш-значения в качестве примера, предполагая, что длина массива int равна 100.

void Set(int data) {
       // ByteNO 是表示在 table 数组中那个元素
       int ByteNo = data / 32;
       // bitNo 是表示在 32 位 bit 中哪个 bit 位。
       int BitNo = data % 32;
       // 置 1
       _table[ByteNo] |= (1 << BitNo); 
   }

4. Используйте эффект

В начале мы упомянули, что если для размещения 10 миллиардов URL-адресов в HashMap требуется 640 ГБ, сколько места потребуется после использования фильтра Блума? Ответ примерно равен 23 ГБ. Напротив, допустим ли такой размер пространства?

5. Недостатки

Фильтр Блума обладает тем свойством, что он скорее убьет сотню по ошибке, чем отпустит одного. Говоря об URL-адресе, который принадлежит к черному списку, нужно уметь правильно судить о том, что он находится в черном списке, но URL-адрес, который не принадлежит к черному списку, также может считаться находящимся в черном списке, и есть определенная частота ошибок.

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

Ссылаться на:blog.CSDN.net/Вэньцян 120…

PS: эта статья изначально была опубликована в общедоступной учетной записи WeChat «Не только Java», и фоновый ответ «Java» даст вам 13 классических электронных книг Java. Официальная учетная запись ориентирована на обмен галантерейными товарами Java, чтение заметок и мышление о росте.