Равномерно распределяя хэш заданных свойств - PullRequest
Новая
       31

Равномерно распределяя хэш заданных свойств

0 голосов
/ 14 февраля 2019

Я пытаюсь распределить набор предметов по количеству ведер.Я ищу следующие свойства:

  1. Назначение корзины должно быть детерминированным.В разных прогонах один и тот же ввод должен заканчиваться в одном и том же сегменте.

  2. Распределение данных между сегментами должно быть равномерным.

  3. Это должно работать при довольно небольшом числевходов (например, если я хочу распределить 50 входов по 25 сегментам, в идеале каждый сегмент будет иметь 2 элемента).

Первая попытка состояла в том, чтобы сгенерировать md5 из входных данных и сформировать сегмент из первых байтов md5.Я не слишком доволен единообразием.Это работает хорошо, когда ввод велик, но не так хорошо для маленького ввода.Например, распределение 100 предметов по 64 ведрам: 

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]++;
    }
}

Histogram

Какие-либо предложения, что я мог бы сделать для достижения более высокой однородности?Спасибо.

1 Ответ

0 голосов
/ 14 февраля 2019

Оставляя в стороне эффективность использования MD5 для этой цели (см. Обсуждение здесь и в отмеченном дубликате этого вопроса), в основном ответ заключается в том, что у вас есть то, как на самом деле выглядит равномерное распределение.

Это может показаться нелогичным, но это легко продемонстрировать математически или экспериментально.

В качестве своего рода мотивирующего примера рассмотрим задачу выбора ровно 64 чисел в диапазоне 0-63.Вероятность того, что вы получите один за ведро, очень близка к 0. Существует 64 64 возможных последовательностей, из которых 64!содержит все 64 номера.Вероятность получения одной из этих последовательностей составляет около 1 на 3,1 × 10 26 .Фактически, шансы получить последовательность, в которой ни один элемент не появляется три раза, меньше одного на тысячу (это около .000658).Таким образом, почти наверняка, что случайная однородная выборка из 64 чисел в диапазоне 0-63 будет иметь триплеты, и вполне вероятно, что будет некоторый квадруплет.Если в выборке 100 чисел, эти вероятности становятся еще больше.

Но математика не так проста для вычисления в целом, поэтому здесь я решил проиллюстрировать экспериментально :-), используя random.org , который является довольно надежным источником случайных чисел.Я попросил 100 чисел в диапазоне от 0 до 63 и посчитал их (используя 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

Вы можете попробовать это с вашим любимым генератором случайных чисел, играя сРазмер распределения.Вы получите такую ​​же форму.

...