python之创建返回集合的随机哈希函数

考虑以下代码:

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}?

请您参考如下方法:

使用数据的普通整数值随机散列作为 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 和整数值哈希函数将取决于您需要集值哈希函数的强度和速度。