Filtering: sets con poca memoria

Sets

• Se comporta igual que un diccionario, pero solo teniendo en cuenta las claves

x = {a, b, d}

y = {a, c}

x & y = {a}

x + y = {a, b, c, d}

x - y = {b, d}

• insert
• contains
• & (intersec)

Filtros de Bloom

• Vector de n bits (bitmap)
• K funciones de hashing (se pueden conseguir infinitas funciones de hashing a partir de una)3

Struct Bloom {

Char* bitmap,

hash_t func,

}

Primitivas

• insert → O(1)
• find → O(1)