Hash 32bit int a 16bit int?

¿Cuáles son algunas formas simples de hash de un entero de 32 bits (por ejemplo, dirección IP, por ejemplo, Unix time_t, etc.) hasta un número entero de 16 bits?Hash 32bit int a 16bit int?

E.g. hash_32b_to_16b(0x12345678) podría devolver 0xABCD.

Vamos a empezar con esto como una solución horrible ejemplo pero funcional:

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

pregunta es específicamente acerca de JavaScript, pero no dude en añadir cualquier soluciones independientes del idioma, preferentemente sin utilizar funciones de biblioteca.

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

Simple = bueno. Wacky + ofuscado = divertido.

Fuente

2010-06-17 dkamins

XOR los 2 bytes altos con los 2 bytes bajos? 0x1234 XOR 0x5678. Pero no puede etiquetar la pregunta con 'criptografía' y pedir algo como esto ... –

@Remus: ¿Por qué no puedo etiquetarlo como 'criptografía'?¿No es esta una pregunta destilada y extremadamente simple relacionada con la criptografía? PD ¿Por qué no publicar tu comentario como respuesta? – dkamins

Para el punto de Remus, estoy de acuerdo en que esto no se trata de criptografía. Si estoy pensando en este derecho, su hash de 16 bits se correlacionará con uno de dos enteros de 32 bits. Tengo curiosidad sobre el problema particular que estás tratando de resolver, y espero que no tenga nada que ver con la seguridad. –

Esto depende de la naturaleza de los enteros. Si pueden contener algunas máscaras de bits, o pueden diferir en potencias de dos, entonces los XOR simples tendrán una alta probabilidad de colisiones. Puede intentar 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 excesiva.

Fuente

2010-06-17 01:16:25 Rotsor

Este es un punto interesante y aparentemente relevante para las direcciones IP hash, ¿sí? – dkamins

Sí. Para valores de tiempo, i & 0xffff debería ser suficiente. (esperando que no haya sueño (65536); en cualquier parte :)) – Rotsor

¿Bastará con un número primo fijo? ¿Por qué funciona esto? – dkamins

Creo que esto es lo mejor que vas a obtener. Se podría comprimir el código de una sola línea, pero el de var 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 cada uno de hash de 16 bits corresponden exactamente a 2^16 números de 32 bits. También sería IMO hash números secuenciales de 32 bits 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 hash es muy pocos bits. Creo que la solución que di proporciona una distribución uniforme de los números de 32 bits a 16 bits hashes

Fuente

2010-06-17 00:40:11

¿Por qué crees que es el mejor? Creo que se pueden producir muchas colisiones por números útiles y frecuentes. – Rotsor

Esta no es la mejor idea. La razón es que las direcciones IP a menudo se asignan como subredes contiguas. Esto significa que si la dirección IP A.B.C.D existe en una red, entonces A. (B^1) .C.D y A.B.C. (D^1) son un poco más propensos a existir también y obtendrán el mismo hash. Obviamente, cualquier hash tendrá muchas colisiones. Pero su esquema tendrá más colisiones de las que esperaría al dividir los enteros de 32 bits de forma uniforme. Obtendrás mejores resultados al mezclar un poco más las piezas. – sigfpe

los criterios que usaste para evaluar la calidad de la función hash, mantenlos incluso para el más simple: hash = val & 0xffff. Sin embargo, estas funciones tienen diferentes probabilidades de colisión en datos de la vida real. – Rotsor

Algo tan simple como este ....

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; 
}

Fuente

2010-06-17 00:40:34 yfeldblum

¿Por qué 4096 veces? – dkamins

Para reducir la velocidad. Esta es una técnica común para contraseñas hash, para hacer que los órdenes de magnitud sean más difíciles de crear una tabla arcoíris o contraseñas de fuerza bruta. – yfeldblum

yo diría que sólo se aplica un hash SHA1 o estándar como md5 y luego tomar los últimos 16 bits de eso.

Fuente

2010-06-17 00:41:16 dreeves

¿Podría haber problemas con flujos de entrada cortos (como 4 bytes) para sha1 o md5? – dkamins

sh1 y md5 generalmente no están disponibles en entornos JavaScript. ¿Hay versiones ligeramente menos seguras pero muy simplificadas que se pueden expresar en algunas líneas de JS? – dkamins

Suponiendo que espere que los bits menos significativos 'varíen' al máximo, creo que probablemente obtendrá 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 hash no tendrán ese tipo de distribución, entonces el paso adicional de xor-ing en los 16 bits superiores podría 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 busca las propiedades relacionadas con la criptografía de la no capacidad de adivinación y la no reversibilidad (que el xor -las sugerencias realmente no te compran tampoco).

Fuente

2010-06-17 00:53:37

Hash 32bit int a 16bit int?

Respuesta

Cuestiones relacionadas