must - Hash más corto en Python para nombrar archivos de caché

python hashmap

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 para que se utilicen para "inicializar" el nombre de archivo. Quiero producir un nombre de archivo posiblemente único para cada objeto (no tantos). No deben chocar, pero si lo hacen, mi aplicación simplemente carecerá de 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 los ahorros acumulados al almacenar en caché todos los objetos hacen 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, la cadena de hash! Todavía no he encontrado ninguna colisión, pero me gustaría tener una mejor función de 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 razonable resistencia a la colisión?

Edición: el caso de uso es así: el cargador de datos obtiene una nueva instancia de un objeto portador de datos. Tipos únicos tienen reproducción única. por lo tanto, si existe un archivo de caché para hash(repr(obj)) , elimino ese archivo de caché y sustituyo obj con el objeto no seleccionado. Si hubo una colisión y el caché era una coincidencia falsa, lo noté. Entonces, si no tenemos caché o no tenemos una coincidencia falsa, en su lugar, inicio obj (recargando sus datos).

Conclusiones (?)

El str hash en python puede ser lo suficientemente bueno, solo estaba preocupado por su resistencia a la colisión. Pero si puedo juntar 2**16 objetos con él, va a ser más que suficiente.

Descubrí cómo tomar un hash hexadecimal (de cualquier fuente de hash) y almacenarlo de forma compacta con base64:

# ''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

Considere su caso de uso, si no tiene su corazón puesto en usar archivos de caché separados y no está demasiado lejos en esa ruta de desarrollo, podría considerar el uso del módulo de shelve .

Esto le dará un diccionario persistente (almacenado en un solo archivo dbm) en el que almacena sus objetos. El decapado / desenrollado se realiza de forma transparente, y no tiene que preocuparse por el hash, las colisiones, la E / S de archivos, etc.

Para las claves del diccionario de la estantería, solo debe usar repr (obj) y dejar que la shelve ocupe de esconder sus objetos por usted. 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

Answer 2

Estoy seguro de que hay una implementación de CRC32 en Python, pero puede ser demasiado corta (8 dígitos hexadecimales). Por el lado bueno, es muy rápido.

Lo encontré, binascii.crc32

Answer 3

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

Ya que menciona que una colisión es una molestia menor, le recomiendo que apunte a una longitud de hash que sea aproximadamente el cuadrado de la cantidad de objetos que tendrá, o un poco menos, pero no mucho menos que eso.

Desea crear un nombre de archivo: ¿se trata de un sistema de archivos que distingue entre mayúsculas y minúsculas, como es típico en Unix, o también tiene que atender sistemas que no distinguen entre mayúsculas y minúsculas? Esto es importante porque apunta a nombres de archivo cortos, pero la cantidad 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.

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

Incluso en un sistema que no distingue entre mayúsculas y minúsculas, aún puede hacerlo mejor que el hexadecimal: use el código base64.b32 y obtenga 5 bits por carácter.

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

Si tiene algunas decenas de miles de objetos, creo que estará bien con el hash incorporado (32 bits, por lo que 6-7 caracteres, dependiendo de la codificación elegida). Para un millón de objetos, querría 40 bits más o menos (7 u 8 caracteres): puede plegar (xor, no truncar ;-) un sha256 a lo largo con un número razonable de bits, por ejemplo, 128 , y use el operador % para cortarlo a la longitud deseada antes de codificar.

Answer 4

La función hash incorporada de las 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, tendrá solo 2**31 valores).

Has estado pidiendo la función hash más corta. Eso seria ciertamente

def hash(s):
  return 0

Pero supongo que realmente no lo dijiste así ...

Answer 5

Los hashes cortos significan que puede tener el mismo hash para dos archivos diferentes. Lo mismo puede suceder con los hashes grandes, pero es más raro. Es posible que estos nombres de archivos varíen según otras referencias, como el microtiempo (a menos que estos archivos se creen demasiado rápido).

Answer 6

Puedes acortar cualquier hash que desees simplemente truncándolo. md5 siempre tiene 32 dígitos hexadecimales, pero una subcadena arbitraria (o cualquier otro hash) tiene las cualidades adecuadas de un hash: valores iguales producen hashes iguales, y los valores se distribuyen alrededor de un grupo.

Answer 7

Si tienes una colisión, ¿cómo vas a decir que realmente sucedió?

Si fuera usted, usaría hashlib para sha1() the repr() , y luego obtendría una subcadena limitada (los primeros 16 caracteres, por ejemplo).

A menos que esté hablando de un gran número de estos objetos, sugeriría que utilice el hash completo. Entonces, la oportunidad de colisión es tan, tan, tan pequeña, que nunca vivirás para que esto suceda (es probable).

Además, si está lidiando con tantos archivos, supongo que su técnica de almacenamiento en caché debe ajustarse para acomodarla.

Answer 8

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