funciones hash generador de familia en python

Question

Estoy buscando un generador de funciones de funciones hash que podría generar una familia de funciones hash dado un conjunto de parámetros. No he encontrado ningún generador de ese tipo hasta el momento. ¿Hay alguna manera de hacerlo con el paquete hashlib?

Por ejemplo me gustaría hacer algo como:

h1 = hash_function(1) 
h2 = hash_function(2) 
... 

y h1 y h2 habría diferentes funciones hash.

Para aquellos de ustedes que puedan saber sobre esto, estoy tratando de implementar un algoritmo de min-hash en un conjunto de datos muy grande.

Básicamente, tengo un gran conjunto de características (100 millones a 1 mil millones) para un documento dado, y necesito crear de 1000 a 10000 permutaciones aleatorias diferentes para este conjunto de características.

NO deseo de construir las permutaciones aleatorias de forma explícita por lo que la técnica que le gustaría utilizar en el siguiente:

1. generar una función hash h y considerar que durante dos índices r y s
2. r aparece antes del s en la permutación si es h(r) < h(s) y lo hace para 100 a 1000 funciones hash diferentes.

¿Hay alguna biblioteca conocida que me haya pasado por alto? ¿O cualquier forma estándar de generar familias de funciones hash con python de las que puedas estar al tanto?

Answer 1

que acababa de hacer algo como (si es que no es necesario hilo de seguridad - no es difícil de alterar Si necesita hilo de seguridad - y asumiendo una versión de 32 bits de Python):

import random 

_memomask = {} 

def hash_function(n): 
    mask = _memomask.get(n) 
    if mask is None: 
    random.seed(n) 
    mask = _memomask[n] = random.getrandbits(32) 
    def myhash(x): 
    return hash(x)^mask 
    return myhash 

Answer 2

Debería considerar el uso del hashing universal. Mi respuesta y el código se pueden encontrar aquí: https://stackoverflow.com/a/25104050/207661

Answer 3

Como se mencionó anteriormente, puede utilizar hashing universal para minhash. Por ejemplo:

import random 



def minhash(): 
    d1 = set(random.randint(0, 2000) for _ in range(1000)) 
    d2 = set(random.randint(0, 2000) for _ in range(1000)) 
    jacc_sim = len(d1.intersection(d2))/len(d1.union(d2)) 
    print("jaccard similarity: {}".format(jacc_sim)) 

    N_HASHES = 200 
    hash_funcs = [] 
    for i in range(N_HASHES): 
     hash_funcs.append(universal_hashing()) 

    m1 = [min([h(e) for e in d1]) for h in hash_funcs] 
    m2 = [min([h(e) for e in d2]) for h in hash_funcs] 
    minhash_sim = sum(int(m1[i] == m2[i]) for i in range(N_HASHES))/N_HASHES 
    print("min-hash similarity: {}".format(minhash_sim)) 



def universal_hashing(): 
    def rand_prime(): 
     while True: 
      p = random.randrange(2 ** 32, 2 ** 34, 2) 
      if all(p % n != 0 for n in range(3, int((p ** 0.5) + 1), 2)): 
       return p 
    m = 2 ** 32 - 1 
    p = rand_prime() 
    a = random.randint(0, p) 
    if a % 2 == 0: 
     a += 1 
    b = random.randint(0, p) 
    def h(x): 
     return ((a * x + b) % p) % m 
    return h 

Reference