Использование Guava 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 или байтового массива в фильтр.

//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 начинает заполняться и в результате генерирует больше ложных срабатываний до такой степени, что становится бесполезным. Существует другая версия метода BloomFilter.create, принимающая дополнительный параметр, double, представляющий желаемый уровень вероятности ложного попадания (должен быть больше 0 и меньше единицы). Уровень вероятности ложного попадания влияет на количество хэшей для хранения или поиска элементов. Чем ниже требуемый процент, тем больше будет выполнено хэшей.

Вывод

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

Рекомендации

• Модульное тестовое демо Guava BloomFilter .
• Класс BloomFilter
• Все, что вы хотите знать о BloomFilters .
• Учебник BloomFilter .
• BloomFilter в Википедии .