Разбить весь хэш-диапазон на n равных диапазонов

Question

Я хочу взять диапазон хешей (md5 или sha1) и разделить его на n равных диапазонов.

Например, если m (num узлов) = 5, весь диапазон хеш-функции будет разделен на 5, чтобы обеспечить равномерное распределение диапазонов ключей. Я хотел бы, чтобы n = 1 (узел 1) был от начала диапазона хеш-функции до 1/5, 2 от 1/5 до 2/5 и т. Д. Вплоть до конца.

По сути, мне нужно, чтобы диапазоны клавиш были сопоставлены с каждым n, чтобы при хэшировании значения он знал, какой n позаботится об этом диапазоне.

Я новичок в хешировании и немного не уверен, с чего начать. Любая помощь, которую вы могли бы оказать, была бы великолепна.

Answer 1

Если вы можете выстоять немного сложнее, чтобы убрать смещение (любую степень двух невозможно разделить равномерно на 5, поэтому должно быть некоторое смещение), то по модулю (% в C и многих других языках с C -подобный синтаксис) - это способ разделить весь диапазон на 5 почти одинаковых по размеру разделов.

Любое сообщение m с md5(m)%5==0 находится в первом разделе и т. Д.

Answer 2

Если вы хотите равномерно разместить хеш-значение в нескольких «корзинах», тогда подойдет какая-то простая математика. Остерегайтесь случаев округления по краям ... Лучше использовать степень 2 для значения ВЕДРО.

Кстати, это код Python, который поддерживает большие целые числа ...

BUCKETS    = 5
BITS       = 160

BUCKETSIZE = 2**BITS / BUCKETS

int('ad01c5b3de58a02a42367e33f5bdb182d5e7e164', 16) / BUCKETSIZE == 3
int('553ae7da92f5505a92bbb8c9d47be76ab9f65bc2', 16) / BUCKETSIZE == 1
int('001c7c8c5ff152f1cc8ed30421e02a898cfcfb23', 16) / BUCKETSIZE == 0