# El filtro de Bloom - Sitio: Ikusmira — enciclopedia en castellano de ciencias sociales y humanidades - URL canónica: https://ikusmira.org/p/el-filtro-de-bloom/ - Categoría: Informática - Publicado: 2026-09-04 - Autoría: Eneko Sarasola (redacción de Ikusmira) - Política editorial (autoría, revisión, correcciones, financiación): https://ikusmira.org/politica-editorial/ El **filtro de Bloom** es una estructura de datos que responde a la pregunta «¿he visto ya este elemento?» usando una cantidad de memoria ridícula, a cambio de equivocarse a veces en una sola dirección. Nunca dice que no ha visto algo que sí vio. Puede decir que ha visto algo que no vio, con una probabilidad pequeña y calculable. Esa asimetría lo hace perfecto como portero: antes de hacer una operación cara —consultar un disco, preguntar a otro servidor, buscar en una lista de millones de direcciones maliciosas—, se pregunta al filtro, y si dice «no» se ahorra la operación con toda seguridad; si dice «quizá», se hace la operación y se comprueba. Burton Bloom lo propuso en 1970 en cuatro páginas, y hoy está en los navegadores, en las bases de datos, en los routers y en las criptomonedas. La figura de esta página es un filtro de Bloom entero, bit a bit. La rejilla de la izquierda es un vector de *m* bits, todos a cero al principio. Insertar una palabra es pasarla por *k* funciones hash distintas, que dan *k* posiciones del vector, y poner a uno esos *k* bits. Consultar una palabra es calcular sus mismas *k* posiciones y mirar: si alguno de los bits está a cero, la palabra no se ha insertado, con certeza absoluta, porque de haberse insertado ese bit estaría a uno. Si todos están a uno, la palabra probablemente se insertó, pero puede que no: puede que otros elementos, entre todos, hayan encendido por casualidad esos *k* bits. Eso es un *falso positivo*, y el botón que consulta una palabra que no está permite ir a la caza de uno. Lo primero que se ve es cuánto cabe. El vector de 256 bits de la figura ocupa 32 bytes, lo que ocuparían cinco o seis palabras cortas escritas tal cual, y sin embargo con tres funciones hash puede guardar la huella de cuarenta palabras y responder mal a menos del 10 % de las consultas sobre palabras ausentes. Con 1.024 bits y cien palabras, el error baja del 2 %. El filtro no guarda las palabras: no se pueden recuperar de él ni recorrer, solo preguntar por una. Esa es la renuncia que compra el ahorro, y el motivo de que el filtro complemente a otras estructuras en lugar de sustituirlas. Lo segundo es la fórmula, que la gráfica de la derecha dibuja junto a la medida real. Tras insertar *n* elementos con *k* funciones en *m* bits, la fracción de bits que sigue a cero es aproximadamente e^(−*kn*/*m*), y la probabilidad de que una palabra ausente encuentre sus *k* bits encendidos es esa fracción de bits encendidos elevada a *k*. La medida de la figura, hecha con quinientas palabras que no están, sigue la curva teórica con el vaivén que corresponde a una muestra de ese tamaño. La fórmula dice también cuántas funciones conviene usar: con pocas, cada palabra deja poca huella y una ausente la imita fácilmente; con muchas, el vector se llena de unos y todo parece estar. El óptimo es *k* = (*m*/*n*)·ln 2, unas 0,7 funciones por cada bit disponible por elemento, y con él la tasa de error es 0,6185 elevado a *m*/*n*: con diez bits por elemento, menos del 1 %. La figura calcula el óptimo para el número de palabras insertadas y avisa cuando el *k* elegido se aleja. Lo tercero es de dónde salen *k* funciones hash. Calcular ocho funciones distintas por cada consulta sería caro, y en la práctica no hace falta. Adam Kirsch y Michael Mitzenmacher demostraron en 2008 que basta con dos funciones, *h*₁ y *h*₂, y usar *h*₁ + *i*·*h*₂ para *i* de 0 a *k* − 1, sin que la tasa de falsos positivos empeore de forma apreciable. Es lo que hace la figura, con dos variantes de la función FNV, y es lo que hacen la mayoría de las implementaciones. El filtro tardó treinta años en hacerse famoso, y lo que lo lanzó fue la red. Li Fan y sus colegas propusieron en 2000 que las cachés web de una organización se intercambiaran, en lugar de la lista completa de las páginas que cada una tenía, un filtro de Bloom de esa lista: una fracción de la memoria, y a cambio alguna consulta ocasional a una caché vecina que resultaba no tener la página. Andrei Broder y Michael Mitzenmacher recopilaron en 2004 decenas de usos en redes y acuñaron el *principio del filtro de Bloom*: siempre que una lista o un conjunto se usen y el espacio importe, considérese un filtro de Bloom si los falsos positivos se pueden tolerar. Bigtable, la base de datos de Google descrita en 2008, guarda un filtro por cada fichero en disco para no leer ficheros que no contienen la clave buscada, y la idea se copió en casi todos los almacenes de datos posteriores. Chrome usó durante años un filtro de Bloom con las direcciones peligrosas conocidas, para consultar al servidor solo cuando el filtro decía «quizá». Bitcoin lo usa para que un cliente ligero pida a la red solo las transacciones que le pueden interesar sin revelar cuáles son. Hay una limitación que la figura hace visible: no se puede borrar. Poner a cero los bits de una palabra apagaría también los de otras que los compartan, y el filtro empezaría a dar falsos negativos, lo único que prometía no dar. Las variantes con contadores en lugar de bits lo permiten a cambio de más memoria. Pero la versión original, la de 1970, sigue siendo la que se usa cuando lo que hay que recordar solo crece, y su lección va más allá del caso: hay preguntas cuya respuesta exacta cuesta mucho y cuya respuesta casi exacta, con el error en la dirección correcta, cuesta casi nada. ## Fuentes - Burton H. Bloom — *Space/Time Trade-offs in Hash Coding with Allowable Errors*, Communications of the ACM 13(7) (1970) - Li Fan, Pei Cao, Jussara Almeida y Andrei Z. Broder — *Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol*, IEEE/ACM Transactions on Networking 8(3) (2000) - Andrei Broder y Michael Mitzenmacher — *Network Applications of Bloom Filters: A Survey*, Internet Mathematics 1(4) (2004) - Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes y Robert E. Gruber — *Bigtable: A Distributed Storage System for Structured Data*, ACM Transactions on Computer Systems 26(2) (2008) - Adam Kirsch y Michael Mitzenmacher — *Less Hashing, Same Performance: Building a Better Bloom Filter*, Random Structures & Algorithms 33(2) (2008) --- Cómo citar: Sarasola, Josemari (2026). «El filtro de Bloom». Ikusmira. https://ikusmira.org/p/el-filtro-de-bloom/ Índice del sitio para modelos: https://ikusmira.org/llms.txt