是否有任何已知的哈希算法输入int的向量并输出一个类似于内积的int?
换句话说,我正在考虑在C++中可能看起来像这样的哈希算法:
// For simplicity, I'm not worrying about overflow, and assuming |v| < 7. int HashVector(const vector& 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; }
我对此感兴趣,因为我正在撰写一篇关于算法的论文,该算法将受益于之前任何类似哈希的工作.特别是,如果有关于这样的散列算法的碰撞属性的任何已知信息,那将是很好的.
我感兴趣的算法会散列整数向量,但浮点向量的东西也很酷.
澄清
该哈希旨在用于哈希表中以进行快速键/值查找.这里没有安全问题.
期望的答案类似于一组常量,这些常量对于像这样的散列特别有效 - 类似于乘法器和模数,其作为伪随机数生成器比其他更好.
例如,已知线性同余伪随机发生器的一些常数选择可给出最佳循环长度并具有易于计算的模数.也许有人做过研究,表明在向量散列中有一组乘法常数和模数常量可以减少邻近整数向量之间碰撞的机会.