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

Question

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 beaucoup 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 l' 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 la cohérence de l'avalanche de propriétés sur tous les bits. (Concaténation de 32 bits hachages tend à violer l'avalanche propriétés, au moins avec mon muets sont 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 besoin d'ê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 un souhait de la liste 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!

Answer 1

Jetez un oeil à la 128-bit de MurmurHash3. 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. (Mise à jour de 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 ainsi, 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()

Sortie:

15662901497824584782
7997834649920664675
murmur3: 0.264422178268
str.__hash__: 0.219163894653

Answer 2

Utilisez la fonction de hachage () intégrée. Cette fonction, au moins sur la machine pour laquelle je développe (avec python 2.7 et un processeur 64 bits) produit un entier qui tient dans les 32 bits - pas assez grand pour mes besoins.

Ce n'est pas vrai. La fonction de hachage intégrée générera un hachage 64 bits sur un système 64 bits.

Il s'agit de la fonction de hachage python str de Objects/stringobject.c (Python version 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;
}
 

Answer 3

"chaînes": je suppose que vous souhaitez hacher des objets Python 2.x str et / ou Python3.x bytes et / ou bytearray objets.

Cela peut violer votre première contrainte, mais: envisagez d'utiliser quelque chose comme

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

pour obtenir un hachage (32 + N) bits.

Answer 4

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