hashing de cadena rápido, de ancho grande y no criptográfico en python

plotly title

Question

Necesito una función de hashing de cadena de alto rendimiento en python que produzca enteros con al menos 34 bits de salida (64 bits tienen sentido, pero 32 es muy pocos). Hay varias otras preguntas como esta sobre Stack Overflow, pero de esas respuestas aceptadas / con votos arriba que pude encontrar cayeron en una de las pocas categorías, que no se aplican (por la razón dada).

• Use la función incorporada hash() . Esta función, al menos en la máquina en la que estoy desarrollando (con python 2.7 y una CPU de 64 bits) produce un entero que se ajusta a 32 bits, no lo suficientemente grande para mis propósitos.
• Use hashlib. hashlib proporciona rutinas criptográficas hash, que son mucho más lentas de lo que deben ser para fines no criptográficos. Encuentro esto evidente, pero si necesita puntos de referencia y citas para convencerlo de este hecho, entonces puedo proporcionarlo.
• Use la función de string.__hash__() como prototipo para escribir su propia función. Sospecho que este será el camino correcto, excepto que la eficiencia de esta función en particular radica en su uso de la función c_mul, que envuelve alrededor de 32 bits, una vez más, ¡demasiado pequeña para mi uso! Muy frustrante, ¡está tan cerca de ser perfecto!

Una solución ideal tendría las siguientes propiedades, en un orden de importancia relativo y suelto.

1. Tener un rango de salida que se extienda por lo menos a 34 bits de largo, probablemente 64 bits, mientras se conservan propiedades de avalancha consistentes sobre todos los bits. (Concatenando algoritmos de 32 bits tiende a violar las propiedades de avalancha, al menos con mis tontos ejemplos).
2. Portátil. Dada la misma cadena de entrada en dos máquinas diferentes, debería obtener el mismo resultado las dos veces. Estos valores se almacenarán en un archivo para su posterior reutilización.
3. Alto rendimiento. Cuanto más rápido mejor, ya que esta función se llamará aproximadamente 20 mil millones de veces durante la ejecución del programa que estoy ejecutando (es el código de rendimiento crítico en este momento). No necesita escribirse en C, realmente solo necesita superar a md5 (en algún lugar del ámbito del hash incorporado () para cadenas).
4. Acepte una ''perturbación'' (¿cuál es la mejor palabra para usar aquí?) Entero como entrada para modificar la salida. Pongo un ejemplo a continuación (las reglas de formato de lista no me permiten ubicarlo más cerca.) Supongo que esto no es 100% necesario ya que puede simularse perturbando la salida de la función manualmente, pero tenerlo como entrada me da un agradable y cálido sentimiento.
5. Escrito completamente en Python. Si es absolutamente necesario escribirlo en C, entonces supongo que se puede hacer, pero tomaría una función un 20% más lenta escrita en python sobre la más rápida en C, solo debido a la coordinación del proyecto, el dolor de cabeza de usar dos idiomas diferentes . Sí, esto es una salida de escape, pero esta es una lista de deseos aquí.

Ejemplo de hash ''Perturbed'', donde el valor de hash se cambia drásticamente por un pequeño valor entero n

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

Finalmente, si tiene curiosidad sobre qué diablos estoy haciendo, necesito una función hash específica, estoy haciendo una relectura completa del módulo pybloom para mejorar su rendimiento considerablemente. Logré eso (ahora corre aproximadamente 4 veces más rápido y usa aproximadamente el 50% del espacio), pero me di cuenta de que, a veces, si el filtro aumentaba lo suficiente, de repente aumentaba en tasas de falsos positivos. Me di cuenta de que era porque la función hash no estaba dirigiendo suficientes bits. 32 bits solo pueden direccionar 4 mil millones de bits (fíjese usted, el filtro trata los bits y no los bytes) y algunos de los filtros que estoy usando para los datos genómicos doblan esa o más (por lo tanto, un mínimo de 34 bits).

¡Gracias!

Answer 1

Use la función incorporada hash (). Esta función, al menos en la máquina en la que estoy desarrollando (con python 2.7 y una CPU de 64 bits) produce un entero que se ajusta a 32 bits, no lo suficientemente grande para mis propósitos.

Eso no es cierto. La función hash incorporada generará un hash de 64 bits en un sistema de 64 bits.

Esta es la función de hash python str de Objects/stringobject.c (Python versión 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 2

"cadenas": presumo que desea hash objetos Python 2.x str y / o bytes Python3.x y / o objetos bytearray .

Esto puede violar su primera restricción, pero: considere usar algo como

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

para obtener un hash (32 + N) -bit.

Answer 3

Eche un vistazo a la variante de 128 bits de MurmurHash3 . La página del algoritmo incluye algunos números de rendimiento. Debería ser posible llevar esto a Python, puro o como una extensión C. ( Actualizado, el autor recomienda usar la variante de 128 bits y tirar los bits que no necesita).

Si MurmurHash2 de 64 bits funciona para usted, hay una implementación de Python (extensión C) en el paquete pyfasthash , que incluye algunas otras variantes de hash no criptográficas, aunque algunas de ellas solo ofrecen salida de 32 bits.

Actualización Hice una capa rápida de Python para la función hash Murmur3. El proyecto Github está aquí y también lo puedes encontrar en Python Package Index ; solo necesita un compilador de C ++ para compilar; no se requiere Boost.

Ejemplo de uso y comparación de tiempo:

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()

Salida:

15662901497824584782
7997834649920664675
murmur3: 0.264422178268
str.__hash__: 0.219163894653

Answer 4

Si puede usar Python 3.2, el resultado hash en Windows de 64 bits ahora tiene un valor de 64 bits.