Comments 15
Значение по простому модулю (а именно так вычисляется попадание хэша в массив) должно лежать в диапазоне, равном длине массива. Для составных чисел это требование не соблюдается. Поэтому массив длиной [составное число] может быть заполнен лишь частично.
То, что вы говорите, не похоже на правду. M % N для положительного целого N и неотрицательного целого M всегда лежит в [0; N-1]. Даже распределение, насколько понимаю, должно быть равномерным для равномерно распределенного M.
Согласен с iliazeus.
Также добавлю, что штатная реализация hash table в ядре linux-а оперирует с количеством корзин, равным степени двойки (2, 4, 8, ...). Простыми числами там и не пахнет.
Степень двойки (как легко вычисляемая сдвигом) по модулю простого числа даёт именно наибольшую относительную "ширину" таблицы только для простых чисел. Для составных размер таблицы будет в разы меньше составного числа.
В википедии степень двойки фигурирует в разделе "Variable range". Текст на английском, но обычно слева есть возможность выбрать язык. Хотя на русском обычно тексты менее полные.
Теперь мы знаем, какие функции дают наши "магические числа". К сожалению, определений в этом файле не нашлось.
Но у вас же прямо в картинке есть комментарий:
Hidden text
"Default value for rehash policy. Bucket size is (usually) the smallest prime that keeps the load factor small enough."
Ну а причина, по которой умножается на два, примерно такая же как и для std::vector - чтобы амортизированная сложность копирования данных при перехешировании была O(1) на каждую вставку элемента.
Насколько я понимаю, простые модули для хеш-таблиц выбирают для того, чтобы было меньше коллизий при использовании определенных алгоритмов хеширования. Условие, насколько помню, даже более слабое - модуль в хеш-таблице должен быть взаимно простым с неким параметром, который используется в алгоритме хеширования. Это легче всего организовать, если либо оба будут простыми числами, либо если одно будет просым больше двух, а второе - степенью двух.
Мои знания алгоритмов уже не те, что раньше, но вот тут есть более подробный разбор (на английском, правда). Там, насколько вижу, и алгоритм из GCC вскользь упоминается.
А конкретная последовательность простых такая для того, чтобы они росли примерно как степени двойки. Это позволяет иметь, в среднем, константное время на переаллокацию и перехеширование таблицы.
Хеши беруться по модулю размера таблицы. Простые модули используются, потому что хеши по не простым модулям часто распределены хуже.
Потому что, например, операция умножения по не простому модулю не обратима. Поэтому операции над разными входными данными могут совпадать чаще. Например, в таблице умножения по модулю 5, все числа, кроме 0, встречаются по 4 раза. В таблице умножения по модулю 6 же: 1 встречается 2 раза, 2 — 6 раз, 3 — 5 раз, 4 — 6 раз, 5 — 2 раза. Похожие свойства вычисления по модулям сказываются на многих агоритмах вычисления хешей.
Умножение же размера контейнера на какое-то число каждый раз — это известный трюк, гаранитирующий, что каждое число в таблице будет рехешированно O(1) раз в среднем.
Это так потому что сумма 1 + 1/2 + 1/4 + 1/8 +… сходится. Если у вас в таблице оказалось n чисел, то все они были туда один раз добавлены. Половина, возможно была там до прошлого рехеширования. Т.е. было еще n/2 лишних хеширований. Половина от половины могла быть там 2 рехеширования назад — поэтому добавляется еще n/4. и т.д. В итоге не более чем 2n раз были подсчитаны хеши элементов.
Рехеширование как бы размазывается во времени равномерно.
Вероятно, поведение при добавлении элемента похоже на автоматический .reserve() вектора на условные 16 элементов при его создании. То есть понятно, что если юзер сделал umap, то туда будут добавляться еще элементы, и было выбрано небольшое число для условного .reserve().
"Первая часть изысканий делается через встроенную в IDE возможность перехода " а IDE какая? VS Code, CLion?
Вглубь std::unordered_map: магические числа