El hash más corto en python para nombrar archivos de caché

Question

¿Cuál es el hash más corto (en forma de nombre de archivo, como un hexdigest) disponible en python? Mi aplicación quiere guardar archivos de caché para algunos objetos. Los objetos deben tener repr() único, por lo que se usan para 'sembrar' el nombre del archivo. Quiero producir un nombre de archivo posiblemente único para cada objeto (no tantos). No deberían colisionar, pero si lo hacen, mi aplicación simplemente carecerá de memoria caché para ese objeto (y tendrá que volver a indexar los datos de ese objeto, un costo menor para la aplicación).

Por lo tanto, si hay una colisión perdemos un archivo de caché, pero es el ahorro acumulado de almacenar en caché todos los objetos hace que la aplicación se inicie mucho más rápido, por lo que no importa mucho.

Ahora mismo estoy usando ABS (hash (repr (obj))); ¡Así es, el hash de cuerdas! Aún no he encontrado ninguna colisión, pero me gustaría tener una mejor función hash. hashlib.md5 está disponible en la biblioteca de python, pero el hexdigest es realmente largo si se coloca en un nombre de archivo. Alternativas, con una razonable resistencia a la colisión?

Edit: El caso de uso es así: El cargador de datos recibe una nueva instancia de un objeto que transmite datos. Los tipos únicos tienen repr exclusivo. entonces, si existe un archivo de caché para hash(repr(obj)), deshago ese archivo de caché y reemplazo obj con el objeto no caído. Si hubo una colisión y el caché fue una coincidencia falsa lo noté. Entonces, si no tenemos memoria caché o tenemos una coincidencia falsa, en su lugar, inicio OBJ (recargando sus datos).

Conclusiones (?)

El hash str en Python puede ser lo suficientemente bueno, fue sólo preocupado por su resistencia al choque. Pero si puedo usar hash 2**16 objetos con él, será más que suficiente.

descubrí cómo tomar un hash hexagonal (de cualquier fuente de hash) y almacenarlo de forma compacta con base 64:

# 'h' is a string of hex digits 
bytes = "".join(chr(int(h[i:i+2], 16)) for i in xrange(0, len(h), 2)) 
hashstr = base64.urlsafe_b64encode(bytes).rstrip("=") 

Answer 1

El birthday paradox aplica: dado una buena función de hash, el número esperado de hashes antes de que ocurra una colisión es de aproximadamente sqrt (N), donde N es el número de valores diferentes que la función hash puede tomar. (La entrada de wikipedia que he señalado proporciona la fórmula exacta). Así, por ejemplo, si desea utilizar no más de 32 bits, sus preocupaciones de colisión son graves por alrededor de 64 K (es decir, objetos Objetos - 2**16 la raíz cuadrada de los valores diferentes 2**32 su función hash puede tomar). ¿Cuántos objetos espera tener, como un orden de magnitud?

Como mencionas que una colisión es una molestia menor, te recomiendo que busques una longitud de hash que sea aproximadamente el cuadrado de la cantidad de objetos que tendrás, o un poco menos pero no MUCHO menos que eso.

¿Desea crear un nombre de archivo? ¿Es eso en un sistema de archivos sensible a las mayúsculas y minúsculas, como es típico en Unix, o tiene que atender también a los sistemas que no distinguen entre mayúsculas y minúsculas? Esto es importante porque busca nombres de archivos cortos, pero el número de bits por carácter que puede usar para representar su hash como nombre de archivo cambia drásticamente en sistemas sensibles a mayúsculas y minúsculas frente a sistemas insensibles.

En un sistema de mayúsculas y minúsculas, puede utilizar el módulo de la biblioteca estándar base64 (recomiendo el "urlsafe" versión de la codificación, es decir this función, como evitar '/' caracteres que podrían estar presentes en la base 64 liso es importante en nombres de archivo Unix). Esto le da 6 bits utilizables por carácter, mucho mejor que los 4 bits/char en hex.

