Статьи

Google Guava BloomFilter

Февраль 20, 2019

Когда проект Guava выпустил версию 11.0, одним из новых дополнений стал класс BloomFilter. BloomFilter — это уникальная структура данных, используемая для указания того, содержится ли элемент в наборе. Что делает BloomFilter интересным, так это то, что он будет указывать, если элемент абсолютно не содержится или может содержаться в наборе.

Это свойство отсутствия ложного отрицания делает BloomFilter отличным кандидатом для использования в качестве защитного условия, помогающего предотвратить выполнение ненужных и дорогостоящих операций. В то время как BloomFilters в последнее время получили хороший отклик, использование одного означало переход на другой или поиск в Google кода. Проблема с прокруткой собственного BloomFilter заключается в получении правильной хеш-функции для создания фильтра.

эффективный. Учитывая, что Guava использует Murmur Hash для его реализации, теперь у нас есть полезный эффективный BloomFilter, находящийся вдали от библиотеки.

Ускоренный курс BloomFilter

BloomFilters по существу являются битовыми векторами. На высоком уровне BloomFilters работают следующим образом:

  1. Добавьте элемент в фильтр.
  2. Сделайте хэш-код несколько раз, затем установите биты равными 1, где индекс соответствует результатам хэша.

При проверке наличия элемента в наборе вы выполняете ту же процедуру хеширования и проверяете, установлены ли биты на 1 или 0. Этот процесс позволяет BloomFilter гарантировать, что элемент не существует. Если биты не установлены, элемент просто не может быть в наборе. Однако положительный ответ означает, что элемент находится в наборе или произошло столкновение хэширования. Более подробное описание BloomFilter можно найти здесь, а хорошее руководство по BloomFilters здесь . Согласно википедии , Google использует BloomFilters в BigTable, чтобы избежать поиска на диске несуществующих элементов. Еще одно интересное использование — использование BloomFilter для оптимизации SQL-запросов .

Использование Guava BloomFilter

Guava BloomFilter создается путем вызова статического метода create в классе BloomFilter,
передача в объекте Funnel и int, представляющий ожидаемое количество вставок. Воронка, также новая в Guava 11, — это объект, который может отправлять данные в Sink . Следующий пример является реализацией по умолчанию и имеет процент ложных срабатываний 3%. Guava предоставляет класс Funnels, содержащий два статических метода, обеспечивающих реализации интерфейса Funnel для вставки CharSequence или байтового массива в фильтр.

1
2
3
4
5
6
7
8
9
//Creating the BloomFilter
BloomFilter bloomFilter = BloomFilter.create(Funnels.byteArrayFunnel(), 1000);
 
//Putting elements into the filter
//A BigInteger representing a key of some sort
bloomFilter.put(bigInteger.toByteArray());
 
//Testing for element in set
boolean mayBeContained = bloomFilter.mayContain(bitIntegerII.toByteArray());

ОБНОВЛЕНИЕ: на основе комментария от Луи Вассермана, вот как создать BloomFilter для BigIntegers с пользовательской реализацией Funnel:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
//Create the custom filter
class BigIntegerFunnel implements Funnel<BigInteger> {
        @Override
        public void funnel(BigInteger from, Sink into) {
            into.putBytes(from.toByteArray());
        }
    }
 
//Creating the BloomFilter
BloomFilter bloomFilter = BloomFilter.create(new BigIntegerFunnel(), 1000);
 
//Putting elements into the filter
//A BigInteger representing a key of some sort
bloomFilter.put(bigInteger);
 
//Testing for element in set
boolean mayBeContained = bloomFilter.mayContain(bitIntegerII);

Соображения

Очень важно правильно оценить количество ожидаемых вставок. Когда число вставок в фильтр приближается или превышает ожидаемое число, BloomFilter начинает заполняться и в результате генерирует больше ложных срабатываний до такой степени, что становится бесполезным. Существует другая версия метода BloomFilter.create, принимающая дополнительный параметр, double, представляющий желаемый уровень вероятности ложного попадания (должен быть больше 0 и меньше единицы). Уровень вероятности ложного попадания влияет на количество хэшей для хранения или поиска элементов. Чем ниже требуемый процент, тем больше будет выполнено хэшей.

Вывод

BloomFilter — это полезный элемент, который разработчик может иметь в своем наборе инструментов. Теперь проект Guava упрощает использование BloomFilter, когда в этом возникает необходимость. Я надеюсь, вам понравился этот пост. Полезные комментарии и предложения приветствуются.

использованная литература

Ссылка: Google Guava BloomFIlter от нашего партнера по JCG Билла Беджека в блоге « Случайные мысли о кодировании» .

37
Share: