Filtro de Bloom

Un filtro de Bloom es una estructura de datos probabilística, concebida por Burton Howard Bloom en 1970, que es usada para verificar si un elemento es miembro de un conjunto.

Los falsos positivos son posibles pero los falsos negativos no.

Los filtros de Bloom se suelen usar para:

Un ejemplo de filtro de Bloom, representando el conjunto { x , y , z }. Las flechas coloreadas muestran las posiciones en el vector de bits de los resultados de aplicar las funciones hash a cada uno de los elementos. El elemento w no está en el conjunto { x , y , z }, porque tiene uno o más de los valores hash a 0. Para este ejemplo m = 18 y k = 3.