Comment hacher une chaîne en 8 chiffres?

106

Existe-t-il de toute façon que je puisse hacher une chaîne aléatoire en un nombre à 8 chiffres sans implémenter moi-même d'algorithmes?

Dorafmon
la source
2
hash ("your string")% 100000000
Theran
2
8 chiffres semblent trop petits et peuvent entraîner des collisions de hachages si vous avez un grand nombre d'enregistrements. stackoverflow.com/questions/1303021/…
DhruvPathak
Utilisez hashlib car le hash a un autre but!
architectonique
2
Tout nombre fini de chiffres entraînera des collisions pour un nombre suffisamment grand d'éléments de hachage, c'est pourquoi vous ne devriez pas les traiter comme des clés uniques - cela a tendance à se transformer en problème d'anniversaire.
Alex North-Keys
1
J'ai choisi "CityHash" pour hacher les chaînes en entiers longs à 19 chiffres (entiers 64 bits), en espérant que cela conduira à moins de collisions potentielles que la suggestion de Raymond ci-dessous. en.wikipedia.org/wiki/List_of_hash_functions
tryptofame

Réponses:

155

Oui, vous pouvez utiliser les modules hashlib intégrés ou la fonction de hachage intégrée. Ensuite, coupez les huit derniers chiffres à l'aide d'opérations modulo ou d'opérations de découpage de chaîne sur la forme entière du hachage:

>>> s = 'she sells sea shells by the sea shore'

>>> # Use hashlib
>>> import hashlib
>>> int(hashlib.sha1(s).hexdigest(), 16) % (10 ** 8)
58097614L

>>> # Use hash()
>>> abs(hash(s)) % (10 ** 8)
82148974
Raymond Hettinger
la source
26
annonce de service public ... cette technique n'entraîne pas réellement une valeur de hachage unique pour la chaîne; il calcule un hachage puis se transforme en une valeur unique non garantie
twneale
88
annonce de service public ... à l'exception du cas particulier des hachages parfaits sur un ensemble limité de valeurs d'entrée, les fonctions de hachage ne sont pas censées générer des valeurs uniques garanties.
Raymond Hettinger
5
Avez-vous lu la question du PO? Il (ou elle) voulait (ou avait besoin) de 8 décimales. En outre, la façon dont les tables de hachage fonctionnent est de hacher dans un petit espace de recherche (la table fragmentée). Vous semblez ne pas savoir que les fonctions de hachage veulent sont couramment utilisées et ne se soucient pas de la question qui a été posée.
Raymond Hettinger
17
J'ai lu la question. J'observe simplement que sur le même espace d'entrée que SHA-1, votre réponse est astronomiquement plus susceptible de produire une collision que non. Au moins un certain degré d'unicité est implicitement requis par la question, mais votre réponse est une fonction de hachage dans le même esprit que celle qui renvoie simplement 12345678 pour chaque entrée. J'ai pu générer expérimentalement une collision avec aussi peu que 1000 entrées en utilisant cette méthode. Pour conserver la même probabilité de collision que SHA-1, vous devez mapper des SHA-1 non tronqués à des entiers à 8 chiffres. Je pense que c'est digne d'un PSA
twneale
20
Attention, le ou les hash ne sont pas garantis pour donner les mêmes résultats sur toutes les plates-formes et exécutions.
M. Napik
94

La réponse de Raymond est excellente pour python2 (cependant, vous n'avez pas besoin des abs () ni des parens autour de 10 ** 8). Cependant, pour python3, il y a des mises en garde importantes. Tout d'abord, vous devez vous assurer que vous transmettez une chaîne codée. De nos jours, dans la plupart des cas, il est probablement préférable d'éviter sha-1 et d'utiliser quelque chose comme sha-256 à la place. Ainsi, l'approche hashlib serait:

>>> import hashlib
>>> s = 'your string'
>>> int(hashlib.sha256(s.encode('utf-8')).hexdigest(), 16) % 10**8
80262417

Si vous souhaitez utiliser la fonction hash () à la place, la mise en garde importante est que, contrairement à Python 2.x, dans Python 3.x, le résultat de hash () ne sera cohérent que dans un processus, pas entre les invocations python. Vois ici:

$ python -V
Python 2.7.5
$ python -c 'print(hash("foo"))'
-4177197833195190597
$ python -c 'print(hash("foo"))'
-4177197833195190597

$ python3 -V
Python 3.4.2
$ python3 -c 'print(hash("foo"))'
5790391865899772265
$ python3 -c 'print(hash("foo"))'
-8152690834165248934

Cela signifie la solution basée sur hash () suggérée, qui peut être raccourcie à seulement:

hash(s) % 10**8

ne renverra la même valeur que dans une exécution de script donnée:

#Python 2:
$ python2 -c 's="your string"; print(hash(s) % 10**8)'
52304543
$ python2 -c 's="your string"; print(hash(s) % 10**8)'
52304543

#Python 3:
$ python3 -c 's="your string"; print(hash(s) % 10**8)'
12954124
$ python3 -c 's="your string"; print(hash(s) % 10**8)'
32065451

Donc, selon que cela compte dans votre application (c'est le cas dans la mienne), vous voudrez probablement vous en tenir à l'approche basée sur hashlib.

JJC
la source
2
Il convient de noter que cette réponse a une mise en garde très importante depuis Python 3.3, pour se protéger contre le tar-pitting Python 3.3 et les versions ultérieures utilisent une graine de hachage aléatoire au démarrage.
Wolph
Si les chiffres ne sont pas votre principale exigence, vous pouvez également utiliser la hashlib.sha256("hello world".encode('utf-8')).hexdigest()[:8]sorcière qui aura encore des collisions
lony
Ils devraient mettre ça sur la boîte!
Tomasz
3

Juste pour compléter la réponse JJC, en python 3.5.3, le comportement est correct si vous utilisez hashlib de cette façon:

$ python3 -c '
import hashlib
hash_object = hashlib.sha256(b"Caroline")
hex_dig = hash_object.hexdigest()
print(hex_dig)
'
739061d73d65dcdeb755aa28da4fea16a02b9c99b4c2735f2ebfa016f3e7fded
$ python3 -c '
import hashlib
hash_object = hashlib.sha256(b"Caroline")
hex_dig = hash_object.hexdigest()
print(hex_dig)
'
739061d73d65dcdeb755aa28da4fea16a02b9c99b4c2735f2ebfa016f3e7fded

$ python3 -V
Python 3.5.3
user8948052
la source
-3

Je partage notre implémentation nodejs de la solution implémentée par @Raymond Hettinger.

var crypto = require('crypto');
var s = 'she sells sea shells by the sea shore';
console.log(BigInt('0x' + crypto.createHash('sha1').update(s).digest('hex'))%(10n ** 8n));
utilisateur 923227
la source
Vous partagez une solution nodejs dans une question sur python?
Harabeck
Oui, lorsque nous construisions le système - le backend a traité cela en utilisant python tandis que le frontend utilisait node.js. Nécessaire pour s'assurer que les deux fonctionnent de manière transparente.
utilisateur 923227