生成几个整数的哈希值

Question

我面临着有几个整数的问题,我必须使用它们生成一个整数.例如.

Int 1: 14
Int 2: 4
Int 3: 8
Int 4: 4

Hash Sum: 43

我对值有一些限制,和属性可以有的最大值是30,所有这些的加法总是30.并且属性总是正的.

关键是我想为类似的整数生成相同的哈希值,例如,如果我有整数,14,4,10,2,那么我想生成相同的哈希值,在43以上的情况下.但当然如果整数非常不同(4,4,2,20)那么我应该有一个不同的哈希值.它也需要快速.

理想情况下,我希望哈希和的输出在0到512之间,并且应该均匀分布.根据我的限制,我可以拥有大约5K种不同的可能性,所以我想要的是每桶10个左右.

我确信有很多算法可以做到这一点,但我找不到谷歌搜索这个东西的方法.任何人都可以发一个算法来做这个吗？

更多信息

整个问题是这些整数是函数的属性.我想将函数的值存储在表中,但是我没有足够的内存来存储所有不同的选项.这就是我想在类似属性之间进行概括的原因.

之所以10,5,15与5,10,15完全不同,是因为如果你想象这在3D中那么两点都是完全不同的点

更多信息2

一些答案尝试使用散列来解决问题.但我不认为这太复杂了.感谢其中一条评论,我意识到这是一个聚类算法问题.如果我们只有3个属性并且我们想象3d中的问题,我只需要将块空间分开.

实际上,这可以通过这种类型的规则来解决

if (att[0] < 5 && att[1] < 5 && att[2] < 5 && att[3] < 5)
     Block = 21


if ( (5 < att[0] < 10) &&  (5 < att[1] < 10) &&  (5 < att[2] < 10) &&  (5 < att[3] < 10))
     Block = 45

问题是我需要一种快速而通用的方法来生成那些我无法写出所有可能性的ifs.

Answer 1

简单的解决方案:

将整数转换为用逗号分隔的字符串,并使用常用的散列算法(md5,sha等)对生成的字符串进行散列.

如果你真的想要自己动手,我会做的事情如下:

• 生成大素数P.
• 生成随机数0 <a [i] <P(对于您拥有的每个维度)

要生成散列,请计算:sum(a [i]*x [i])mod P.

Answer 2

给定输入 a、b、c 和 d，每个值的范围为 0 到 30（5 位），以下将产生一个范围为 0 到 255（8 位）的数字。

bucket = ((a & 0x18) << 3) | ((b & 0x18) << 1) | ((c & 0x18) >> 1) | ((d & 0x18) >> 3)

一般方法是否合适取决于如何解释问题。3 个最低有效位被删除，将 0-7 分组为同一组，将 8-15 分组为下一组，依此类推。

0-7,0-7,0-7,0-7 -> bucket 0
0-7,0-7,0-7,8-15 -> bucket 1
0-7,0-7,0-7,16-23 -> bucket 2
...
24-30,24-30,24-30,24-30 -> bucket 255

经过简单测试：

for (int a = 0; a <= 30; a++)
    for (int b = 0; b <= 30; b++)
        for (int c = 0; c <= 30; c++)
            for (int d = 0; d <= 30; d++) {
                int bucket = ((a & 0x18) << 3) |
                             ((b & 0x18) << 1) |
                             ((c & 0x18) >> 1) |
                             ((d & 0x18) >> 3);
                printf("%d, %d, %d, %d -> %d\n",
                         a,  b,  c,  d,   bucket);
            }