O código mais rápido que existe é aquele que não precisa ser executado.

Considere, por exemplo, que esteja implementando uma funcionalidade para recuperação de senhas. Nesse caso, é um completo desperdício de recursos fazer uma requisição ao servidor apenas para constatar que o e-mail informado não está cadastrado. Entretanto, como fazer para determinar se um e-mail “existe na base”, sem consultá-la?

Em outro exemplo, considere que esteja implementando a funcionalidade para cadastro de um novo usuário que precisará ter um “nome-de-usuário” único. Seria um total desperdício de recursos fazer requests ao servidor para constatar que o “nome-de-usuário” informado já está cadastrado, associado a outro usuário. Entretanto, como saber se um “nome-de-usuário” já foi utilizado sem consultar o servidor?

Infelizmente, é comum que requisições “inúteis”, como as indicadas nos parágrafos anteriores, ocorram, gerando desperdício de recursos e, muitas vezes, prejuízos de performance. O triste, é que elas poderiam ser evitadas com uso inteligente de estruturas de dados como o Bloom Filter.

Utilizando Bloom Filter, com apenas poucos bits é possível gerar filtros eficientes para milhares de elementos. Um milhão de strings, por exemplo, poderiam ser controladas com apenas 1Mb e 1% de taxa de erro (consultas que geram falsos positivos).

Ou seja, é possível enviar para o “lado cliente” de um software informação suficiente para reduzir dramaticamente requests inócuos e, por consequência, trafego na rede, acessos a “disco” e alocações desnecessárias em memória. Afinal, antes de fazer uma requisição ao servidor para verificar a “presença” de um dado em um conjunto, bastaria o “lado cliente” consultar, antes, ao filtro, podendo prover feedback muito mais rápido sem onerar o backend.

O segredo para a eficiência dessa estrutura de dados é a utilização de hashes de qualidade que são utilizados para ligar ou desligar bits em um mapa. Sempre que um dado é “incluído” no filtro, os bits correspondentes do hash são ligados.

Para verificar se um dado está no filtro, basta verificar se todos os bits correspondentes ao hash estão ligados. Caso estejam, o dado poderá estar no conjunto. Caso contrário, o dado certamente não estará.

A implementação que compartilhamos aqui é baseada em uma versão antiga compartilhada pela Microsoft no Codeplex.

public delegate int HashFunction<T>(T input);

public class BloomFilter<T>
{

    private readonly HashFunction<T> getHashPrimary;
    private readonly HashFunction<T> getHashSecondary;
    private readonly int hashFunctionCount;
    private readonly BitArray hashBits;

    public BloomFilter(
        int capacity, 
        float errorRate,
        HashFunction<T> primaryHashFunction,
        HashFunction<T> secondaryHashFunction
        )
    {
        var m = BestM(capacity, errorRate);
        var k = BestK(capacity, errorRate);
        Debug.WriteLine($"New BloomFilter (k = {k}; m = {m})");

        hashBits = new BitArray(m);
        hashFunctionCount = k;
        getHashPrimary = primaryHashFunction ?? throw new ArgumentNullException(nameof(secondaryHashFunction));
        getHashSecondary = secondaryHashFunction ?? throw new ArgumentNullException(nameof(secondaryHashFunction));
    }

    public void Add(T item)
    {
        // start flipping bits for each hash of item
        int primaryHash = item.GetHashCode();
        int secondaryHash = getHashSecondary(item);
        for (int i = 0; i < hashFunctionCount; i++)
        {
            int hash = ComputeHashUsingDillingerManoliosMethod(primaryHash, secondaryHash, i);
            hashBits[hash] = true;
        }
    }

    public bool MaybeContains(T item)
    {
        int primaryHash = getHashPrimary(item);
        int secondaryHash = getHashSecondary(item);
        for (int i = 0; i < hashFunctionCount; i++)
        {
            int hash = ComputeHashUsingDillingerManoliosMethod(primaryHash, secondaryHash, i);
            if (hashBits[hash] == false)
                return false;
        }
        return true;
    }

    private int ComputeHashUsingDillingerManoliosMethod(int primaryHash, int secondaryHash, int i)
    {
        var resultingHash = (primaryHash + i * secondaryHash) % hashBits.Count;
        return Math.Abs(resultingHash);
    }

    private static int BestM(int capacity, float errorRate)
      => (int)Math.Ceiling(capacity * Math.Log(errorRate, 1.0 / Math.Pow(2, Math.Log(2.0))));

    private static int BestK(int capacity, float errorRate)
      => (int)Math.Round(Math.Log(2.0) * BestM(capacity, errorRate) / capacity);
}

O código, aqui escrito em C#, é fácil de transcrever para qualquer linguagem, incluindo Javascript.

A utilidade da Bloom filter também está associada a capacidade de gerar boas chaves hash para os objetos que se quer controlar. Abaixo, implementações para string e int32.

public static class HashFunctions
{
    public static HashFunction<T> FromType<T>() => 
        (obj) => obj.GetHashCode();

    public static int ForStrings(string input)
    {
        var hash = 0;

        for (var i = 0; i < input.Length; i++)
        {
            hash += input[i];
            hash += (hash << 10);
            hash ^= (hash >> 6);
        }
        hash += (hash << 3);
        hash ^= (hash >> 11);
        hash += (hash << 15);
        return hash;
    }

    public static int ForInt32(int input)
    {
        uint x = (uint)input;

        unchecked
        {
            x = ~x + (x << 15); 
            x = x ^ (x >> 12);
            x = x + (x << 2);
            x = x ^ (x >> 4);
            x = x * 2057; 
            x = x ^ (x >> 16);
            return (int)x;
        }
    }
}

[tweet]Embora existam “acrobacias técnicas” que geram grandes ganhos de desempenho, a forma mais consistente e efetiva de escrever software com performance excelente é fazendo bom uso de algoritmos e estruturas de dados.[/tweet]