algorithm - secure - ¿Qué es una buena función hash para una colección(es decir, un conjunto múltiple) de enteros?
sha-256 algorithm (6)
Bits inversos.
Por ejemplo, 00001011 se convierte en 11010000. Luego, solo SUMA todos los elementos del conjunto invertido.
Si necesitamos O (1) al insertar / eliminar, el SUM habitual funcionará (y así es como se implementan los Conjuntos en Java), aunque no está bien distribuido en conjuntos de enteros pequeños.
En caso de que nuestro conjunto no se distribuya uniformemente (como suele serlo), necesitamos mapear N-> f (N), de modo que f (N) se distribuya uniformemente para la muestra de datos esperada. Generalmente, la muestra de datos contiene muchos más números cercanos a cero que números cercanos al máximo. En este caso, el hash de bits inverso los distribuiría de manera uniforme.
Ejemplo en Scala:
def hash(v: Int): Int = {
var h = v & 1
for (i <- 1 to 31) {
h <<= 1;
h |= ((v >>> i) & 1)
}
h
}
def hash(a: Set[Int]): Int = {
var h = 0
for (e: Int <- a) {
h += hash(e);
}
h
}
Pero el hash de nuestro conjunto múltiple no será uniforme, aunque será mucho mejor que el simple SUMA.
Estoy buscando una función que asigne un conjunto múltiple de enteros a un entero, con suerte con algún tipo de garantía como la independencia de pares.
Idealmente, el uso de la memoria sería constante, y el valor de hash podría actualizarse en O (1) tiempo después de una inserción / eliminación. (Esto prohíbe hacer algo como ordenar los enteros y usar una función hash como h (x) = h_1 (x_1, h_2 (x_2, h_3 (x_3, x_4))).)
Los hashes XORing juntos no funcionan porque h ({1,1,2}) = h ({2})
Creo que multiplicar hashes juntos módulo a primo podría funcionar si la función de hash subyacente tuviera una garantía irrealmente fuerte, como la independencia n.
El hash min debería funcionar aquí. Aplique permutación, mantenga un pequeño conjunto de n elementos mínimos, elija el más grande.
Elaboración: esta es una forma sencilla de trabajar en O (1) tiempo y espacio. Necesita algo así como una cola de prioridad, sin que el vínculo a los valores iniciales sea demasiado obvio. Así que ordena su cola de prioridad de acuerdo con alguna clave elaborada, que es equivalente a ejecutar una cola de prioridad en una permutación del orden de clasificación normal. Haga que la cola haga un seguimiento de la multiplicidad para que los elementos seleccionados también formen un conjunto múltiple.
Dicho esto, no estoy seguro de que esto se disperse lo suficientemente bien (y la ejecución de múltiples permutaciones puede llegar a ser costosa), por lo que tal vez sea mejor basarse en la respuesta de Bradley. Aquí hay un pellizco para que los elementos repetidos no se cancelen:
xor(int_hash(x_n, multiplicity_n) foreach n)
Estoy de acuerdo con Dzmitry en el uso de SUMA aritmética de hash, pero recomiendo usar una función hash con una buena distribución de salida para enteros de entrada en lugar de solo invertir los bits en el entero. Los bits de inversión no mejoran la distribución de salida. Incluso puede empeorar la distribución de salida, ya que la probabilidad de que los bits de orden superior se pierdan debido al desbordamiento de la suma es mucho mayor que la probabilidad de que los bits de orden inferior se pierdan en este caso. Este es un ejemplo de una función hash rápida con una buena distribución de salida: http://burtleburtle.net/bob/c/lookup3.c . Lea también el documento que describe cómo se deben construir las funciones hash: http://burtleburtle.net/bob/hash/evahash.html .
El uso de SUM de valores hash para cada elemento del conjunto satisface los requisitos en las preguntas:
- El uso de la memoria es constante. Necesitamos almacenar un entero ordinario que contenga un valor de hash para cada conjunto. Este número entero se usará para la actualización O (1) del hash al agregar / eliminar elementos del conjunto.
- La adición de un nuevo elemento requiere solo la adición del valor hash del elemento al valor hash existente, es decir, la operación es O (1).
- La eliminación del elemento existente solo requiere la resta del valor hash del elemento del valor hash existente, es decir, la operación es O (1).
- El hash será diferente para los conjuntos, que solo se diferencian por pares de elementos idénticos.
SUM y SUB son operaciones seguras ante el desbordamiento de enteros, ya que son reversibles en una aritmética modular , donde el módulo es 2 ^ 32 o 2 ^ 64 para los enteros en java.
Hice esta misma pregunta en cstheory.stackexchange.com y obtuve una buena respuesta:
Knuth toca esto en TAoCP, y esto es casi un duplicado de ¿Qué función de hash de enteros es buena que acepta una clave de hash de entero? .
Para su situación, convertir su conjunto múltiple en un solo número entero y luego realizar el hash descrito en la publicación vinculada puede ser lo que desee hacer. Convertir una colección en un número es trivial; Una concatenación de los dígitos servirá.
Para obtener más información sobre el método de Knuth, busque "Método multiplicativo de Knuth"
-tjw
Una vez hice una pregunta similar, "¿ Buena función hash para permutaciones? ", Y obtuve un hash que funcionó muy bien para mi caso de uso, tengo muy pocas colisiones en mi código de trabajo. También podría funcionar bien para ti. Calcula algo como esto:
// initialize this->hash with 1
unsigned int hash = 1;
void add(int x) {
this->hash *= (1779033703 + 2*x);
}
Entonces, cuando agregue un número x , actualice su código hash con la fórmula anterior. El orden de los valores no es importante, siempre obtendrá el mismo valor hash.
Cuando desee fusionar dos conjuntos, simplemente multiplique el valor de hash.
Lo único que no estoy seguro de si es posible es eliminar un valor en O (1).