在Python中哈希函數族發生器

Question

我正在尋找一個哈希函數族發生器，可以生成哈希函數家族給定的一組參數。到目前爲止我還沒有找到任何這樣的發生器。 有沒有辦法做到這一點與hashlib包？

比如我想這樣做：

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

和h1和h2將不同的散列函數。

對於那些可能知道它的人，我試圖在一個非常大的數據集上實現min-hashing算法。

基本上，對於一個給定的文檔，我有一個非常大的功能集（1億到10億），我需要爲這組功能創建1000到10000個不同的隨機排列。

我不想建立隨機排列明確這樣的技術，我想在使用下列內容：

1. 生成一個散列函數h並認爲兩個索引r和s
2. r如果h(r) < h(s)在排列中出現在s之前並且爲100到1000個不同的散列函數執行該操作。

是否有任何已知的庫可能會遺漏？或者您可能知道的使用python生成哈希函數族的任何標準方法？

Answer 1

我只是這樣做（如果你不需要線程安全 - 不是很難改變，如果你確實需要線程安全 - 並假設一個32位的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

你應該考慮使用通用哈希。我的答案和代碼可以在這裏找到：https://stackoverflow.com/a/25104050/207661

Answer 3

如上所述，你可以使用通用哈希minhash。 例如：

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