c - 将 20 位输入压缩为 5 位输出的哈希函数

Question

我需要为哈希函数提出一个算法，该算法需要 20 位长的输入，而输出应该只有 5 位长。

上周我在互联网上进行了搜索，但找不到任何有用的信息。

非常感激你的帮助。谢谢

Answer 1

一个简单的解决方案是将输入分成 4 个 5 位的块并对它们进行异或。

Answer 2

((x * 1772 + 271828182) % 314159) & 31

Answer 3

这个计算相当于 Barmar 建议的“将输入分成 4 个 5 位的块并对它们进行异或”，但可能更有效（x输入在哪里）：

t = x ^ (x>>10);
result = (t ^ (t>>5)) & 31;

但是，XOR 方法通常不会像 Crocker 提到的方程式那样搅动和混合原始的 20 位。在某些机器上，这种方法会比 Crocker 的更快，反之亦然。

Answer 4

你真的需要一个:edit: 原始或新算法吗？（即，这是一项学校作业）。

您可以只使用标准库的随机数生成器并将其播种为 20 位。它使用的算法将绰绰有余。C 的 rand() 使用了哪些常用算法？

只需选择一种标准实现，您就可以了。下面的例子只是生活在野外（非便携方面）。由于 rand 实现因编译器或库的版本而异，如果您将它们用于通用的东西，您使用的哈希将不匹配，但我敢打赌，您只需要运行时消息校验和或者它是学校作业.

#include <time.h>
#include <stdlib.h>
...
int compress20To5(int input) {
    srand( input );
    return rand() & 0x1f; // mask last 5 bits 0x1f (11111b)
}