Генератор семейства хэш-функций в Python

Question

Я ищу генератор семейства хеш-функций, который может генерировать семейство хеш-функций с учетом набора параметров. Я не нашел такого генератора до сих пор. Есть ли способ сделать это с пакетом hashlib?

Например, я хотел бы сделать что-то вроде:

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

и h1 и h2 будут разными хеш-функциями.

Для тех из вас, кто может знать об этом, я пытаюсь реализовать алгоритм мини-хеширования для очень большого набора данных.

По сути, у меня есть очень большой набор функций (от 100 миллионов до 1 миллиарда) для данного документа, и мне нужно создать 1000-10000 различных случайных перестановок для этого набора функций.

Я НЕ хочу явно строить случайные перестановки, поэтому я хотел бы использовать следующую технику:

1. сгенерируйте хеш-функцию h и учтите, что для двух индексов r и s
2. r появляется перед s в перестановке, если h(r) < h(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

Как уже упоминалось выше, вы можете использовать универсальное хеширование для 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

Ссылка

Answer 3

Вы должны рассмотреть возможность использования универсального хеширования. Мой ответ и код можно найти здесь: https://stackoverflow.com/a/25104050/207661