c - 适用于异构元组的快速 8 位校验和算法

Question

假设我有包含 3 个异构整数类型(int16_t、int32_t、int64_t)的三元组，并且我想计算一个 8 位这 3 个值的无符号校验和。假设所有值在所有有效位上均匀分布，因此我们不能通过在连接它们时截断任何值来作弊。

什么是计算具有相对较低冲突率和非加密属性的校验和的快速方法？我猜我可以连接字节并使用 Fletcher 校验和或 Pearson 哈希的变体，但我见过的所有实现似乎都过时了，我想看看是否可以进一步利用任何 SIMD 或属性现代(Skylake)建筑。

我也知道 MurmurHash，但它没有 8 位实现。

Answer 1

由于您提到所有值均匀分布在所有位上，因此您可以简单地选择元组中的任何字节作为 8 位哈希，忽略其余位，即本质上是免费的。结果是一个完全一致的哈希函数，这是最好的(它的碰撞概率为 256 分之一，这是不可预测输入的下限)。

如果您输入的位在某种程度上不均匀，那么您只需要一个“更好”的哈希函数(对于不仅仅是随机数的真实数据来说，绝大多数情况下都是这种情况，但我猜您的情况有所不同)。