Geek Answers Handbook

Divide the entire hash range into n equal ranges

I want to take a hash range (md5 or sha1) and split it into n equal ranges.

For example, if m (num nodes) = 5, the entire hash range will be divided by 5, so that there will be an even distribution of key ranges. I would like n = 1 (node ​​1) to be from the beginning of the hash range to 1/5, 2 from 1/5 to 2/5, etc. To the end.

Basically, I need to have key ranges associated with each n, so when I pass the value, it knows which n will take care of that range.

I am new to hashing and a little unsure where I could start solving this for a project. Any help you could give would be great.

+6
hash md5 sha1
source share
2 answers

If you can evade bias a bit (any force of the two cannot be divided evenly by 5, then there must be some bias), then modulo ( % in C and many other languages ​​with C-like syntax) - this is a way to split the whole range of 5 almost the same size.

Any message m with md5(m)%5==0 is in the first section, etc.

+1
source share

If you want to put the hash value in the number of buckets evenly, then simple math will do the trick. Watch out for rounding off the edges ... You better use power 2 for the BUCKETS value.

This is python code, by the way, which supports large integers ...

 BUCKETS = 5 BITS = 160 BUCKETSIZE = 2**BITS / BUCKETS int('ad01c5b3de58a02a42367e33f5bdb182d5e7e164', 16) / BUCKETSIZE == 3 int('553ae7da92f5505a92bbb8c9d47be76ab9f65bc2', 16) / BUCKETSIZE == 1 int('001c7c8c5ff152f1cc8ed30421e02a898cfcfb23', 16) / BUCKETSIZE == 0
0
source share

More articles:


All Articles