Filtros de bloom

• k funciones de hashing
• bitmap de m bits

Set memoria: O(1)

No puedo sacar cosas

m = 8, k = 2

[0, 0, 0, 0, 0, 0, 0, 0]

• Insert (A)
  • h1(A) = 1
  • h2(A) = 6

[0, 1, 0, 0, 0, 0, 1, 0]

• Contains (A)
  • true
• Insert (B)
  • h1(B) = 6
  • h2(B) = 3

[0, 1, 0, 1, 0, 0, 1, 0]

• Insert (C):
  • h1(B) = 5
  • h2(B) = 7

[0, 1, 0, 1, 0, 1, 1, 1]

• Contains(D):

  • h1(D) = 7
  • h2(D) = 3

  True → falso positivo

Proba de falsos positivos p = 0,00001

M óptimo = $(-n * ln(p))/ln(2)^2$

K optimo = $(M opt/n) * ln(2)$

Counting filters

En lugar de un bitmap tiene números enteros (va sumando uno donde hashea), entonces me permite borrar cosas