javascript - hashids - Hash 32bit int a 16bit int?

id hash

Question

¿Cuáles son algunas formas sencillas de codificar un entero de 32 bits (p. Ej., Una dirección IP, por ejemplo, Unix time_t, etc.) hasta un entero de 16 bits?

Por ejemplo, hash_32b_to_16b(0x12345678) podría devolver 0xABCD .

Comencemos con esto como una solución ejemplo horrible, pero funcional:

function hash_32b_to_16b(val32b) {
    return val32b % 0xffff;
}

La pregunta es específicamente sobre JavaScript, pero no dude en agregar cualquier solución neutral para el idioma, preferiblemente sin usar las funciones de la biblioteca.

El contexto para esta pregunta es generar ID únicos (por ejemplo, un ID de 64 bits puede estar compuesto de varios hashes de 16 bits de varios valores de 32 bits). Evitar las colisiones es importante.

Simple = bueno Wacky + ofuscado = divertido.

Answer 1

Algo tan simple como esto ....

function hash_32b_to_16b(val32b) {    
    var h = hmac(secretKey, sha512);
    var v = val32b;
    for(var i = 0; i < 4096; ++i)
        v = h(v);
    return v % 0xffff;
}

Answer 2

Creo que esto es lo mejor que vas a conseguir. Podría comprimir el código en una sola línea, pero las variantes están ahí por ahora como documentación:

function hash_32b_to_16b(val32b) {
    var rightBits = val32b & 0xffff; // Left-most 16 bits
    var leftBits = val32b & 0xffff0000; // Right-most 16 bits

    leftBits = leftBits >>> 16; // Shift the left-most 16 bits to a 16-bit value

    return rightBits ^ leftBits; // XOR the left-most and right-most bits
}

Dados los parámetros del problema, la mejor solución tendría que cada hash de 16 bits correspondiera exactamente a 2 ^ 16 números de 32 bits. También sería IMO hash números de 32 bits secuenciales de manera diferente. A menos que me esté perdiendo algo, creo que esta solución hace esas dos cosas.

Yo diría que la seguridad no puede ser una consideración en este problema, ya que el valor de hash es solo unos pocos bits. Creo que la solución que proporcioné proporciona una distribución uniforme de números de 32 bits a hashes de 16 bits

Answer 3

Diría que solo aplique un hash estándar como sha1 o md5 y luego tome los últimos 16 bits de eso.

Answer 4

Esto depende de la naturaleza de los enteros. Si pueden contener algunas máscaras de bits, o pueden diferir por potencias de dos, entonces los XOR simples tendrán una alta probabilidad de colisiones. Puedes probar algo como (i>>16) ^ ((i&0xffff) * p) siendo p un número primo.

Los hashes de seguridad como MD5 son buenos, pero obviamente son una exageración aquí. Cualquier cosa más compleja que CRC16 es una exageración.

Answer 5

La clave para maximizar la preservación de la entropía de alguna "señal" original de 32 bits es garantizar que cada uno de los 32 bits de entrada tenga una capacidad independiente e igual para alterar el valor de la palabra de salida de 16 bits.

Como el OP solicita un tamaño de bit que es exactamente la mitad del original, la forma más sencilla de satisfacer este criterio es XOR en las mitades superior e inferior, como han mencionado otros. El uso de XOR es óptimo porque, como es obvious por la definición de XOR, se garantiza que la conmutación independiente de cualquiera de los 32 bits de entrada cambiará el valor de la salida de 16 bits.

El problema se vuelve más interesante cuando necesita una reducción adicional más allá de la mitad del tamaño , por ejemplo, de una entrada de 32 bits a, digamos, una salida de 2 bits . Recuerde, el objetivo es preservar la mayor cantidad de entropía de la fuente como sea posible, por lo que las soluciones que involucran el enmascaramiento ingenuo de los dos bits más bajos con (i & 3) generalmente se dirigen en la dirección incorrecta; al hacerlo, se garantiza que no hay forma de que los bits que no están enmascarados afecten el resultado, y eso generalmente significa que hay una parte arbitraria, posiblemente valiosa, de la señal de tiempo de ejecución que se está descartando sumariamente sin principio.

Siguiendo el párrafo anterior, por supuesto, puede repetir con XOR tres veces más para producir una salida de 2 bits con la propiedad deseada de estar igualmente influenciado por cada uno de los bits de entrada. Por supuesto, esa solución sigue siendo óptimamente correcta, pero involucra operaciones en bucle o múltiples operaciones no desarrolladas que, como resultado, ¡no son necesarias!

