¿Cómo generar un hash único para una URL?

Question

Dadas estas dos imágenes de twitter.

http://a3.twimg.com/profile_images/130500759/lowres_profilepic.jpg 
http://a1.twimg.com/profile_images/58079916/lowres_profilepic.jpg 

Quiero descargarlos en sistema de ficheros local & almacenarlos en un solo directorio. ¿Cómo superaré los conflictos de nombres?

En el ejemplo anterior, no puedo almacenarlos como lowres_profilepic.jpg. Mi idea de diseño es tratar las URL como cadenas opacas, excepto para el último segmento. Qué algoritmos (implementado como f) puedo usar para convertir los prefijos en cadenas únicas.

f("http://a3.twimg.com/profile_images/130500759/") = 6tgjsdjfjdhgf 
f("http://a1.twimg.com/profile_images/58079916/") = iuhd87ysdfhdk 

De esa manera, puedo guardar los archivos como: -

6tgjsdjfjdhgf_lowres_profilepic.jpg 
iuhd87ysdfhdk_lowres_profilepic.jpg 

no quiero un algoritmo criptográfico, ya que esto tiene que ser una operación performant.

Answer 1

Veo que su pregunta es cuál es el mejor algoritmo de hash para este asunto. Es posible que desee comprobar esto Best hashing algorithm in terms of hash collisions and performance for strings

Answer 2

La naturaleza de un hash es que puede provocar colisiones. ¿Qué tal una de estas alternativas:

1. utilizan un árbol de directorios. Literalmente cree subdirectorios para cada componente de la URL.
2. Genera una ID única. El problema aquí es cómo mantener la asignación entre el nombre real y la ID guardada. Puede utilizar una base de datos que se correlaciona entre una URL y una ID única generada. Simplemente puede insertar un registro en una base de datos que genere identificadores únicos, y luego usar esa identificación como el nombre del archivo.

Answer 3

Uno de los conceptos clave de una URL es que es única. ¿Por qué no usarlo?

Cada algoritmo que acorta la información, puede producir colisiones. Tal vez poco probable, pero posible sin embargo

Answer 4

El sistema de gestión de contenido git se basa en SHA1 porque tiene muy pocas posibilidades de colisión.

Si es bueno para git, será bueno para usted.

Answer 5

Un enfoque muy simple:

f("http://a3.twimg.com/profile_images/130500759/") = a3_130500759.jpg 
f("http://a1.twimg.com/profile_images/58079916/") = a1_58079916.jpg 

Como las otras partes de esta URL son constantes, se puede utilizar el subdominio, la última parte de la ruta de consulta como un nombre de archivo único.

No sabe lo que podría ser un problema con esta solución

Answer 6

Usted dijo:

no quiero un algoritmo criptográfico, ya que esto tiene que ser una operación performant.

Bueno, entiendo su necesidad de velocidad, pero creo que debe considerar los inconvenientes de su enfoque. Si solo necesita crear hash para urls, debe seguir con él y no escribir un nuevo algoritmo, donde tendrá que lidiar con colisiones, por ejemplo.

Por lo que podría tener un Dictionary<string, string> trabajar como un cache para sus URL. Entonces, cuando obtiene una nueva dirección, primero realiza una búsqueda en esa lista y, si no encuentra una coincidencia, la utiliza y almacena para uso futuro.

Siguiendo esta línea, usted podría dar una oportunidad MD5:

public static void Main(string[] args) 
{ 
    foreach (string url in new string[]{ 
     "http://a3.twimg.com/profile_images/130500759/lowres_profilepic.jpg", 
     "http://a1.twimg.com/profile_images/58079916/lowres_profilepic.jpg" }) 
    { 
     Console.WriteLine(HashIt(url)); 
    } 
} 

private static string HashIt(string url) 
{ 
    Uri path = new Uri(new Uri(url), "."); 
    MD5CryptoServiceProvider md5 = new MD5CryptoServiceProvider(); 
    byte[] data = md5.ComputeHash(
     Encoding.ASCII.GetBytes(path.OriginalString)); 
    return Convert.ToBase64String(data); 
} 

que obtendrá:

rEoztCAXVyy0AP/6H7w3TQ== 
0idVyXLs6sCP/XLBXwtCXA== 

Answer 7

Parece lo que realmente quiere es tener un nombre de archivo legal que no lo hará colisionar con otros

• Cualquier codificación de la URL funcionará, incluso base64: p. Ej. filename = base64(url)
• Un hash criptográfico le dará lo que quiere - aunque usted afirma que este será un cuello de botella, no estar seguro hasta que haya Benchmarked

Answer 8

