plus petite valeur de la fonction de hachage()?

Question

dans python (3), quelle est la plus petite valeur que hash(x) peut renvoyer? Je veux utiliser des hachages pour donner une «empreinte digitale» rapide aux valeurs de la base de données (ce qui permet de voir si deux textes longs et similaires sont réellement égaux ou non), et je veux me débarrasser des nombres négatifs (pour plus de simplicité)), alors j'ai pensé que j'ajouterais juste la plus petite valeur possible pour obtenir des valeurs de zéro et plus. the manual est très utile indiquant "Les valeurs de hachage sont des entiers." ce qui est à peu près tout ce que je savais avant.

J'étais un peu surpris aujourd'hui quand j'ai découvert que mon python compilé à la main sur un Ubuntu 64bit utilise apparemment 64 bits ou plus pour sa fonction de hachage; J'ai toujours pensé que ça devrait être 32bit. l'architecture de la machine a-t-elle un impact sur la fonction hash()?

également, lorsque j'ai compilé python, je n'ai pas défini d'option pour compiler une architecture 64 bits (en espérant que cela «fonctionnerait»). est-ce que python ajuste cela par lui-même ou est-ce que j'ai maintenant un python 32 bits sur une machine 64 bits? pas une question stupide je crois autant de fois que vous êtes offerts des paquets distincts en fonction de l'opérateur.

modifier: Je soupçonne fortement la réponse sera étroitement liée à sys.maxint qui a malheureusement été retiré de python 3. Je soupçonne que je devrais def xhash(x): return hash(x) - (-maxint - 1) si maxint était disponible. Je sais que cette valeur «a perdu sa valeur» en raison de l'unification des ints et des longs, mais il pourrait y avoir un domaine où cela pourrait encore s'avérer utile. quelqu'un a une idée de la façon de mettre en œuvre un analogue?

Answer 1

Les fonctions de hachage utilisent généralement la plage complète de la valeur de retour. La raison en est qu'ils sont généralement construits avec des opérations sur les bits (décalage, xoring, etc.) - les bits de la valeur de retour sont tous utilisés pendant l'algorithme.

Pourquoi les valeurs positives sont-elles plus faciles ou plus dures que les valeurs négatives?

Answer 2

hash()hash() peut renvoyer n'importe quel nombre entier, et comme vous l'avez vu, la taille de l'entier peut varier avec l'architecture. C'est l'une des raisons pour lesquelles le classement des dictionnaires est arbitraire: le même ensemble d'opérations sur deux plates-formes différentes peut donner des résultats différents car les hachages utilisés en cours de route peuvent différer.

Si tout ce que vous faites est d'afficher un hachage pour une empreinte rapide, alors gardez simplement un sous-ensemble des bits. C'est toujours valide comme un hachage. La seule exigence d'une fonction de hachage est que les valeurs égales doivent avoir des hachages égaux. Après cela, les différences entre les hachages affectent simplement l'efficacité des algorithmes utilisant le hachage, car les risques de collision augmentent ou diminuent.

Ainsi, par exemple, vous pourriez décider que vous voulez un hachage à 8 chiffres, et l'obtenir à l'aide:

hash(x) % 100000000 

Ou vous pourriez obtenir un hachage alphanumérique de huit caractères à afficher avec:

md5(hash(x)).hexdigest()[:8] 

Answer 3

la réponse à votre question devrait être:

assert(hash(100) == 100 and hash(-100) == -100) 
smallest_hash_value= -2**min(range(256), key=lambda i: hash(-2**i)) 

Cela dépend du fait que Python utilise le entier lui-même comme un hachage (à l'exception de -1) si le nombre entier est un résultat hash() valide. L'algorithme devrait normalement rester le même quelle que soit l'architecture.

Answer 4

donc aujourd'hui, je plus de chance au casino google, et ce que je trouve:

(1) l'architecture du système si un python donné est en cours d'exécution sur un 64 ou d'une machine 32 bits peut être trouvée par

from platform import architecture 
print(architecture()) 

de la documentation: « Interroge le fichier exécutable donné (par défaut le binaire interpréteur Python) pour diverses informations sur l'architecture Retourne un tuple (bits, de liaison) qui contiennent des informations sur l'architecture de bits et le format de liaison utilisé pour la. exécutable Les deux valeurs sont renvoyées en tant que chaînes. " sur ma machine, c'est ('64bit', 'ELF'). bingo.

(2) plus petit entier il n'y a pas sys.maxint en python 3 plus, mais il n'y a sys.maxsize. les docs disent "Un nombre entier donnant la valeur maximale qu'une variable de type Py_ssize_t peut prendre.C'est généralement 2**31 - 1 sur une plate-forme 32 bits et 2**63 - 1 sur une plateforme 64 bits." par conséquent,

from sys import maxsize 
assert maxsize == 2**63 - 1 

fonctionne sur ma machine.

(3) directement répondre à la question initiale: « la plus petite valeur de la fonction hash()devrait être moins ce sys.maxsize rapports pour cette raison, on peut s'attendre que

def xhash(x): return hash(x) + sys.maxsize + 1 

ne fera que jamais. signaler les valeurs ≥ 0. "