哈希函数，压缩20位输入到5位输出

Question

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

我在网上搜索了上周的内容，但却找不到有用的东西。

您的帮助非常感谢。谢谢

Answer 1

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

Answer 2

该计算等同“打破输入到5个比特的4个块和XOR他们”由Barmar的建议，但可能是一点点更有效（其中x是输入）：

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

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

Answer 3

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

Answer 4

你真的需要一个：编辑：原创或新算法？ （即这是一个学校作业）。

您可以使用标准库的随机数生成器并为您的20位播种。它使用的算法将绰绰有余。 What common algorithms are used for C's rand()?

只要选择一个标准的实现，你应该没问题。下面的例子只是生活在野外（非便携式）。由于rand的实现根据编译器或库的版本的不同而不同，如果你将它们用于通用的东西，那么你使用哈希将不匹配，但是我打赌你只需要在运行时消息校验和或它是一个学校任务。

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