La plus courte de hachage en python pour le nom des fichiers de cache

La le paradoxe d'anniversaire s'applique: étant donné une bonne fonction de hachage, le nombre attendu de hachages avant qu'une collision se produit est d'environ sqrt(N), où N est le nombre de valeurs différentes que la fonction de hachage peut prendre. (L'entrée de wikipedia que j'ai pointé donne la formule exacte). Ainsi, par exemple, si vous souhaitez ne pas utiliser plus de 32 bits, votre soucis de collision sont graves pour environ 64 KO objets (c'est à dire, 2**16 objets -- la racine carrée de la 2**32 différentes valeurs de votre fonction de hachage peut prendre). Combien d'objets vous attendez-vous à avoir, comme un ordre de grandeur?

Puisque vous mentionnez qu'une collision est un problème mineur, je vous recommande de viser une longueur de hachage qui est à peu près le carré du nombre d'objets que vous aurez, ou un peu moins, mais pas BEAUCOUP moins que cela.

Vous voulez faire un nom de fichier, c'est que sur la casse du système de fichiers, comme typique sur Unix, ou avez-vous à répondre à la casse des systèmes de trop? C'est important parce que vous visez pour les noms de fichiers courts, mais le nombre de bits par caractère que vous pouvez utiliser pour représenter votre hachage comme un nom de fichier change de façon spectaculaire sur le cas-sensive vs insensible systèmes.

Sur la casse du système, vous pouvez utiliser la bibliothèque standard du base64 module (je recommande le "urlsafe" version de l'encodage, c'est à dire cette fonction, d'éviter les '/' caractères qui pourraient être présentes dans la plaine base64 est important dans les noms de fichiers Unix). Cela vous donne 6 bits utilisable par caractère, beaucoup mieux que les 4 bits/char dans l'hex.

Même sur la casse du système, vous pouvez toujours faire mieux que hex -- utilisation en base64.b32encode et obtenez 5 bits par caractère.

Ces fonctions prennent et renvoient des chaînes; utiliser le struct module pour transformer des chiffres en chaînes si votre choix de la fonction de hachage génère des nombres.

Si vous avez quelques dizaines de milliers d'objets, je pense que vous serez très bien avec builtin de hachage (32 bits, 6-7 caractères en fonction de votre choix de l'encodage). Pour un million d'objets que vous aimeriez 40 bits ou (7 ou 8 caractères) -- vous pouvez plier (xor, ne pas tronquer;-) un sha256 vers le bas pour un long avec un nombre raisonnable de bits, dire 128, et utiliser le % opérateur de réduire encore plus pour la longueur souhaitée avant le codage.

Vous pouvez faire tout de hachage vous aimez le plus court, simplement en la tronquant. md5 est toujours de 32 chiffres hexadécimaux, mais l'arbitraire d'un sous-chaîne d'elle (ou de tout autre hachage possède les qualités d'un hachage: l'égalité des valeurs de produire de l'égalité des tables de hachage, et de la dispersion des valeurs autour d'un tas.

Si vous avez une collision, comment allez-vous dire qu'il s'est réellement passé?

Si j'étais vous, je voudrais utiliser hashlib à sha1() la repr(), et puis juste obtenir un limitées substring (les 16 premiers caractères, par exemple).

Sauf si vous parlez d'un grand nombre de ces objets, je suggère que vous venez d'utiliser la totalité de hachage. Puis la possibilité de collision est tellement, tellement, tellement, tellement petite, que vous ne serez jamais en direct de la voir arriver (probable).

Aussi, si vous traitez avec que de nombreux fichiers, je devine que votre technique de mise en cache doit être ajusté pour tenir compte de cela.

Condsidering votre cas d'utilisation, si vous n'avez pas votre coeur sur l'aide de séparer les fichiers de cache et vous n'êtes pas trop loin dans cette voie de développement, vous pourriez envisager d'utiliser la shelve module.

Cela vous donnera une persistante dictionnaire (stocké dans un seul fichier dbm) vous permet de stocker vos objets. Décapage/unpickling est effectuée de manière transparente, et vous n'avez pas à vous soucier de hachage, des collisions, des e/S de fichier, etc.

Pour la mettre en veilleuse les clés de dictionnaire, vous utilisez simplement repr(obj) et laissez shelve traiter accrocher vos objets pour vous. Un exemple 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