统一分配给定属性的哈希值

Question

我试图在多个桶中分配一组项目。我正在寻找以下属性：

1. 存储桶分配需要具有确定性。在不同的运行中，相同的输入应该在同一个桶中结束。
2. 存储桶之间的数据分配应该是统一的。
3. 这适用于相当少量的输入（例如，如果我想在25个桶中分配50个输入，理想情况下每个桶将有2个项目）。

首先尝试从输入数据生成md5并从md5的第一个字节形成桶。我对均匀性不太满意。输入很大时效果很好但小输入不太好。例如。在64个桶中分配100个项目：

List<string> l = new List<string>();

for (int i = 0; i < 100; i++)
{
    l.Add(string.Format("data{0}.txt", i));
}

int[] buckets = new int[64];

var md5 = MD5.Create();
foreach (string str in l)
{
    {
        byte[] hash = md5.ComputeHash(Encoding.Default.GetBytes(str));
        uint bucket = BitConverter.ToUInt32(hash, 0) % 64;
        buckets[bucket % 64]++;
    }
}

有什么建议我可以做些什么来达到更高的均匀性？谢谢。

Answer 1

撇开使用MD5为此目的的效率（参见讨论here和该问题的标记副本），基本上答案是你所拥有的是统一分布的真实情况。

这可能看似违反直觉，但它可以通过数学或实验轻松证明。

作为一种激励性的例子，考虑在0-63范围内精确选择64个数字的任务。你每桶获得一个的几率非常接近0.有6464个可能的序列，其中64个！包含所有64个数字。获得这些序列之一的几率约为3.1×1026中的一个。事实上，获得一个没有元素出现三次的序列的几率小于千分之一（大约是0.000658）。因此，几乎可以肯定，在0-63范围内的64个数字的随机均匀样本将具有一些三元组，并且很可能会有一些四元组。如果样本是100个数字，那么这些概率会变得更大。

但是数学通常不是那么容易计算，所以在这里我选择用实验来说明:-)，使用random.org，这是一个非常可靠的随机数源。我问它在0-63范围内的100个数字，并计算它们（使用bash，所以我的“图形”不如你的那么漂亮）。这是两个运行：

First run:

Random numbers: 
44  17  50  11  16   4  24  29  12  36
27  32  12  63   4  30  19  60  28  39
22  40  19  16  23   2  46  31  52  41
13   2  42  17  29  39  43   9  20  50
45  40  38  33  17  45  28   6  48  12
56  26  34  33  35  40  28  44  22  10
50  55  49  43  63  62  22  50  15  52
48  54  53  26   4  53  13  56  42  60
49  30  14  55  29  62  15  13  35  40
22  38  37  36  10  36   5  41  43  53

Counts:                                                                
                      X                 X         X             
    X       XX   X    X     XX      X   X  X      X  X          
  X X     X XX XXX X  X   X XXX  X XX XXXXXXXX  XXX XX XX   X XX
  X XXX  XXXXXXXXX XX XXX XXXXXXXXXXXXXXXXXXXXX XXX XXXXX   X XX
----------------------------------------------------------------
          1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6
0 2 4 6 8 0 2 4 6 8 0 2 4 6 8 0 2 4 6 8 0 2 4 6 8 0 2 4 6 8 0 2

Second run:

Random numbers:
41  31  16  40   1  51  17  41  27  46
24  14  21  33  25  43   4  36   1  14
40  22  11  22  30  19  23  63  39  61
 8  55  40   6  21  13  55  13   3  52
17  52  53  53   7  21  47  13  45  57
25  27  30  48  38  55  55  22  61  11
11  28  45  63  43   0  41  51  15   2
33   2  46  14  35  41   5   2  11  37
28  56  15   7  18  12  57  36  59  51
42   5  46  32  10   8   0  46  12   9

Counts:
           X                             X    X        X        
  X        X XX      XX                 XX    X    X   X        
XXX  X XX  XXXXX X   XX  X XX X  X  X   XX X XX    XXX X X   X X
XXXXXXXXXXXXXXXXXXXX XXXXX XX XXXX XXXXXXXXX XXXX  XXX XXX X X X
----------------------------------------------------------------
          1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6
0 2 4 6 8 0 2 4 6 8 0 2 4 6 8 0 2 4 6 8 0 2 4 6 8 0 2 4 6 8 0 2

您可以尝试使用您最喜欢的随机数生成器，玩弄分布的大小。你会得到同样的形状。