如何对数字向量进行哈希处理？

Question

是否有已知的哈希算法可将整数向量作为输入并输出单个整数，类似于内积的工作方式？

换句话说，我在考虑一种哈希算法，在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;
}

我对此很感兴趣，因为我正在撰写一篇关于算法的论文，需要借鉴类似哈希的先前工作。特别是，如果已知这样一个哈希算法的碰撞属性，那就太棒了。

我感兴趣的算法将对整数向量进行哈希，但是对浮点向量进行哈希也很酷。

澄清

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

期望的答案类似于一组常数，可以证明在这样的哈希中特别有效 - 类比于乘法器和模数，它们作为伪随机数生成器比其他选择更好。

例如，某些线性同余伪随机数生成器的常数选择已知可提供最佳周期长度并具有易于计算的模数。 也许有人已经研究表明，在向量哈希中使用某个乘法常数集合以及一个模数常数，可以减少相邻整数向量之间发生碰撞的机会。

- Tyler

---

你对输入值的分布了解或假设了什么？你的例子看起来都小于1000。 - Martin v. Löwis

由于目标是为论文寻找参考文献，所以他们做出的任何假设可能都可以接受。顺便说一下，在示例中编造的常量并不是输入，而是算法中的常量。我没有在那个示例中指定任何实际的输入值。 - Tyler

你考虑过使用以下通用哈希函数之一吗：http://www.partow.net/programming/hashfunctions/index.html。它们非常快速高效。 - Matthieu N.

Answer 1

我进行了一些（未公开的实际）实验，测试了各种字符串哈希算法。(结果发现Java默认的字符串哈希函数很差。)

一个简单的实验是对英语词典进行哈希，并比较算法A和算法B之间的冲突次数。

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

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

- Patrick McKenzie

---

不错的想法，Patrick。这听起来是一种非常实用和有效的找到实际算法的方法。我仍然对此问题上以前已经存在的出版物很感兴趣。 - Tyler

Answer 2

根据常量的大小，我认为输入向量中混沌的程度将对结果产生影响。然而，对您帖子的快速定性分析表明，您有一个良好的开端： - 您的输入被乘起来，因此增加了每次迭代中相似输入值之间的分离程度（例如，65 + 66比65 * 66小得多），这是很好的。 - 它是确定性的，除非您的向量应该被视为集合而不是序列。为了清楚，v = { 23, 30, 37 }是否应该与v = { 30, 23, 37 }不同？ - 分布的均匀性将根据v中输入值的范围和混沌程度而变化。然而，这也适用于一般的整数哈希算法。

出于好奇，为什么不只使用现有的整数哈希算法并对结果进行一些有趣的数学操作呢？

- Rob

---

我正在撰写一篇关于算法的论文，希望能找到有关这个主题的参考资料，这样我就不能只说“STL使用这种实现方式，所以它一定很好”。 - Tyler

Answer 3

Python曾经以这种方式哈希元组（source）：

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

这与内积无关，所以可能帮不上什么忙。

- Claudiu

Answer 4

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

只是为了澄清，这些哈希已知具有良好的哈希特性，我相信没有理由重新发明轮子并实现新的哈希。另一个可能性是使用已知的 CRC 算法。

- Drakosha

---

谢谢，但SHA1和MD5是为安全而设计的，而不是为避免碰撞而设计的。它们与内积的工作方式也非常不同。 - Tyler