Os filtros de bloom são realmente mais rápidos que os hashes, mesmo levando em conta o cache?

Os filtros Bloom ficam realmente ótimos quando você considera que pode determinar se um Int está em um conjunto com 99% de certeza em tempo constante. Mas os hashes também podem, com a única diferença de que, em um hash, na maioria das vezes você acessa a memória apenas uma vez. Com os filtros de bloom, você precisa acessá-los ~ 7 vezes por solicitação em locais completamente distantes , para ter várias falhas de cache por solicitação.

Estou esquecendo de algo?

Está faltando como as duas estruturas de dados lidam com colisões de hash. Os filtros de bloom não armazenam os valores reais; portanto, o espaço necessário é o tamanho constante da matriz designada. Em vez disso, se você usar um hash tradicional, ele tenta armazenar todos os valores que você atribui, aumentando assim com o tempo.

Considere uma função de hash simplificada (apenas para fins de exemplo!) f(x) = x % 2. Agora você entrada os seguintes inteiros: 2, 3, 4, 5, 6, 7.

Hash padrão: os valores fornecidos serão divididos em hash e acabamos com muitas colisões devido a f(2) = f(4) = f(6) = 0e f(3) = f(5) = f(7) = 1. No entanto, o hash armazena todos esses valores e poderá dizer que 8não está armazenado nele. Como isso acontece? Ele monitora colisões e armazena todos os valores com o mesmo valor de hash; então, quando você o consulta, ele também compara sua consulta. Então, vamos consultar o mapa para 8: f(8) = 0, por isso vou olhar para um balde onde já inserido 2, 4, 6e as necessidades para fazer 3 comparações, a fim de dizer-lhe que 8não fazia parte da entrada.

Filtro Bloom: Normalmente, cada valor de entrada é hash em kdiferentes funções de hash. Novamente, para simplificar, vamos apenas assumir que usamos apenas a função hash única f. Precisamos de uma matriz de 2 valores e, quando encontramos a entrada, 2isso significa que, devido ao fato de f(2) = 0definirmos o valor da matriz na posição 0com o valor 1. O mesmo acontece para 4e 6. Da mesma forma, as entradas 3, 5, 7definem a posição da matriz 1como valor 1. Agora, perguntamos se 8fazia parte da entrada: f(8) = 0e a matriz na posição 0é 1, de modo que o filtro bloom afirmará falsamente que 8realmente fazia parte da entrada.

Para ficar um pouco mais realista, vamos considerar que adicionamos uma segunda função de hash g(x) = x % 10. Com isso, o valor de entrada 2leva a dois valores de hash f(2) = 0e g(2) = 2e as duas posições da matriz correspondente irá ser definido para 1. Obviamente, a matriz agora deve ter pelo menos tamanho 10. Porém, quando solicitarmos 8, verificaremos o array na posição 8devida a g(8) = 8, e essa posição ainda será 0. É por isso que funções adicionais de hash diminuem os falsos positivos que você obterá.

Comparação: o filtro bloom usa kfunções hash, o que significa que até kposições aleatórias da matriz estão sendo acessadas. Mas esse número é exato. Em vez disso, o hash garante apenas um tempo de acesso constante amortizado, mas pode ser gerado de acordo com a natureza da função de hash e dos dados de entrada. Por isso, normalmente é mais rápido, exceto nos casos des-gerados.

No entanto, depois de ter uma colisão de hash, o hash padrão precisará verificar a igualdade dos valores armazenados em relação ao valor da consulta. Essa verificação de igualdade pode ser arbitrariamente cara e nunca ocorrerá com um filtro de bloom.

Em termos de espaço, o filtro bloom é constante, pois nunca há necessidade de usar mais memória que a matriz designada. Por outro lado, o hash cresce dinamicamente e pode ficar muito maior devido à necessidade de acompanhar os valores de colisão.

Troca: Agora que você sabe o que é barato e o que não é e em que circunstâncias, deve poder ver a troca. Os filtros Bloom são ótimos se você deseja detectar rapidamente que um valor foi visto anteriormente, mas pode viver com falsos positivos. Por outro lado, você pode escolher o mapa de hash se desejar garantir a correção pelo preço de não ser capaz de julgar exatamente o tempo de execução, mas pode aceitar casos degenerados ocasionalmente que podem ser muito mais lentos que a média.

Da mesma forma, se você estiver em um ambiente de memória limitado, poderá preferir filtros de bloom para garantir a utilização da memória.

Os casos de uso para filtros e hashes de bloom são distintos e, principalmente, disjuntos, portanto, a comparação direta não faz sentido. Além disso, dependerá de detalhes técnicos das implementações, pois há muitas maneiras de lidar com colisões de hash com diferentes trade-offs.

O filtro bloom pode responder se o elemento está em um conjunto para conjuntos enormes , com probabilidade razoável, mas não exatamente, usando uma quantidade modesta de memória. Enorme, tipo, trilhões de elementos. Mas eles nunca são exatos. Você só pode reduzir a quantidade de falsos positivos usando mais memória ou mais funções de hash.

Por outro lado, as tabelas de hash são exatas, mas precisam armazenar o conjunto. Portanto, trilhões de elementos exigiriam terrabytes de memória (e isso é apenas trilhões americanos). Eles também podem armazenar dados extras para cada elemento, que os filtros de bloom não podem.

Portanto, os filtros bloom são usados ​​quando você tem um método lento de obter dados para algum membro (que envolve a consulta de servidor, leituras do disco e outros) de um conjunto grande (que não cabe na memória ou não é prático transferi-lo para o cliente ou tal) e deseja evitar executar a operação lenta para objetos que não estão no conjunto.