¿Está bien para usar solo 64 bits de sha1 hash como id?

Question

1) Con el propósito de una colisión hash muy baja, ¿puedo salirse con la suya simplemente usando la mitad de los 128 bits de un sha1 en lugar de lidiar con el sha1 mismo? Entiendo que esto no es adecuado para hashes criptográficos, pero solo necesito los hash para las claves de la tabla hash.

2) El tiempo de cálculo no es una prioridad, y además estoy recopilando datos muy pequeños. En particular, voy a tomar 2 o 3 hashes de 64 bits y mezclarlos para obtener otro hash de 64 bits. ¿Hay una mejor opción que sha1 para este propósito? Nuevamente, las colisiones deberían ser muy poco probables.

3) Soy un sql newb. ¿Es una buena idea usar hashes de 64 bits como id en sql? ¿Los id de 64 bits causarán problemas de rendimiento en sqlite o postgres? Voy a necesitar coordinar los datos en varias bases de datos (incluido un índice Lucene), así que pensé que debería tratar con los hash directamente en las tablas en lugar de molestar con los identificadores autoincormentados (que solo serían significativos en un db, no en todas las tiendas de datos). Creo que 64 bits es un buen compromiso: lo suficientemente grande para colisiones poco probables, pero ahorra espacio (¿y tiempo de búsqueda?).

4) ¿Qué hay de CRC-64? ¿Eso produce una distribución lo suficientemente aleatoria?

Answer 1

Si tiene pocos registros, es casi seguro que nunca tendrá una colisión hash en 64 bits. Probablemente caerá en esta categoría.

Hay debe haber ningún problema con el recorte por un hash criptográfico como sha1, porque si hubiera estructura interna en el hash entonces no sería lo suficientemente bueno para ser un hash criptográfico, y si no hay estructura, entonces cualquier subconjunto de los bits debe ser bastante aleatorio. Tenga en cuenta que solo estoy hablando de usar eso para ID, ¡no para fines criptográficos!

Pero realmente, ¿su SQL no tiene algún tipo de GUID? Y si lo hace, ¿por qué no usarlo?

Answer 2

Si el tiempo de cálculo no es importante ¿por qué no ir a los 128 bits enteros? ¿Hay alguna razón real para elegir 64 bits además de posibles problemas de almacenamiento? (y luego 8 bytes adicionales no te van a matar con un almacenamiento tan económico)

64 bits frente a 128 bits no causarán problemas de velocidad en SQLite, no estoy seguro acerca de mySQL.

Answer 3

Para una buena comparación de longitudes de hash, echar un vistazo a través de al http://en.wikipedia.org/wiki/List_of_hash_functions

Además, sólo una nota: SHA-1 es de 160 bits, no 128.

Answer 4

Sus claves necesitarán absoluta singularidad no alta probabilidad de singularidad Sugiero usar GUID en lugar de hash para las claves de compatibilidad entre bases de datos. Genere el hash como un mecanismo de búsqueda rápida, puede tener un índice no exclusivo en esto, pero en el caso de una colisión tendrá que comparar los datos reales para asegurarse de que son los mismos. Al sincronizar sus bases de datos, puede verificar el hash (usando rápidamente el índice) y si encuentra una colisión, entonces resuelva si los datos son los mismos y, por lo tanto, los GUID deben resolverse. Si no hay una colisión, simplemente actualice cualquier base de datos que necesite la entrada faltante e inserte usando el GUID de la otra base de datos.

Yo también veo un punto en la creación de su propio hash de hashes para ahorrar espacio. Si ya tiene los otros hashes, simplemente úselos (adjuntar, no repetir). Si no, simplemente use una función hash estándar como MD5 o SHA1 y almacene los datos resultantes.

Answer 5

Con hashes de 64 bits, tiene un 1% de posibilidades de una colisión con 6.1 × 10 registros. (Para otras combinaciones, vea Wikipedia page on the Birthday problem.) Puede tirar los primeros 64 bits, o el último, de cada segundo bit, no hace ninguna diferencia en las propiedades del hash.