3

最好是快速的方法。这个N = 2^b案子很简单。为此，首先我要弄清楚我选择的类型中有多少位：

typedef unsigned int type;
size_t size = sizeof(type) * 8;

然后我将执行适当数量的位右移以产生高位的哈希键b。

type input = 0x657;
unsigned char b = 4;
unsigned char hash = input >> (size - b);

但如果我想要N = 3呢？或任何其他非 2 的幂？假设 my Nwill 总是适合一个unsigned char（所以它最多是 256），那么散列一些最快的方法是input什么？在保持桶的范围差异不超过 +/- 1 的同时，还保留 的高位的顺序input，就像上面的函数一样。

4

1 回答 1

3

对于 32 位值，进行 64 位乘法运算N并保留前 32 位。（对于其他大小也是如此，尽管如果您有 64 位值，则乘法会变得更加棘手。）

这是一个基本的证明大纲。

很明显，这种映射是保序的；唯一的问题是每个桶中有多少值。现在，考虑一些桶并找到映射到该桶j的最小桶。iFor ito fall into bucketj意味着在哪里，但如果是最小的这样的值，。（否则，也会落入桶中。）Ni − j×232 = m0 ≤ m < 232i0 ≤ m < Ni−1j

现在，定义，这相当于说。通过将这两个公式相加，我们发现; 化简，我们得到和。这意味着or是映射到的最小值（取决于是否为负），这意味着存在映射到的or 或值。既然对于 any 都是如此，我们可以肯定地说只有两种桶大小，其中之一是. 我在评论（现已删除）中做出的断言离那里不远，即另一个可能的存储桶大小是.w = ⌊232∕N⌋Nw − 232 = −m' where 0 ≤ m' < NNi + Nw - j×232 - 232 = m−m'N(i+w)-(j+1)×232 = m−m'−N < m−m' < Ni + wi + w + 1j + 1m − m'ww + 1jj⌊232∕N⌋⌈232∕N⌉

上面的证明没有什么神奇之处；我可以使用任何值。但这会使精简的证明更加难以阅读。232M

于 2012-12-18T18:08:52.547 回答