Почему распределение MD5 Голанга не кажется однородным? - PullRequest
Новая
       7

Почему распределение MD5 Голанга не кажется однородным?

0 голосов
/ 29 апреля 2018

Я полностью ожидаю, что у меня где-то есть ошибка или я что-то неправильно понимаю, но почему следующий код не демонстрирует равномерное распределение? 

func TestMD5(t *testing.T) {
    n := 50000
    counts := map[uint32]int{} // # of hashes per 1/nth shard

    for i := 0; i < n; i++ {
        hash := md5.Sum(newUUID())
        result := binary.BigEndian.Uint32(hash[:4])
        counts[result/uint32(n)]++
    }

    dupeShards := 0
    dupeEntries := 0
    for _, count := range counts {
        if count > 1 {
            dupeShards++
            dupeEntries += count - 1
        }
    }
    t.Logf("%d inputs hashed to the same %d shards as other inputs.", dupeEntries, dupeShards)

    if len(counts) < n*95/100 {
        t.Fatalf("%d populated shards not within 5%% of expected %d uniform distribution!", len(counts), n)
    }
}

https://play.golang.org/p/05mA0Dl9GBG

-

Пояснение к коду:

  • MD5 50 000 случайных UUID.
  • Для каждой суммы MD5 возьмите первые 4 байта и преобразуйте в uint32.
  • Разделите результат на 50 КБ (используя усеченное деление / деление по полу), чтобы распределить хэши на осколки размером 50 КБ.

==> Я бы ожидал, что 50k суммы MD5 будут равномерно распределены по 50 тысячам черепков, но я последовательно вижу, что заполнены только ~ 38 тысяч черепков, с комкованием в ~ 10 тысяч черепков: 

main.go:29: 12075 inputs hashed to the same 9921 shards as other inputs.
main.go:32: 37925 populated shards not within 5% of expected 50000 uniform distribution!

Я могу повторить это и с другими хешами (например, FNV), поэтому я предполагаю, что я что-то неправильно понимаю. Спасибо за помощь!

1 Ответ

0 голосов
/ 29 апреля 2018

Это абсолютно нормальное поведение, которое не показывает смещения или неправильности реализации MD5.

То, что вы делаете, - это (очень близко) брать 50 000 случайных чисел от 0 до 49 999. Когда вы делаете это, почти наверняка многие цифры будут повторяться, и поэтому некоторые цифры не появятся. На самом деле было бы очень маловероятно, что 50 000 номеров должны быть разными, без повторений.

Вы можете проверить это с помощью шестигранных кубиков - если вы бросите их 6 раз, вы вряд ли получите все шесть чисел и гораздо чаще увидите около 3, 4 или 5 из них с одним, два или три повторения. Это также связано с так называемым парадоксом дня рождения .

Другим примером этого явления является «вопрос стикера Панини». Альбом с наклейками Panini - это книга, вмещающая около 600 футбольных наклеек, посвященных Чемпионату мира по футболу. Каждый из них пронумерован и различен, и они произвольно представлены в пакетах. Вы должны получить один из каждого номера, чтобы завершить альбом. Предположим, что вы купили абсолютно правильное количество стикеров, чтобы заполнить альбом. Было бы очень повезло, если бы вы смогли идеально заполнить альбом, не имея двойников или недостающих наклеек. Фактически вам нужно купить в среднем большое количество наклеек, чтобы получить хотя бы одну из них (если вы не обмениваетесь копиями с другими коллекционерами).

Число различных значений 0-49,999, которые появляются, и число, показывающее «комкование», можно рассчитать математически. Я не уверен, как именно вы измеряете комкование. Но значение 38K заполненных значений будет достаточно стабильным от одного испытания к другому, даже если фактические значения, которые вы видите, изменятся.

Фактически, ожидаемое количество заполненных значений равно (1 - 1 / e) n, где n - количество возможных значений, а e - математическая константа 2.718281828 ... Ответ для n = 50000 - 31606. Конечно, вы не всегда получите это значение, но все результаты должны быть в пределах нескольких сотен или около того (плеваться здесь). Вы допустили небольшую ошибку в своей программе, поэтому я не смог расшифровать соответствующий расчет, который дает вам ~ 37000.

...