散列数字向量的方法？

Question

是否有任何已知的哈希算法输入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;
}

我对此感兴趣,因为我正在撰写一篇关于算法的论文,该算法将受益于之前任何类似哈希的工作.特别是,如果有关于这样的散列算法的碰撞属性的任何已知信息,那将是很好的.

我感兴趣的算法会散列整数向量,但浮点向量的东西也很酷.

澄清

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

期望的答案类似于一组常量,这些常量对于像这样的散列特别有效 - 类似于乘法器和模数,其作为伪随机数生成器比其他更好.

例如,已知线性同余伪随机发生器的一些常数选择可给出最佳循环长度并具有易于计算的模数.也许有人做过研究,表明在向量散列中有一组乘法常数和模数常量可以减少邻近整数向量之间碰撞的机会.

Answer 1

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

简单的实验是对英语字典进行哈希处理，并比较算法 A 和算法 B 的冲突次数。

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

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