Filtro de Bloom

Un filtro de Bloom almacena m bits, inicialmente a cero. Insertar una cadena pone a uno sus k posiciones hash. Una consulta comprueba las mismas posiciones: cualquier bit a cero significa definitivamente ausente; todos a uno significa solo posiblemente presente. Con parámetros fijos y sin eliminación, las cadenas insertadas no pueden convertirse en falsos negativos. La referencia didáctica aparte almacena las cadenas exactas solo para identificar la pertenencia verdadera y los falsos positivos; su almacenamiento extra no está incluido en los m bits del filtro.

Elige un entero m de 8 a 1024 y k de 1 a 12, luego crea el filtro. Editar cualquiera de los dos parámetros descarta el filtro activo hasta que se vuelva a crear. Restablecer borra el filtro y conserva los campos. Las cadenas tienen 1–256 unidades de código UTF-16; se conservan como máximo 1024 cadenas distintas. La comparación es exacta y distingue mayúsculas: no hay recorte ni normalización Unicode. Los espacios cuentan, muchos emojis ocupan dos unidades de código, y los acentos compuestos y descompuestos son cadenas distintas. La última cadena se muestra con comillas y escapes JSON para hacer identificables los espacios y caracteres de control. Una inserción duplicada deja el arreglo de bits, el recuento de entradas distintas y los contadores de consultas sin cambios.

La implementación conserva su variante de hash de 32 bits de tipo FNV-1a sobre las unidades de código UTF-16 de JavaScript, en lugar de los octetos del FNV-1a estándar. Cada unidad se combina con XOR en el hash y se multiplica por 16777619 módulo 2³². Los dos valores iniciales son 2166136261 y 0xdeadbeef; el segundo resultado se hace impar. Las posiciones reales son (h₁ + i h₂) mod m para i = 0…k−1. La aritmética se reduce módulo m sin un desbordamiento intermedio de 32 bits. Se permiten posiciones repetidas: un paso impar no garantiza un ciclo completo para un m arbitrario. La tabla de operación muestra cada posición en secuencia, incluidas las repeticiones. Una inserción en un bit ya a uno simplemente lo deja a uno. Los dos hashes base están disponibles en Detalles. Esta es una implementación didáctica determinista, no criptográfica, no una afirmación de que los hashes sean independientes y uniformes.

La tasa de falsos positivos observada es los falsos positivos divididos por las consultas de cadenas realmente ausentes del conjunto de referencia. Las consultas de cadenas insertadas no entran en ningún contador. Una nueva inserción distinta reinicia los contadores porque el conjunto de referencia y posiblemente los bits han cambiado. Sin consultas negativas, la tasa es indefinida. Las consultas repetidas cuentan como peticiones repetidas; las consultas elegidas a mano no son una muestra aleatoria independiente y la tasa mostrada no es una garantía para cadenas futuras.

Detalles muestra la aproximación clásica f ≈ (1 − exp(−kn/m))ᵏ para n entradas distintas y hashes ideales independientes uniformes. No es la tasa exacta de este filtro determinista finito. El ejemplo a…h inserta esas ocho cadenas ASCII en el filtro actual. Con m = 8 y k = 1 llenan todos los bits, así que cualquier cadena nueva es un falso positivo. Para un ejemplo más pequeño inserta solo a, luego consulta i, a y b: i es falso positivo, a verdaderamente presente y b ausente; la tasa observada es 1/2, porque solo dos consultas son negativas.

Los parámetros y borradores sin procesar, entradas, contadores de consultas, última operación y detalles abiertos se guardan localmente hasta 100000 caracteres serializados. Por encima se conserva la copia anterior y aparece un aviso: exporta toda la sesión antes de recargar o salir de la página. La navegación interna conserva la sesión actual. Una importación inválida conserva el filtro actual. Los estados antiguos siguen siendo legibles. Restablecer borra el filtro y conserva los borradores. No hay borrado, variante con contadores, protección criptográfica ni pruebas de rendimiento.

Fuentes: Bloom (1970), Method 2 and Eq. 1, original-paper mirror; Kirsch and Mitzenmacher (2008), §§2 and 5.2; RFC 9923, FNV basics.

La última consulta o inserción aparece primero. Los bits marcados muestran las posiciones utilizadas. Abre Posiciones hash para los valores antes/después en orden, y Modelo y hashes para la estimación ideal y los hashes base. La tasa observada solo cuenta consultas de cadenas ausentes; las consultas manuales no son una muestra aleatoria.

Los bits conservan un tamaño de celda fijo y legible. La cuadrícula se adapta al ancho disponible, hasta 64 columnas; los filtros pequeños conservan su ancho natural. Las cuadrículas altas se desplazan dentro de su región. Los bordes naranjas marcan las posiciones de la última operación.

Solo se conservan los valores introducidos en este navegador. No se guardan los resultados calculados ni los historiales.