散列数值向量的方法？

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

我很感兴趣，这是因为我在一个算法，将有利于撰写的论文从任何以前的工作类似的哈希。特别是，如果有关于像这样的散列算法的碰撞属性的任何知识，这将是非常好的。

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

澄清

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

想要的答案就像一组常数，可证明这样的散列效果特别好 - 类似于乘法器和模数，其作用比其他伪随机数生成器更好。已知例如，线性同余伪随机发生器的一些常数选择给出最佳周期长度并且具有易于计算的模数。也许有人已经做了研究，表明在矢量哈希中的一组乘法常数以及模常数可以减少在附近的整数向量中碰撞的机会。

来源

2008-11-12 Tyler

您对输入值的分布有何认识或假设？你的例子看起来好像都小于1000. – 2008-11-12 06:47:21

既然目标是找到一篇论文的参考文献，他们所做的任何假设都可能是正确的。顺便说一下，这个例子中的组合常数并不是输入，而是算法中的常量。在这个例子中，我没有指定任何实际的输入值。 – Tyler 2008-11-12 08:10:09

+20

您是否考虑过使用以下一种或多种通用哈希函数：http：//www.partow.net/programming/hashfunctions/index.html它们非常快速且高效。 – 2011-01-23 10:12:50

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

最简单的实验是散列英语词典，比较你有多少碰撞对算法A对算法B.

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

当你能够做到这一点后，你可以使用模拟退火或类似的技术来找到“神奇数字”，这对你来说效果很好。在我的工作中，对于给定的词汇表和有限的散列大小，我们可以通过改变“幻数”使通用算法适用于多种人类语言。

来源

2008-11-12 08:42:23

根据常量的大小，我不得不说，输入向量中的混沌程度会对结果产生影响。然而，你的帖子的快速定性分析会建议你有一个良好的开端：

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

出于好奇，为什么不直接使用现有的整数哈希算法，并对结果执行一些有趣的数学？

来源

2008-11-12 07:28:43 Rob

我正在写一篇关于算法的论文，并且很想找到关于这个主题的参考文献，所以我不能说“STL使用这个实现，所以它一定很好”。 – Tyler 2008-11-12 08:07:08

虽然我可能完全误解了你，但也许把一个矢量当作一个字节流并做一些知道它的散列是个好主意，例如SHA1或MD5。

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

来源

2008-11-12 07:34:49 Drakosha

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

这确实什么都没有尽管...可能没有太大的帮助。

来源

2008-11-12 08:13:50 Claudiu

散列数值向量的方法？

回答

相关问题