c# - 均匀分布给定属性的散列

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。有 64⁶⁴ 个可能的序列，其中 64!包含所有 64 个数字。获得其中一个序列的几率约为 3.1×10²⁶ 中的一个。事实上，得到一个没有元素出现 3 次的序列的几率小于千分之一(约为 .000658)。所以几乎可以肯定，0-63 范围内的 64 个数字的随机均匀样本会有一些三元组，而且很可能会有一些四元组。如果样本是 100 个数字，这些概率就会变得更大。

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

第一次运行:

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

第二次运行:

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

您可以使用您最喜欢的随机数生成器来尝试此操作，并研究分布的大小。你会得到同样的形状。