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é técnicas de hash utilizar al construir un filtro de floración en clojure?
¿Qué debo usar para la implementación del mapa de floración más rápida (en lugar de la más precisa) en Clojure?
Por lo tanto, lo divertido de los filtros bloom es que para que funcionen de manera efectiva necesitan múltiples funciones hash.
Java Strings ya tiene una función de 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.
Si no es así, probablemente querrás rodar el tuyo propio, en cuyo caso recomendaría usar String.getChars() para acceder a los datos sin procesar, luego utilizar esto para calcular varios hashcodes.
Clojure código para que pueda empezar (simplemente sumando los valores de caracteres):
(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
Nota el uso de Java de Clojure interoperabilidad llamar getChars, y el uso de areduce para darle una iteración muy rápido durante la matriz de caracteres.
Puede que también le interese esta implementación de filtro de floración 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.
Al haber escrito un Bloom Filter en Java (la pregunta era sobre JVM y algoritmos hash), no se necesitan múltiples funciones hash. De hecho (ver respuesta a continuación), un buen MumurHash es excelente para Bloom Filters porque es extremadamente rápido y la menor incidencia de colisión no es realmente un factor, ya que Bloom Filters tiene una tasa de falsos positivos de todos modos.El tipo de datos en el Conjunto tampoco es relevante, ya que una mejor práctica para el rendimiento y para administrar tasas de falsos positivos es suavizar la distribución del conjunto de bits al mezclar las teclas de entrada de todos modos. –
@Darrell - bueno, necesitas suficientes * bits * calculados de forma independiente para poder segmentar el resultado en múltiples funciones hash. Eso es lo que hace la respuesta a continuación: definiría eso como "usar múltiples funciones hash" :-) – mikera
La pregunta era sobre "librerías hash que pueden estar disponibles para los lenguajes basados en JVM", por lo que el comentario fue en referencia a esos versus el 'número de cubos de hash 'que se usan/calculan. Creo que la frase 'función hash' implica una función o método (implementación), mientras que el comentario a continuación indica 'calcular el número deseado de hashes'. Perdón por cualquier confusión, pero espero que esto aclare a los nuevos usuarios, ya que este es un tema de computación bastante pesado. –
Eche un vistazo a la implementación del filtro Bloom en Apache Cassandra. 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 this paper
y aquí es un fragmento de código fuente del 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 and Cassandra = Why used and why hashed several times?
¿Qué tipo de datos son las llaves? ¿Instrumentos de cuerda? Arrays de bytes? Enteros? UUIDs? – pmdj
Estoy probando la pertenencia a un conjunto de cadenas – jdoig
Puede intentar aplicando repetidamente una función hash de mezcla al valor hash incorporado reportado por el método 'hash()' en la cadena, p. Ej. http://www.cris.com/~Ttwang/tech/inthash.htm Los valores generados pueden correlacionarse demasiado, lo que podría hacer que el filtro de floración sea ineficaz. Un enfoque que he usado en el pasado es usar una función hash con un resultado muy largo, como SHA-256, y dividir el resultado en fragmentos. Esto puede ser demasiado lento para sus propósitos. Lo más simple podría ser hacer una búsqueda en google de 'función de hash de cadena' e implementar algunos de los resultados que proporciona. – pmdj