rapide, de grande largeur, non cryptographique chaîne de hachage en python

J'ai un besoin pour une haute performance de la chaîne de fonction de hachage en python qui produit des entiers avec au moins 34 bits de sortie (64 bits serait logique, mais 32 est trop peu). Il y a plusieurs autres questions de ce genre sur un Débordement de Pile, mais de ceux de tous les acceptée/upvoted réponse que j'ai pu trouver est tombé dans l'une des catégories suivantes, qui ne s'appliquent pas (pour la raison.)

  • Utiliser le haut- hash() fonction. Cette fonction, au moins sur la machine que je suis en développement (avec python 2.7, et un processeur 64 bits) produit un nombre entier qui correspond à l'intérieur de 32 bits - pas assez grand pour mes fins.
  • Utilisation hashlib. hashlib offre de hachage cryptographique routines, qui sont loin plus lentement qu'ils doivent être pour les non-cryptographiques fins. Je trouve cette auto-évident, mais si vous avez besoin de repères et de citations pour vous convaincre de ce fait, alors je peux leur fournir.
  • Utiliser le string.__hash__() fonction comme un prototype pour écrire votre propre fonction. J'imagine que ce sera la bonne façon de procéder, sauf que cette fonction de l'efficacité réside dans son utilisation de la c_mul fonction, qui s'enroule autour de 32 bits - encore une fois, trop petit pour mon utilisation! Très frustrant, c'est tellement proche de la perfection!

Une solution idéale serait d'avoir les propriétés suivantes, dans une relative, sans ordre d'importance.

  1. Ont une gamme de puissance s'étend au moins 34 bits de long, probablement en 64 bits, tout en préservant cohérente avalanche propriétés de plus de tous bits. (Concaténation de 32 bits hachages tend à violer l'avalanche propriétés, au moins avec mon mutisme des exemples).
  2. Portable. Compte tenu de la même chaîne d'entrée sur deux machines différentes, je devrais obtenir le même résultat à chaque fois. Ces valeurs seront stockées dans un fichier pour une utilisation ultérieure.
  3. De haute performance. Le plus rapide est le mieux que cette fonction sera appelée à près de 20 milliards de fois au cours de l'exécution du programme que je suis en cours d'exécution (c'est la critique de code pour le moment.) Il n'a pas besoin d'être écrit en C, il est vraiment juste besoin de surpasser md5 (quelque part dans le royaume de l'intégré dans la table de hachage() pour les chaînes).
  4. Accepter une "perturbation" (quel est le meilleur terme à utiliser, ici?) entier comme entrée pour modifier la sortie. J'ai mis un exemple ci-dessous (la liste des règles de mise en forme ne m'a pas permis de le placer le plus proche.) Je suppose que ce n'est pas 100% nécessaire car il peut être simulé en perturbant la sortie de la fonction manuellement, mais l'avoir en entrée me donne une agréable sensation de chaleur.
  5. Entièrement écrit en Python. Si absolument, positivement besoins être écrit en C alors je suppose que peut être fait, mais je voudrais prendre un 20% plus lent fonction écrite en python sur le plus rapide en C, juste à cause de la coordination du projet de maux de tête à l'aide de deux langues différentes. Oui, c'est une dérobade, mais c'est une liste de souhaits ici.

"Perturbée" de hachage exemple, où la valeur de hachage est changé radicalement par une petite valeur entière n

def perturb_hash(key,n):
    return hash((key,n))

Enfin, si vous êtes curieux de savoir ce que le diable, je suis en train de faire que j'ai besoin d'un tel spécifique de la fonction de hachage, je suis en train de faire une réécriture complète de la pybloom module afin d'améliorer ses performances considérablement. J'ai réussi à l' (il se situe maintenant à environ 4x plus rapide et consomme environ 50% de l'espace), mais j'ai remarqué que, parfois, si le filtre a obtenu assez grand, il était soudain de dopage dans le taux de faux positifs. J'ai réalisé que c'était à cause de la fonction de hachage n'était pas aborder assez de bits. 32 bits ne s'adresse qu'à 4 milliards de bits (vous l'esprit, le filtre des adresses de bits et non d'octets) et certains filtres que j'utilise pour les données de la génomique du double ou plus (donc 34 bits minimum.)

Merci!

  • Il n'y a rien de mal avec hash(s) * 2**32 + hash(s+s)? Si hash est "assez bon", alors que c'est "assez bon", n'est-ce pas? En supposant que hash(s+s) porte pas discernable rapport à hash(s), puis vous obtenez votre avalanche dans tous les bits de sortie. Et si ce n'est pas assez rapide en raison de l'allocation de mémoire, vous pouvez coder en C pour effet d'appliquer l'algorithme de hachage à s+s, mais sans réellement effectuer la concaténation de chaîne.
  • Donc, en d'autres termes, hash(s)<<32 + hash(s+s). Je vais donner un coup de feu - merci pour l'idée!
InformationsquelleAutor eblume | 2011-03-23
  1. 22

    Prendre un coup d'oeil à la 128-bit de MurmurHash3. Le l'algorithme de la page comprend certains chiffres de la performance. Devrait être possible de porter ce Python, pure ou comme une extension de do. (Mis à jour l'auteur recommande d'utiliser le 128-bit et d'en jeter les morceaux que vous n'avez pas besoin).

    Si MurmurHash2 64 bits qui fonctionne pour vous, il est un Python de mise en œuvre (C extension) dans le pyfasthash paquet, qui comprend quelques autres non-hachage cryptographique variantes, si certains d'entre eux offrent seulement 32 bits de sortie.

    Mise à jour j'ai fait une rapide wrapper Python pour le Murmur3 fonction de hachage. Projet Github est ici et vous pouvez le trouver sur Python Package Index; il a juste besoin d'un compilateur C++ pour construire; pas de Boost nécessaire.

    Exemple d'utilisation et le calendrier de comparaison:

    import murmur3