Afortunadamente, hay una buena técnica de solo dos operaciones que proporciona el resultado provablemente óptimo para esta situación. Al igual que con XOR , no solo garantiza que, para cualquier valor de 32 bits dado, la combinación de cualquiera de los bits de entrada produzca un cambio en el valor de salida de (por ejemplo) 2 bits, sino que también la distribución de 2 bits. Los valores de salida son perfectamente uniformes. En otras palabras, sobre los 4,294,967,296 posibles valores de entrada, habrá exactamente 1,073,741,824 de cada uno de los cuatro resultados de hash de 2 bits posibles { 0, 1, 2, 3 } .

El método que menciono aquí utiliza valores mágicos específicos que descubrí a través de una búsqueda exhaustiva, y que no parecen discutirse mucho en ninguna otra parte de Internet, al menos para el uso particular que se discute aquí (es decir, garantizar una distribución de hash uniforme que sea máxima preservación de la entropía). Curiosamente, de acuerdo con esta misma búsqueda exhaustiva, los valores mágicos son de hecho únicos, lo que significa que para cada uno de los anchos de bits de destino { 16, 8, 4, 2 } , el valor mágico que muestro a continuación es el único valor que, cuando se usa como muestro aquí, satisface los criterios de hashing perfectos descritos anteriormente.

Sin más preámbulos, el procedimiento único y matemáticamente óptimo para aplicar hashing de 32 bits a n = { 16, 8, 4, 2 } es multiplicar por el valor mágico correspondiente a n (sin signo, descartar el desbordamiento) y luego tomar la n más alta Bits del resultado. Para aislar esos bits de resultado como un valor de hash en el rango [0 ... (2ⁿ - 1)] , simplemente desplace hacia la derecha (sin firmar) el resultado de la multiplicación por 32 - n bits.

Los valores "mágicos" y la sintaxis de expresión tipo C son los siguientes:

El hash de máxima preservación de entropía para reducir de 32 bits a ...

Target Bits Multiplier Right Shift Expression ----------- ------------ ----------- ----------------------- 16 0x80008001 16 (i * 0x80008001) >> 16 8 0x80808081 24 (i * 0x80808081) >> 24 4 0x88888889 28 (i * 0x88888889) >> 28 2 0xAAAAAAAB 30 (i * 0xAAAAAAAB) >> 30

Notas:

1. Utilice la multiplicación de 32 bits sin firmar y descarte cualquier desbordamiento (no es necesaria la multiplicación de 64 bits).
2. Si aísla el resultado usando el cambio a la derecha (como se muestra), asegúrese de usar una operación de cambio sin firma .

[ edit: tabla agregada para valores de entrada de 64 bits]

El hash que preserva la entropía al máximo para reducir un valor de 64 bits a ...

Target Bits Multiplier Right Shift Expression ----------- ------------------ ----------- ------------------------------- 32 0x8000000080000001 32 (i * 0x8000000080000001) >> 32 16 0x8000800080008001 48 (i * 0x8000800080008001) >> 48 8 0x8080808080808081 56 (i * 0x8080808080808081) >> 56 4 0x8888888888888889 60 (i * 0x8888888888888889) >> 60 2 0xAAAAAAAAAAAAAAAB 62 (i * 0xAAAAAAAAAAAAAAAB) >> 62

Más discusión

Todo esto me pareció genial. En términos prácticos, el requisito teórico de la información clave es la garantía de que, para cualquier valor de entrada de m-bit y su correspondiente valor de hash de n-bit , el cambio de cualquiera de los m bits de fuente siempre causa algún cambio en el resultado de n-bit valor Ahora, aunque hay 2ⁿ valores de resultados posibles en total, uno de ellos ya está "en uso", ya que cambiar el resultado a uno no sería ningún cambio. Esto deja solo 2ⁿ - 1 valores de resultado que son elegibles para ser utilizados por el conjunto completo de m valores de entrada producidos por un solo bit-flip.

Consideremos un ejemplo; de hecho, para mostrar cómo esta técnica puede parecer casi mágica o fantasmagórica, consideraremos un caso más extremo, donde m = 64 y n = 2 . Con 2 bits de salida hay cuatro valores de resultado posibles, { 0, 1, 2, 3 } . Asumiendo un valor de entrada de 64 bits arbitrario 0x7521d9318fbdf523 , obtenemos su valor de hash de 2 bits de 1 :

 (0x7521d9318fbdf523 * 0xAAAAAAAAAAAAAAAB) >> 62   // result -->  ''1''

