为几个整数生成一个哈希和 [英] Generate a hash sum for several integers

问题描述

我面临着有几个整数的问题，我必须使用它们来生成一个整数。

  Int 1：14 
 Int 2：4 
 Int 3：8 
 Int 4：4 
 
哈希值总数：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来想象这个问题，那么我需要的就是将块空间分开。

实际上，这可以用这个规则来解决type

  if（att [0] <5& att [1]< 5& att （5  Block = 21 
 
 
 ）&（5  Block = 45 
  

问题是我需要一种快速和一般的方法来生成那些ifs我不能写所有的可能性。

解决方案

给定输入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  - >存储桶0 
 0-7,0-7,0-7,8-15  - >桶1 
 0-7,0-7,0-7,16-23  - >桶2 
 ... 
 24-30,24-30,24-30,24-30  - >桶255 
  

经常进行测试：

<$ p （int b = 0; b <= 30; b ++）
for（int a = 0; a< = 30; a ++）
对于（int d = 0; d <= 30; d ++）{
int bucket =（（a& 0x18）），则c = 0; c <= 30; c ++） 3）|
（（b& 0x18）<< 1）|
（（c& 0x18）>> 1）| （（d& 0x18）>> 3）;

printf（％d，％d，％d，％d - >％d \ n，
a，b，c，d，bucket）;
}

I am facing the problem of having several integers, and I have to generate one using them. For example.

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

Hash Sum: 43

I have some restriction in the values, the maximum value that and attribute can have is 30, the addition of all of them is always 30. And the attributes are always positive.

The key is that I want to generate the same hash sum for similar integers, for example if I have the integers, 14, 4, 10, 2 then I want to generate the same hash sum, in the case above 43. But of course if the integers are very different (4, 4, 2, 20) then I should have a different hash sum. Also it needs to be fast.

Ideally I would like that the output of the hash sum is between 0 and 512, and it should evenly distributed. With my restrictions I can have around 5K different possibilities, so what I would like to have is around 10 per bucket.

I am sure there are many algorithms that do this, but I could not find a way of googling this thing. Can anyone please post an algorithm to do this?.

Some more information

The whole thing with this is that those integers are attributes for a function. I want to store the values of the function in a table, but I do not have enough memory to store all the different options. That is why I want to generalize between similar attributes.

The reason why 10, 5, 15 are totally different from 5, 10, 15, it is because if you imagine this in 3d then both points are a totally different point

Some more information 2

Some answers try to solve the problem using hashing. But I do not think this is so complex. Thanks to one of the comments I have realized that this is a clustering algorithm problem. If we have only 3 attributes and we imagine the problem in 3d, what I just need is divide the space in blocks.

In fact this can be solved with rules of this type

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

The problem is that I need a fast and a general way to generate those ifs I cannot write all the possibilities.

解决方案

Given the inputs a, b, c, and d, each ranging in value from 0 to 30 (5 bits), the following will produce an number in the range of 0 to 255 (8 bits).

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

Whether the general approach is appropriate depends on how the question is interpreted. The 3 least significant bits are dropped, grouping 0-7 in the same set, 8-15 in the next, and so forth.

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

Trivially tested with:

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);
            }

这篇关于为几个整数生成一个哈希和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！