import timeit

# without seed
print murmur3.murmur3_x86_64('samplebias')
# with seed value
print murmur3.murmur3_x86_64('samplebias', 123)

# timing comparison with str __hash__
t = timeit.Timer("murmur3.murmur3_x86_64('hello')", "import murmur3")
print 'murmur3:', t.timeit()

t = timeit.Timer("str.__hash__('hello')")
print 'str.__hash__:', t.timeit()

    De sortie:

    15662901497824584782
7997834649920664675
murmur3: 0.264422178268
str.__hash__: 0.219163894653
    • Tu sais, j'avais vu ce module, mais ne pouvais pas le faire pour compiler en raison du manque de C++ python_boost bibliothèque (ou était-ce boost_python?). Je vais prendre un autre regard sur elle. Je vais vous laisser savoir comment ça se passe merci!
    • Yep, il nécessite de Stimuler Python. Sur Ubuntu il peut être installé avec sudo apt-get install libboost-python-dev. J'ai construit un package dans mon PPA comme un exemple.
    • Malheureusement Ubuntu système de gestion de paquets est encore de retour avec la version 2.6 de python, donc j'ai dû l'installer 2,7 sur le côté. Je pourrais être incroyablement dense, mais il semble comme Boost Python est un mal difficile manuel d'installation. Des conseils à donner?
    • Yep, j'ai aussi fait un test de performance sur la relance de-wrapper murmur2 et a constaté qu'il manque, j'ai donc créé mon propre wrapper autour de murmur3. Vérifier la mise à jour ci-dessus. Cela devrait vous aller. 🙂
    • C'est assez fantastique, merci beaucoup! J'ai une question cependant - platform.cpp a quelques mentions de l'affinité du processeur en elle. Le code qui va exécuter la fonction de hachage est déjà hautement parallélisé - j'espère que ne sera pas causer des problèmes avec ce forfait?
    • Le SetAffinity fonction n'est pas appelée dans le murmur3 code, et platform.cpp est-il juste pour être complet.
    • Je ne rentrerai pas pour tester ce jusqu'à demain, mais je suis sûr que c'est la bonne façon de faire. Merci encore!
    • Dans mon cas d'utilisation, dans laquelle je suis toujours à la spécification d'une "graine" de la valeur (alias le "perturber" la valeur que je l'ai mentionné dans ma question initiale), murmur3 implémenté en C++ surpasse python de hachage((clé,n)) de plus de 10%. C'est certainement le chemin à parcourir. Merci beaucoup!
    • Génial d'entendre cela fonctionne pour vous!

    InformationsquelleAutor samplebias
  2. 3

    Utiliser les hash() fonction. Cette fonction, au moins sur la machine que je suis en développement (avec
    python 2.7, et un processeur 64 bits) produit un nombre entier qui correspond à l'intérieur de 32 bits - pas assez grand pour
    mes fins.

    Ce n'est pas vrai. Le construit en fonction de hachage va générer une version 64 bits de hachage sur un système 64 bits.

    C'est le python str fonction de hachage à partir de Objects/stringobject.c (version de Python 2.7):

    static long
string_hash(PyStringObject *a)
{
    register Py_ssize_t len;
    register unsigned char *p;
    register long x;      /* Notice the 64-bit hash, at least on a 64-bit system */

    if (a->ob_shash != -1)
    return a->ob_shash;
    len = Py_SIZE(a);
    p = (unsigned char *) a->ob_sval;
    x = *p << 7;
    while (--len >= 0)
        x = (1000003*x) ^ *p++;
    x ^= Py_SIZE(a);
    if (x == -1)
        x = -2;
    a->ob_shash = x;
    return x;
}
    • Un autre problème avec les haut- hash() fonction de hachage de la randomisation dans Python 3.3. Si la floraison filtre doit être en mesure d'être écrites sur le disque, puis le haut- hash() fonction ne peut pas être utilisé.
    • Aussi, les implémentations de python sur les plates-formes cloud comme Heroku et GAE sera de retour des valeurs différentes pour hash() sur différentes instances il est donc inutile de tout ce qui doit être partagée entre deux ou plusieurs "machines" (dynamomètres dans le cas de heroku)
    InformationsquelleAutor Saish
  3. 2

    "strings": je suis en supposant que vous souhaitez hachage Python 2.x str objets et/ou Python3.x bytes et/ou bytearray objets.

    Cela pourrait violer votre première contrainte, mais: pensez à utiliser quelque chose comme 

    (zlib.adler32(strg, perturber) << N) ^ hash(strg)

    pour obtenir une (32+N) bits de hachage.

    • Vous avez raison de supposer que je suis de hachage str objets - je vais regarder dans cet extrait de code, merci, mais vous avez raison, je doute personnellement qu'il est cohérent d'entropie pour chaque bit de sortie ici. Merci bien!
    InformationsquelleAutor John Machin
  4. 0

    Si vous pouvez utiliser Python 3.2, le résultat du hachage sur Windows 64 bits est maintenant une valeur de 64 bits.

    • J'ai été à l'aide de Python 2.7, mais si la valeur de hachage de la largeur dans le 3.moteur de x est certainement, toujours plus large, c'est peut-être assez pour me faire basculer. Merci!
    • La version 64 bits de hachage sur Windows 64 bits est une amélioration en 3.2. 64-bit Linux ont toujours eu une version 64 bits de valeur de hachage. 32-bit versions de Python (Linux et Windows) ne possède qu'un 32 bits valeur de hachage.
    InformationsquelleAutor casevh