Pero este resultado implica que ningún valor en el conjunto de 64 valores donde se 0x7521d9318fbdf523 un bit único de 0x7521d9318fbdf523 puede tener el mismo valor de resultado . Es decir, ninguno de esos otros 64 resultados puede usar el valor 1 y todos deben usar 0 , 2 o 3 . Cuando cada uno de los valores de entrada de 2⁶⁴ acapara egoístamente una cuarta parte del espacio de salida de 64 de sus pares, ¿existe una solución que satisfaga a la vez la totalidad de todas?

Bien seguro, para mostrar que (exactamente?) Uno lo hace , aquí están los valores de resultado de hash, ordenados en orden, para entradas que cambian un solo bit de 0x7521d9318fbdf523 (de una en una), desde MSB (posición 63) hasta LSB (0).

3 2 0 3 3 3 3 3 3 0 0 0 3 0 3 3 0 3 3 3 0 0 3 3 3 0 0 3 3 0 3 3 
0 0 3 0 0 3 0 3 0 0 0 3 0 3 3 3 0 3 0 3 3 3 3 3 3 0 0 0 3 0 0 3    // <-- no ''1'' values

Como puede ver, no hay valores 1 , lo que implica que cada bit en la fuente "tal cual" debe contribuir a influir en el resultado (o, si lo prefiere, el estado de facto de cada bit en cada bit en 0x7521d9318fbdf523 es esencial para evitar que el resultado sea "no- 1 "). Dado que no importa qué cambio de un solo bit realice en la entrada de 64 bits, el valor del resultado de 2 bits ya no será 1 .

Tenga en cuenta que la tabla de "valores perdidos" que se muestra arriba se eliminó del análisis de solo el valor de ejemplo elegido al azar 0x7521d9318fbdf523 ; Cada otro valor de entrada posible tiene una tabla similar propia, cada una extrañamente extraña del valor de resultado real de su propietario y, sin embargo, de alguna manera es globalmente consistente en su conjunto de miembros. Esta propiedad corresponde esencialmente a preservar al máximo la entropía disponible durante la tarea de reducción de ancho de bits (inherentemente con pérdida).

Así que vemos que cada uno de los 2 posibles valores de origen impone de forma independiente, en exactamente otros 64 valores de origen, la restricción de excluir uno de los posibles valores de resultado. Lo que desafía mi intuición acerca de esto es que hay cuatrillones no contados de estos conjuntos de 64 miembros, cada uno de cuyos miembros también pertenece a otros 63 conjuntos, aparentemente no relacionados, de bit twiddling. Sin embargo, a pesar de este desconcertante rompecabezas de restricciones entrelazadas, es trivial explotar la resolución (supongo) que, al mismo tiempo, satisface a todas exactamente.

Todo esto parece estar relacionado con algo que puede haber notado en las tablas anteriores: es decir, no veo ninguna forma obvia de extender la técnica al caso de comprimir hasta un resultado de 1 bit . En este caso, solo hay dos valores de resultado posibles { 0, 1 } , por lo que si alguno / cada valor de entrada de 64 bits dado (por ejemplo) todavía excluye sumariamente su propio resultado de ser el resultado para los 64 de su bit único. Los vecinos flip, entonces eso ahora esencialmente impone el otro , solo el valor restante en esos 64. El desglose matemático que vemos en la tabla parece indicar que un resultado simultáneo en tales condiciones es un puente demasiado lejano.

En otras palabras, la característica especial de obvious de XOR (es decir, su garantía lujosamente confiable de que, a diferencia de AND , OR , etc., puede cambiar un poco) no sorprendentemente tiene un cierto costo, a saber, una demanda ferozmente no negociable de una cierta cantidad de espacio para el codo (al menos 2 bits) para trabajar.

Answer 6

Suponiendo que esperas que los bits menos significativos sean los que más ''varíen'', creo que probablemente obtendrás una distribución lo suficientemente buena usando solo los 16 bits más bajos del valor como un hash.

Si los números que va a hacer hash no tendrán ese tipo de distribución, entonces el paso adicional de xoring en los 16 bits superiores puede ser útil.

Por supuesto, esta sugerencia es si tiene la intención de utilizar el hash simplemente para algún tipo de esquema de búsqueda / almacenamiento y no está buscando las propiedades relacionadas con criptografía de no adivinabilidad y no reversibilidad (las sugerencias de Xoring no están disponibles). Realmente no te compro tampoco.