创建返回s的随机哈希函数

Question

考虑以下代码：

def xorHash(n):
    mask = random.getrandbits(32)
    def xorIt(x):
        return (hash(x) ^ mask) % n
    return xorIt  

这将返回一个随机哈希函数，该函数将元素映射到{0,1，…，rng-1}中的一个数字。在

我想创建一个随机散列函数，它将每个元素精确映射到{0,1，…，rng-1}中的k个元素（不重复）。上面的例子适用于k=1。在

What is the most efficient way of creating a random hash function which returns a k-sized random subset of {0,1,...,rng-1}?

Answer 1

使用数据的普通整数值随机化散列为RNG设定种子，并使用它从所需范围中提取随机样本：

def generate_randomized_set_valued_hash_function(n, k):
    hashfunc = generate_randomized_hash_function()
    def set_valued_hashfunc(x):
        rng = random.Random(hashfunc(x))
        return set(rng.sample(xrange(n), k))
    return set_valued_hashfunc

您选择什么RNG和什么整型值散列函数将取决于集值散列函数的强度和速度。在