Mientras CRC32 produce un máximo de 2^32 valores independientemente de su entrada y por lo tanto no evitará conflictos, todavía es una opción viable para este escenario.

Es rápido, por lo que si se genera el nombre de archivo que los conflictos, sólo tiene que añadir/cambiar un carácter a su URL y simplemente volver a calcular el CRC.

4.3 mil millones posibles sumas de comprobación significan que la probabilidad de un conflicto de nombre de archivo, cuando se combina con el nombre de archivo original, será tan baja que no tendrá importancia en situaciones normales.

he utilizado este enfoque a mí mismo por algo similar y estaba satisfecho con el rendimiento. Ver Fast CRC32 in Software.

Answer 9

Independientemente de la forma en que lo hace (hash, codificación, consulta de base de datos) le recomiendo que no intenta asignar un gran número de direcciones URL de archivos en un directorio plana grande.

La razón es que las operaciones de búsqueda de archivos para la mayoría de los sistemas de archivos consiste en una exploración lineal a través de los nombres de archivo en un directorio. Entonces, si todos los N de sus archivos están en un directorio, una búsqueda implicará una media de N comparaciones en promedio; es decir O(N) (Tenga en cuenta que ReiserFS organiza los nombres en un directorio como BTree. Sin embargo, ReiserFS parece ser la excepción y no la regla.)

En lugar de un directorio plano grande, que sería mejor para mapear los URI a un árbol de directorios. Dependiendo de la forma del árbol, la búsqueda puede ser tan buena como O(logN). Por ejemplo, si organizó el árbol para que tuviera 3 niveles de directorio con un máximo de 100 entradas en cada directorio, podría alojar 1 millón de URL. Si ha diseñado el mapeo a utilizar 2 nombres de archivo de caracteres, cada directorio debe encajar fácilmente en un solo bloque de disco, y una búsqueda de ruta (suponiendo que los directorios necesarios ya están en caché) debería tomar unos pocos microsegundos.

Answer 10

Parece ser que la parte numérica de twimg.com URL ya son un valor único para cada imagen. Mi investigación indica que el número es secuencial (es decirel URL de ejemplo a continuación es para la imagen de perfil 433,484,366th cargada, que simplemente es la mía). Por lo tanto, este número es único. Mi solución sería simplemente usar la parte numérica del nombre de archivo como el "valor hash", sin temor a encontrar un valor no único.

• URL: http: //a2.twimg.com/profile_images/433484366/terrorbite-industries-256.png
• Nombre del archivo: 433484366.terrorbite-industrias-256.png
• Steam ID: 433484366

Ya utilizo este sistema para una secuencia de comandos de Python que muestra las notificaciones de los nuevos tweets, y como parte de su operación guarda en caché las miniaturas de las imágenes de perfil para reducir las descargas innecesarias.

P.S. No importa de qué subdominio se descargue la imagen, todas las imágenes están disponibles desde todos los subdominios.

Answer 11

Estoy jugando con thumbalizr usando una versión modificada de su script de almacenamiento en caché, y tiene algunas buenas soluciones, creo. El código está en github.com/mptre/thumbalizr pero la versión corta es que usa md5 para compilar los nombres de los archivos, y toma los dos primeros caracteres del nombre del archivo y lo usa para crear una carpeta que se llama exactamente lo mismo . Esto significa que es fácil romper las carpetas y encontrar rápidamente la carpeta correspondiente sin una base de datos. Me voló la cabeza con su simplicidad.

Se genera nombres de archivo como este http://pappmaskin.no/opensource/delicious_snapcasa/mptre-thumbalizr/cache/fc/fcc3a328e0f4c1b51bf5e13747614e7a_1280_1024_8_90_250.png

la última parte, _1280_1024_8_90_250, coincide con las diferentes configuraciones que utiliza la secuencia de comandos cuando se habla de la API thumbalizr, pero supongo fcc3a328e0f4c1b51bf5e13747614e7a es un MD5 recta de la URL, en este caso para thumbalizr.com

he intentado cambiar la configuración para generar imágenes de 200 píxeles de ancho, y que las imágenes va en la misma carpeta, pero en lugar de _250.png se llama _200.png

yo no tengo tenido tiempo para cavar tanto en el código, pero estoy seguro de que podría separarse de la lógica de thumbalizr y ser más genérico.

Answer 12

Puede utilizar UUID clase en Java para generar cualquier cosa en UUID de bytes que es único y que no va a tener un problema con las operaciones de búsqueda de archivos

String url = http://www.google.com; 
String shortUrl = UUID.nameUUIDFromBytes("http://www.google.com".getBytes()).toString();