代码之家 › 专栏 › 技术社区 › Tyler

散列数值向量的方法?

vector hash math algorithm

14

Tyler · 技术社区 · 17 年前

是否有任何已知的哈希算法可以输入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 回复 | 直到 17 年前

1

3

Patrick McKenzie 17 年前

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

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

2

Rob 17 年前

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

您的输入是相乘的,因此增加了每次迭代中相似输入值之间的分离度(例如,65+66比65*66小得多),这很好。
它是确定性的,除非你的向量应该被视为一个集合而不是一个序列。为了清楚起见,v={23,30,37}应该与v={30,23,37}不同吗?

出于好奇,为什么不使用现有的整数哈希算法并对结果执行一些有趣的数学运算呢?

3

1

Claudiu 17 年前

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

这与内部产品无关,不过。。。所以这可能没什么帮助。

4

0

Drakosha 17 年前

虽然我可能完全误解了你的意思,但把向量当作字节流并对其进行一些已知散列可能是个好主意。 SHA1 或 MD5

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