algorithm - 字符串的成对独立哈希函数？

Question

许多随机算法和数据结构（例如Count-Min Sketch）需要具有成对独立属性的哈希函数。直观地说，这意味着与特定元素发生哈希冲突的概率很小，即使该元素的哈希函数的输出是已知的。

我发现了许多关于基于随机线性函数的固定长度位向量的成对独立哈希函数的描述。但是，我还没有看到任何成对独立的字符串散列函数示例。

是否有任何成对独立的字符串散列函数系列？

Answer 1

我很确定它们存在，但你的问题有一些测量理论的微妙之处。你最好问问 mathoverflow。我对这些东西很生疏，但我想我可以证明，即使它们确实存在，你实际上并不想要一个。

首先，您需要对字符串进行概率测量，并且任何此类测量都必然与任何“均匀”概念看起来非常不同。（这是一个可数集，所有可数集上的 sigma 代数只是将元素集聚集在一起，并为每个集合分配一个概率。你会希望所有的团块都是单例。）

现在，如果你只给出有限多个字符串的正概率，那么你又回到了有限的情况。所以让我们暂时忽略它并假设，对于任何 epsilon > 0，您可以找到一个概率严格在 0 和 epsilon 之间的字符串。

假设我们限制哈希函数将字符串映射到 {0,1} 的情况。

您的散列函数族也需要是无限的，并且您需要将其作为散列函数的概率空间来讨论。如果您有一组 H 具有正概率的哈希函数，则每个字符串都通过 H 的（不同）元素映射到 0 和 1。特别是，H 中没有单个元素具有正概率。所以 H 必须是不可数的，你突然遇到了困难的可表示性问题。

如果没有忘记测度论的人在这里插话，我会很高兴。

Answer 2

不是有界长度的种子和非零有界长度的输出。

这种效果的一个相当粗略的论据是，对于一个有限的散列函数 H 族，考虑一个从元素 x 到一个元组的映射 f，它为 H 中的每个 h 给出 h(x)。由于每个 h 的共域，因此 f 是有限的，存在两个字符串被 H 中的所有 h 以相同的方式映射，假设至少有两个可能的哈希值，这与成对独立相矛盾。