Incluso en un sistema de mayúsculas y minúsculas, todavía se puede hacer mejor que hexagonal - base64.b32encode utilizar y obtener 5 bits por carácter.

Estas funciones toman y devuelven cadenas; use el módulo struct para convertir números en cadenas si su función hash elegida genera números.

Si usted tiene unas pocas decenas de miles de objetos creo que se le multa de almohadilla incorporada (32 bits, por lo 6-7 caracteres en función de su codificación elegida). Para un millón de objetos, querrás 40 bits más o menos (7 u 8 caracteres): puedes doblar (xor, no truncar ;-) un sha256 por debajo de un largo con un número razonable de bits, digamos 128 o menos , y use el operador % para cortarlo más allá de la longitud deseada antes de codificar.

Answer 2

Estoy seguro de que hay una aplicación CRC32 en Python, pero que pueden ser demasiado corto (8 dígitos hexadecimales). Por el lado positivo, es muy rápido.

encontró, binascii.crc32

Answer 3

Si usted tiene una colisión, ¿cómo vas a decir que en realidad pasó?

Si yo fuera usted, me gustaría utilizar hashlib a sha1() la repr(), y luego acaba de obtener una subcadena limitada de la misma (primeros 16 caracteres, por ejemplo).

A menos que esté hablando de un gran número de estos objetos, le sugiero que simplemente use el hash completo. Entonces, la oportunidad de colisión es tan, tan, tan, tan pequeña, que nunca vivirás para ver que ocurra (probablemente).

Además, si se trata de que muchos archivos, supongo que su técnica de almacenamiento en caché se debe ajustar para acomodarlo.

Answer 4

La función hash incorporada de cadenas es bastante libre de colisiones, y también bastante corta. Tiene valores de 2**32, por lo que es bastante improbable que encuentre colisiones (si usa su valor de abs, solo tendrá valores de 2**31).

Has estado solicitando la función hash más corta.Eso sería sin duda

def hash(s): 
    return 0 

pero supongo que en realidad no quiere decir que de esa manera ...

Answer 5

hashes cortos significa que usted puede tener el mismo hash para dos archivos diferentes. Lo mismo puede suceder para los hashes grandes también, pero es mucho más raro. Tal vez estos nombres de archivo deberían variar según otras referencias, como microtime (a menos que estos archivos se creen demasiado rápido).

Answer 6

Usted puede hacer cualquier picadillo te gusta más corto simplemente truncándolo. md5 siempre tiene 32 dígitos hexadecimales, pero una subcadena arbitraria de ella (o cualquier otro hash) tiene las cualidades adecuadas de un hash: los valores iguales producen hash iguales, y los valores se reparten en un montón.

Answer 7

Utilizamos hashlib.sha1.hexdigest(), que produce cadenas aún más largos, para los objetos de caché con buen éxito. Nadie está mirando realmente los archivos de caché de todos modos.

Answer 8

Condsidering su caso de uso, si no tiene su corazón puesto en utilizar archivos de caché separados y no está muy lejos en esa ruta de desarrollo, puede considerar el uso del módulo shelve.

Esto le dará un diccionario persistente (almacenada en un solo archivo dBm) en la que se almacenan los objetos. El decapado/descortezado se realiza de forma transparente, y no tiene que preocuparse por hashing, colisiones, archivos de E/S, etc.

Para las claves del diccionario de archivado, solo debe usar repr (obj) y dejar que shelve con esconder tus objetos por ti. Un ejemplo simple:

import shelve 
cache = shelve.open('cache') 
t = (1,2,3) 
i = 10 
cache[repr(t)] = t 
cache[repr(i)] = i 
print cache 
# {'(1, 2, 3)': (1, 2, 3), '10': 10} 
cache.close() 

cache = shelve.open('cache') 
print cache 
#>>> {'(1, 2, 3)': (1, 2, 3), '10': 10} 
print cache[repr(10)] 
#>>> 10