Qué funciones hash para su uso en una floración filtrar

Question

Tengo la siguiente pregunta sobre la elección de funciones hash para filtros Bloom:

• que funciona para usar?

En casi todos los documento/papel se puede leer que las funciones hash utilizados en un Bloom filtran debe ser independiente y uniformemente distribuida.

Sé lo que se entiende por esto (distribución independiente y uniforme), pero tengo problemas para encontrar una argumentación o una discusión, cuyas funciones hash cumplen esos requisitos y, por lo tanto, son adecuadas. En una gran cantidad de publicaciones que he leído sobre sugerencias para el uso de FNV o Murmur hash función, pero no por qué (o al menos sin una prueba) son adecuados.

¡Gracias de antemano!

Answer 1

Hash Functions debe proporcionarle una prueba gráfica de por qué FNV sería una mala elección, y por qué Murmur2 o uno de Bob Jenkins' Hashes sería una buena opción.

Answer 2

Me hice la misma pregunta al construir una biblioteca de filtros de Java Bloom. Ver the Github readme para un tratamiento detallado de mi análisis de funciones hash para filtros Bloom.

Miré el problema desde dos perspectivas:

• ¿Qué tan rápido es el cálculo?
• ¿Qué tan uniforme es la distribución de salida?

La velocidad se puede medir fácilmente mediante puntos de referencia en la entrada aleatoria. La uniformidad es un poco más difícil y requiere algunas estadísticas. Utilizando las pruebas de bondad de ajuste de Chi-Cuadrado, medí qué tan similar es la distribución de los valores de hash a una distribución uniforme.

El resultado es:

• Uso Murmur3 para el mejor compromiso entre la velocidad y la uniformidad. Do no use Murmur2 ya que no es uniforme para entradas que cambian en pequeños incrementos.
• Utilice una función de cifrado hash como SHA-256 para la mejor uniformidad.
• Aplicar el Kirsch-Mitzenmacher-Optimization para calcular solo 2 en lugar de k funciones hash (hash_i = hash1 + i x hash2).

Si su implementación usa Java, recomendaría utilizar nuestra biblioteca hash de filtros Bloom. Está bien documentado y probado a fondo. Para los detalles, incluyendo los resultados de referencia para diferentes funciones hash y su unformidad de acuerdo con la prueba de Chi-Cuadrado, vea el Github readme of the repo.

Answer 3

Creo que una opción razonable sería múltiples hashes de CRC.Supongo que, si quiere múltiples valores hash n-bit, entonces para los polinomios con coeficientes de campo Booleanos, hay múltiples polinomios primos de grado n + 1. Pero no sé de un proceso para encontrar estos polinomios.

Otra posibilidad sería utilizar hashes de módulo múltiple. El tamaño de la matriz de bits de Bloom Filter debería ser el valor máximo del módulo. Pero creo que, para que funcione bien, los valores del módulo tendrían que ser producto de números primos superiores a 10, y relativamente primos entre sí. Y el rango del valor del módulo mínimo al máximo debería ser lo más pequeño posible. No sé de una manera de encontrar esos valores. He escrito un código C++ de código abierto para el cálculo rápido de los residuos: https://github.com/wkaras/C-plus-plus-intrusive-container-templates/blob/master/modulus_hash.h