fastbloom

El filtro Bloom más rápido en Rust. Sin compromisos en la precisión. Soporte completo para concurrencia y compatible con cualquier función hash.

Visión general

fastbloom es un filtro Bloom rápido, flexible y preciso implementado en Rust. El hasher predeterminado de fastbloom es SipHash-1-3 usando claves aleatorias, pero puede ser inicializado o configurado para usar cualquier función hash. fastbloom es entre 2 y 20 veces más rápido y mucho más preciso que las implementaciones existentes de filtros Bloom. AtomicBloomFilter de fastbloom es un filtro Bloom concurrente que evita la contención de bloqueos.

Uso

Debido a un algoritmo diferente (¡mejorado!) en la versión 0.17.x, los filtros Bloom tienen serialización/deserialización incompatible con versiones anteriores.

# Cargo.toml
[dependencies]
fastbloom = "0.17.0"

Uso básico:

use fastbloom::BloomFilter;let mut filter = BloomFilter::with_num_bits(1024).expected_items(2);
filter.insert("42");
filter.insert("🦀");

Instanciar con una tasa objetivo de falsos positivos:

use fastbloom::BloomFilter;let filter = BloomFilter::with_false_pos(0.001).items(["42", "🦀"].iter());
assert!(filter.contains("42"));
assert!(filter.contains("🦀"));

Usa cualquier hasher:

use fastbloom::BloomFilter;
use foldhash::fast::RandomState;let filter = BloomFilter::with_num_bits(1024)
    .hasher(RandomState::default())
    .items(["42", "🦀"].iter());

Soporte completo para concurrencia. AtomicBloomFilter es un reemplazo directo para RwLock porque todos los métodos toman &self:

use fastbloom::AtomicBloomFilter;let filter = AtomicBloomFilter::with_num_bits(1024).expected_items(2);
filter.insert("42");
filter.insert("🦀");

Antecedentes

Los filtros de Bloom son estructuras de datos de conjuntos de membresía aproximada y espacio eficiente, soportadas por un arreglo subyacente de bits para rastrear la pertenencia de elementos. Para insertar/verificar la pertenencia, se establecen/verifican varios bits en posiciones basadas en el hash del elemento. Son posibles falsos positivos en una verificación de membresía, pero no falsos negativos. Una vez construido, ni el uso de memoria subyacente del filtro de Bloom ni el número de bits por elemento cambian. Ver más.

hash(4) ──────┬─────┬───────────────┐
              ↓     ↓               ↓
0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0
  ↑           ↑           ↑
  └───────────┴───────────┴──── hash(3) (not in the set)

Implementación

fastbloom es extremadamente rápido porque deriva eficientemente muchos bits de índice a partir de solo un hash real por elemento y aprovecha otros hallazgos de investigación sobre filtros Bloom. fastbloom emplea "composición de hashes" sobre dos mitades de 32 bits de un hash original de 64 bits. Cada hash subsecuente se deriva combinando el valor del hash original con una constante diferente usando aritmética modular y operaciones a nivel de bits. Esto resulta en un conjunto de funciones hash que son efectivamente independientes y uniformemente distribuidas, aunque se derivan de la misma función hash original. Calcular la composición de dos hashes originales es más rápido que volver a calcular el hash con una semilla diferente. Esta técnica se explica en profundidad en este artículo.

Velocidad

Procesador AMD Ryzen 9 5900X de 12 núcleos (3.70 GHz)
Sistema operativo de 64 bits, procesador basado en x64

Hashers usados:

- xxhash: sbbf

- Sip1-3: bloom, bloomfilter, probabilistic-collections

- foldhash: fastbloom

Fuente del benchmark

Precisión

fastbloom no compromete la precisión. A continuación se muestra una comparación de las tasas de falsos positivos con otros crates de filtros Bloom:

Fuente del benchmark

Características Disponibles

rand - Habilitado por defecto, esto hace que DefaultHasher obtenga su estado aleatorio usando thread_rng() en lugar de fuentes de hardware. Obtener entropía desde una fuente en espacio de usuario es considerablemente más rápido, pero requiere dependencias adicionales para lograrlo. Deshabilitar esta característica usando default-features = false hace que DefaultHasher obtenga su entropía usando foldhash, lo que tendrá una huella de código mucho más simple a costa de la velocidad.
serde - BloomFilters implementan Serialize y Deserialize cuando es posible.
loom - AtomicBloomFilters usan atómicos de loom, haciéndolo compatible con pruebas loom.

Referencias

Licencia

Licenciado bajo cualquiera de

Licencia Apache, Versión 2.0

(LICENSE-APACHE o http://www.apache.org/licenses/LICENSE-2.0)

Licencia MIT

(LICENSE-MIT o http://opensource.org/licenses/MIT)

a su elección.

Contribución

A menos que usted indique explícitamente lo contrario, cualquier contribución intencionadamente enviada para su inclusión en el trabajo por usted, según se define en la licencia Apache-2.0, será licenciada de forma dual como se indica arriba, sin términos o condiciones adicionales.

--- Tranlated By Open Ai Tx | Last indexed: 2026-05-15 ---