java - ¿Qué técnicas de hashing usar al construir un filtro de floración en clojure?

bloom-filter

Question

Quiero construir un filtro de floración en Clojure, pero no tengo mucho conocimiento de todas las bibliotecas hash que pueden estar disponibles para los lenguajes basados ​​en JVM.

¿Qué debo usar para la implementación del mapa de floración más rápida (en oposición a la más precisa) en Clojure?

Answer 1

Eche un vistazo a la implementación de Bloom Filter en Apache Cassandra . Esto utiliza el algoritmo MurmurHash3 muy rápido y combina dos hashes (o dos partes del mismo hash, desde la actualización a MurmurHash3 en lugar de MurmurHash2) de diferentes maneras para calcular el número deseado de hash.

El enfoque de generación combinatoria se describe en este documento

y aquí hay un fragmento del código fuente de Cassandra:

    long[] hash = MurmurHash.hash3_x64_128(b, b.position(), b.remaining(), 0L);
    long hash1 = hash[0];
    long hash2 = hash[1];
    for (int i = 0; i < hashCount; ++i)
    {
        result[i] = Math.abs((hash1 + (long)i * hash2) % max);
    }

Ver también Bloomfilter y Cassandra = ¿Por qué se usaron y por qué hasheado varias veces?

Answer 2

Entonces, lo divertido de los filtros bloom es que para funcionar de manera efectiva necesitan múltiples funciones hash.

Java Strings ya tiene una función hash incorporada que puede usar - String.hashCode () con un hash entero de 32 bits. Es un código hash OK para la mayoría de los propósitos, y es posible que esto sea suficiente: si divide esto en 2 códigos hash de 16 bits por separado, entonces esto podría ser suficiente para que su filtro bloom funcione. Probablemente tengas algunas colisiones pero está bien, se espera que los filtros de floración tengan algunas colisiones.

De lo contrario, es probable que desee ejecutar el suyo propio, en cuyo caso recomendaría usar String.getChars () para acceder a los datos de registro sin formato y luego usar esto para calcular varios códigos hash.

Código de Clojure para que comiences (solo resumiendo los valores de los personajes):

(let [s "Hello"
      n (count s)
      cs (char-array n)]
  (.getChars s 0 n cs 0)
  (areduce cs i v 0 (+ v (int (aget cs i)))))
=> 500

Tenga en cuenta el uso de la interoperabilidad Java de Clojure para llamar a getChars, y el uso de areduce para darle una iteración muy rápida sobre la matriz de caracteres.

Puede que también le interese esta implementación de filtro de bloom de Java que encontré en Github: https://github.com/MagnusS/Java-BloomFilter . La implementación de código hash se ve bien a primera vista, pero utiliza una matriz de bytes que creo que es un poco menos eficiente que el uso de caracteres debido a la necesidad de ocuparse de la sobrecarga de codificación de caracteres.