c++ - 有效地将 16 位整数哈希到 256 位空间

Question

变得更大听起来很奇怪，但这就是我正在努力做的。我想获取整个 16 位整数序列，并以统一映射到 256 位空间的方式对每个整数进行哈希处理。

这样做的原因是我试图将 16 位数字空间的子集放入 256 位布隆过滤器中，以进行快速成员资格测试。

我可以对每个整数使用一些众所周知的散列函数，但我正在寻找一种极其高效的实现(只需几条指令)，以便它在 GPU 着色器程序中运行良好。我觉得已知哈希输入仅为 16 位这一事实可以告知哈希函数是以某种方式设计的，但我没有看到解决方案。

有什么想法吗？

---

编辑

根据回复，我原来的问题令人困惑。对于那个很抱歉。我将尝试用一个更具体的例子来重申它:

我有一个来自集合 S 的 n 个数字的子集 S1，它在 (0, 2^16-1) 范围内。我需要用一个由单个散列函数构造的 256 位布隆过滤器来表示这个子集 S1。布隆过滤器的原因是空间考虑。我选择了 256 位布隆过滤器，因为它符合我的空间要求，并且误报概率足够低。我正在寻找一个非常简单的哈希函数，它可以从集合 S 中获取一个数字并用 256 位表示它，这样每一位都具有大致相等的概率为 1 或 0。

散列函数要求简单的原因是这个散列函数必须为每个像素运行数千次，所以在任何可以修剪指令的地方都是一个胜利。

Answer 1

如果您将一个 16 位值乘以(使用 uint32_t)介于 2^31 和 2^32 之间的质数(或任何奇数)p，则您“可能”在 32 位空间中相当均匀地涂抹结果。然后你可能想添加另一个质数，以防止 0 映射到 0(你希望每个位都有相同的概率为 0或 1，2^256 中只有一个输入值应该输出全零，并且由于只有 2^16 个输入，这意味着您不希望它们都输出全零)。

这就是如何通过一次操作将 16 位扩展为 32 位(加上加载常量所需的任何指令)。使用四个不同的值 p1 ... p4 获得 256 位，并使用不同的 p 值运行一些测试以找到好的(即那些考虑到您正在编码的集合的大小并假设一个理想的散列函数，它产生的误报不会比您对 Bloom 过滤器的预期更多。例如，我很确定 -1 是一个错误的 p 值。

不过，无论这些值有多好，您都会看到一些相关性:例如，正如我在上面所描述的那样，所有 4 个独立值的最低位将相等，这是一个非常严重的依赖关系。所以你可能想要更多的“混合”操作。例如，您可能会说最终输出的每个字节应该是我所描述的两个字节的异或(而不是两个最不重要的字节!)，只是为了摆脱简单的算术关系。

不过，除非我误解了这个问题，否则布隆过滤器通常不是这样工作的。通常您希望您的散列为每个输入生成精确固定数量的设置位，并且计算误报率的所有算法都依赖于此。这就是为什么对于大小为 256 位的布隆过滤器，您通常会有 k 8 位散列，而不是一个 256 位散列。 k 通常小于过滤器大小的一半(以位为单位)(最佳值是过滤器中每个值的位数乘以 ln(2)，即约 0.7)。所以通常您不希望每个位为 1 的概率高达 0.5。

原因是，一旦您将少至 4 个这样的 256 位值组合在一起，过滤器中的几乎所有位都已设置(其中 16 个位中有 15 个位)。所以您已经看到了很多误报。

但是，如果您已经完成数学运算并且对单个哈希函数产生可变数量的设置位平均一半感到满意，那么就足够了。或者数字 256 的两次出现只是巧合，因为对于您选择的集合大小，k 恰好是 32，而您实际上将 256 位散列用作 32 8 位哈希？

[编辑:你的评论澄清了这一点，但无论如何 k 不应该太高以至于你总共需要 256 位哈希。显然，在这种情况下，使用每个值超过 16 位(即少于 16 个值)的布隆过滤器没有意义，因为使用相同的空间量，您可以只列出值，并且误报率为 0。 A每个值 16 位的过滤器给出的误报率约为 2200 分之一。即使在那里，最佳 k 也仅为 23，也就是说，您应该在过滤器中为集合中的每个值设置 23 位.如果您希望集合大于 16 个值，那么您希望为每个元素设置更少的位，并且您将获得更高的误报率。]