14

是否有任何已知的哈希算法可以输入一个 int 向量并输出一个与内积类似的单个 int？

换句话说，我正在考虑在 C++ 中可能看起来像这样的哈希算法：

// For simplicity, I'm not worrying about overflow, and assuming |v| < 7.
int HashVector(const vector<int>& v) {
  const int N = kSomethingBig;
  const int w[] = {234, 739, 934, 23, 828, 194};  // Carefully chosen constants.
  int result = 0;
  for (int i = 0; i < v.size(); ++i) result = (result + w[i] * v[i]) % N;
  return result;
}

我对此感兴趣，因为我正在写一篇关于算法的论文，该算法将受益于以前关于类似哈希的任何工作。特别是，如果对这样的哈希算法的冲突属性有任何了解，那就太好了。

我感兴趣的算法将散列整数向量，但浮点向量的一些东西也很酷。

澄清

哈希旨在用于哈希表中以进行快速键/值查找。这里没有安全问题。

所需的答案类似于一组常数，可证明对于这样的哈希特别有效 - 类似于乘数和模数，它比其他作为伪随机数生成器的效果更好。

例如，已知线性同余伪随机发生器的一些常数选择可提供最佳周期长度并具有易于计算的模数。也许有人做过研究，表明向量散列中的一组乘法常数以及一个模常数可以减少附近整数向量之间发生冲突的机会。

4

4 回答 4

3

我做了一些（未发表的，实用的）实验来测试各种字符串哈希算法。（事实证明，Java 的默认字符串哈希函数很糟糕。）

一个简单的实验是对英语词典进行哈希处理，然后比较算法 A 与算法 B 的碰撞次数。

您可以构建一个类似的实验：随机生成 $BIG_NUMBER 个长度为 7 或更短的可能向量。在算法 A 上散列它们，在算法 B 上散列它们，然后比较冲突的数量和严重程度。

在你能够做到这一点之后，你可以使用模拟退火或类似的技术来找到对你来说表现良好的“幻数”。在我的工作中，对于给定的感兴趣的词汇和严格限制的哈希大小，我们能够通过改变“幻数”使通用算法适用于几种人类语言。

于 2008-11-12T08:42:23.113 回答
2

根据常数的大小，我不得不说输入向量中的混乱程度会对结果产生影响。但是，对您的帖子进行快速定性分析表明您有一个良好的开端：

  • 您的输入相乘，因此增加了每次迭代相似输入值之间的分离程度（例如，65 + 66 远小于 65 * 66），这很好。
  • 它是确定性的，除非你的向量应该被认为是一个集合而不是一个序列。为清楚起见，v = { 23, 30, 37 } 是否应该不同于 v = { 30, 23, 37 }？
  • 分布的均匀性将根据 v 中输入值的范围和混乱度而变化。但是，对于广义整数散列算法也是如此。

出于好奇，为什么不直接使用现有的整数散列算法并对结果进行一些有趣的数学运算呢？

于 2008-11-12T07:28:43.730 回答
1

Python 曾经以这种方式散列元组（来源）：

class tuple:
    def __hash__(self):
        value = 0x345678
        for item in self:
            value = c_mul(1000003, value) ^ hash(item)
        value = value ^ len(self)
        if value == -1:
            value = -2
        return value

在你的情况下，item总是一个整数，它使用这个算法：

class int:
    def __hash__(self):
        value = self
        if value == -1:
            value == -2
        return value

不过，这确实与内部产品无关......所以也许它没有太大帮助。

于 2008-11-12T08:13:50.053 回答
0

虽然我可能完全误解了你，但将向量视为字节流并对其进行一些已知的哈希处理可能是个好主意，即SHA1或MD5。

澄清一下，众所周知，这些散列具有良好的散列属性，我相信没有理由重新发明自行车并实施新的散列。另一种可能性是使用已知的 CRC 算法。

于 2008-11-12T07:34:49.320 回答