对于整数集合(即多个集合),什么是好的散列函数?

我在cstheory.stackexchange.com上问了同样的问题,得到了一个很好的答案:

https://cstheory.stackexchange.com/questions/3390/is-there-a-hash-function-for-a-collection-i-e-multi-set-of-integers-that-has

反转位。

例如,0000101变为11010000。然后,对所有反转的集合元素求和。

如果在insert/delete上需要O(1),那么通常的SUM就可以工作(这就是用Java实现集合的方式),尽管在小整数集合上分布不好。

如果我们的集合不是均匀分布的(通常是这样),我们需要映射N->f(N),以便f(N)对于预期的数据样本是均匀分布的。通常,数据样本比接近最大数字更接近零个数。在这种情况下,反向位散列将均匀地分布它们。

Scala中的示例:

def hash(v: Int): Int = {
        var h = v & 1
        for (i <- 1 to 31) {
                h <<= 1;
                h |= ((v >>> i) & 1)
        }
        h
}
def hash(a: Set[Int]): Int = {
        var h = 0
        for (e: Int <- a) {
                h += hash(e);
        }
        h
}

但是我们的多重集合的散列不会是一致的,尽管比简单的和要好得多。

我同意Dzmitry关于散列算术和的使用,但我建议使用一个散列函数,它对输入整数具有良好的输出分布,而不仅仅是反转整数中的位。反转位并不能改善输出分布。它甚至会恶化输出分布,因为在这种情况下,由于和溢出而丢失高阶位的概率比丢失低阶位的概率高得多。下面是一个具有良好输出分布的快速哈希函数示例: http://burtleburtle.net/bob/c/lookup3.c . 还请阅读描述哈希函数必须如何构造的论文- http://burtleburtle.net/bob/hash/evahash.html .

使用集合中每个元素的哈希值之和满足问题中的要求:

• 内存使用是恒定的。我们需要存储一个包含散列值的普通整数。当从集合中添加/删除元素时,此整数将用于哈希的O(1)更新。
• 添加新元素只需要将元素的哈希值添加到现有散列值,即操作是O(1)。
• 删除现有元素只需要从现有散列值减去元素的哈希值,即操作是O(1)。
• 集合的散列将不同,而集合的散列只因相同元素对的不同而不同。

SUM和SUB是面对整数溢出的安全操作,因为它们在 modular arithmetic ,其中,对于java中的整数,模数为2^32或2^64。

Knuth在TAoCP上提到了这个,这是 What integer hash function are good that accepts an integer hash key? .

对于您的情况,将多个集合转换为单个整数,然后执行链接post中描述的散列可能是您想要做的。把一个集合转换成一个数字是微不足道的;数字的串联就可以了。

有关Knuth方法的更多信息,请搜索“Knuth的乘法方法”

-tjw公司

最小散列应该在这里工作。应用置换,保持n个最小元素的一个小多集,选择最大的。

阐述:这是一种在O(1)时空中工作的简单方法。您需要类似于优先级队列的东西,而不需要使到初始值的链接过于明显。因此,您可以根据某个精心编制的键对优先级队列进行排序,这相当于在正常排序顺序的排列上运行优先级队列。使队列跟踪多重性,以便所选元素也形成多重集。

也就是说,我不确定这种分散是否足够好(并且运行多个排列可能会变得昂贵),所以也许可以建立在布拉德利的答案上。这里有一个调整,以便重复的元素不会取消:

xor(int_hash(x_n, multiplicity_n) foreach n)

我曾经问过类似的问题 Good hash function for permutations? “,并且得到了一个对我的用例非常有效的散列,我的工作代码中很少有冲突。也许对你也有好处。计算如下:

// initialize this->hash with 1
unsigned int hash = 1;
void add(int x) {
  this->hash *= (1779033703 + 2*x);
}

所以每当你加上一个数字 x ,使用上述公式更新哈希代码。值的顺序并不重要,您将始终获得相同的哈希值。

当你想合并两个集合时,只需乘以散列值。

我唯一不确定的是是否有可能删除O(1)中的值。