我正在寻找一个将整数的多重集映射到整数的函数，希望具有一些像成对独立性这样的保证。
理想情况下，内存使用应该是恒定的，并且在插入/删除后哈希值可以在O(1)时间内更新。(这禁止了执行诸如排序整数并使用像h(x) = h_1(x_1, h_2(x_2, h_3(x_3, x_4)))这样的哈希函数的操作。)
XOR哈希在这里无效，因为h({1,1,2}) = h({2})
如果底层哈希函数具有像n-独立性这样强的保证，那么将哈希相乘取模素数可能会奏效。
6个回答
8
我在cstheory.stackexchange.com上提出了同样的问题，并得到了一个好答案：
- jonderry
4
我同意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。
- valyala
5
2这在实践中可能有效，但很容易使碰撞的几率相当大。考虑以下情况，如果每个集合中有2^16个副本，则{1,1，...，1}与{2,2，...，2}发生碰撞的可能性是多少。通过对质数取模可以得到帮助。尽管如此，仍然没有理论保证，这也是我感到好奇的另一件事（是否能够获得关于哈希函数分布的良好理论保证）。 - jonderry
1反转位并不能改善输出分布。
实际上，如果大多数输入值都接近于零，正如我所说的那样，它可以以最佳方式进行改善。 - Dzmitry Lazerka
"...高位比特将会丢失"
在进行SUM时不会丢失任何比特。您在最后一句话中已经证明了这一点 :) - Dzmitry Lazerka
但是你的提议也很好，我认为它对于输入数据全部为偶数或奇数（或更大的2的幂）的情况是容忍的。 - Dzmitry Lazerka
1但是，如果输入数据没有这种模式，reverse-bits 是一般哈希表的最佳函数。这是因为输入数字的较低位的变化会导致哈希放置在哈希表的不同桶中。而您的建议并未区分输入数据是否接近零（通常情况下是这样）。 - Dzmitry Lazerka
2
反转位
例如，00001011 变成 11010000。然后，只需对所有反转的元素求和。
如果我们需要在插入/删除操作上达到O(1)的时间复杂度，通常的SUM函数就可以实现这一点（这也是Java中集合Set的实现方式），尽管对于小整数集合而言分布不够均匀。
假设我们的集合不是均匀分布的（通常不会如此），我们需要一个映射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
}
但是我们的多集合哈希值不会均匀，尽管比简单的SUM好得多。
- Dzmitry Lazerka
1
我曾经问过一个类似的问题， "排列的好哈希函数是什么？"，并得到了一个对我的用例非常有效的哈希函数，我的工作代码中很少有碰撞。它可能也适合你。计算类似于这样的东西：
// initialize this->hash with 1
unsigned int hash = 1;
void add(int x) {
this->hash *= (1779033703 + 2*x);
}
无论何时，只要你添加一个数字
x，就使用上述公式更新哈希码。值的顺序并不重要，你总是会得到相同的哈希值。当你想要合并两个集合时，只需将哈希值相乘即可。
唯一我不确定是否可能以O(1)时间删除一个值。
- martinus
5
1这与我在问题中提出的建议类似。您可以通过乘以要删除元素的哈希的模反元素来进行删除。这需要保持集合的哈希模质数（并确保元素的哈希值非零）。我对这种方法的问题是如何获得理论保证。 - jonderry
这个哈希函数是否可以修改以支持顺序依赖性？即
[a，b，c] 和 [b，c，a] 产生不同的哈希值？ - jeffreyveon@jeffreyveon 如果你需要有序性，那么你可以使用任何哈希。 - martinus
我有一个数字列表。列表中的每个数字可以独立地进行哈希处理，但是我如何将这些哈希组合成一个单一的哈希，以表示整个列表？我采取的一种方法是使用索引位置作为哈希更新的一部分，就像这样：
this->hash *= (1779033703 + 2 * x * i);，其中 i 是元素 x 在列表中的索引。 - jeffreyveon你可以使用boost::hash_combine之类的东西，但我不认为有使用特殊工具的理由？为什么不直接使用例如murmurhash来哈希整个数据块呢？ - martinus
0
这里应该使用Min-hashing。应用置换，维护一个小型多重集合包含n个最小元素，然后选择最大的元素。
具体地说，这是一种在O(1)时间和空间内工作的简单方法。您需要类似于优先队列的东西，但不要使其与初始值之间的链接太明显。因此，根据一些精心制定的密钥对优先队列进行排序，这等效于在正常排序顺序的排列上运行优先队列。使队列跟踪多重性，以便所选元素也形成一个多重集合。
话虽如此，我不确定这是否分散得足够好（并且运行多个置换可能会变得昂贵），因此最好建立在Bradley的答案基础上。这是一个调整，以便重复的元素不会被取消：
xor(int_hash(x_n, multiplicity_n) foreach n)
- Tobu
-1
Knuth在TAoCP中提到了这一点，这与哪些整数哈希函数接受整数哈希键是好的？几乎相同。
对于您的情况，将您的多集合转换为单个整数，然后执行链接帖子中描述的哈希可能是您想要做的。将集合转换为数字很简单；数字的连接将会做到。
有关Knuth方法的更多信息，请搜索“Knuth的乘法方法”
-tjw
- Travis Webb
3
你不能简单地进行串联，因为集合中整数的顺序不应影响哈希值。 - jonderry
此外，字符串拼接也不会很好地工作，因为 h({12, 3}) == h({1, 23})。 - Dzmitry Lazerka
只有在对整数进行排序后，串联才能起作用，而问题禁止这样做。 - ma11hew28
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接