# How to uniformly project a hash to a fixed number of buckets

Hi Fellow Statisticians,

I have a source generating hashes (e.g. computing a string with a timestamp and other information and hashing with md5) and I want to project it into a fixed number of buckets (say 100).

sample hash: 0fb916f0b174c66fd35ef078d861a367

What I thought at first was to use only the first character of the hash to choose a bucket, but this leads to a wildly non-uniform projection (i.e. some letters apppear very rarely and other very frequently)

Then, I tried to convert this hexa string into an integer using the sum of the char values, then take the modulo to choose a bucket:

import sys

for line in sys.stdin:
i = 0
for c in line:
i += ord(c)
print i%100


It seems to work in practice, but I don't know if there are any common sense or theoretical results that could explain why and to which extent this is true ?

 After some thought I came to the following conclusion: In theory you can convert the hash into a (very big) integer by interpreting it as a number : i = h[0] + 16*h[1]+16*16*h[2] ... + 16^31*h[31] (each letter represents an hexadecimal number). Then you could modulo this big number to project it to the bucket space. [/Edit]

Thanks !

-
A real hash should not give such non-uniform results. Are you sure the hash algorithm is correctly implemented? –  whuber Apr 12 '12 at 16:57
I doubt there is a bug in the hashing algorithm itself. But I suspect the characters of the hex digest not to be strictly uniform and independently distributed. –  oDDsKooL Apr 13 '12 at 8:32
That's what I find doubtful: a "cryptographically secure" hash like MD5 should have uniform distributions of all digits, unless there is something very special about the distribution of the input ("special" means intimately linked with the MD5 algorithm). Your proposed solution amounts to re-hashing the hash, which should not be necessary at all. –  whuber Apr 13 '12 at 13:29
The first character of the Md5 hash should be uniform. But you'd get only 16 values (it's an hexadecimal encoding) –  leonbloy Apr 13 '12 at 19:42
Thanks for insisting on that point, I re-run my counting on the hashes' first letter and it seems indeed ~uniformly distributed : {'a': 789, 'c': 769, 'b': 755, 'e': 730, 'd': 804, 'f': 749, '1': 716, '0': 758, '3': 734, '2': 735, '5': 787, '4': 756, '7': 771, '6': 721, '9': 764, '8': 765}. Therefore my question is more or less answered as I just need to project this 16-states random generator to a 100-states space, which can be done using the first 2 letters of the hash to generate an integer of range [0,16+16*16] and modulo it to 100. Mind if I answer my own question ;) ? –  oDDsKooL Apr 16 '12 at 12:35
show 1 more comment

NB: putting in form the answer that emerged from discussion in comments so that it's easier to read for interested people

The first observation is that the n-th letter of the hash should be uniformly distributed with respect to the alphabet (which is here 16 letters long - thanks to @leonbloy for pointing that out).

Then, to project it to a [0,100[ range, the trick is to take 2 letters from the hash (e.g. 1st and 2nd positions) and generate an integer with that:

int_value = int(hash[0])+10*int(hash[1])


This value lives in the range [0,16+16*16[, hence we just have to modulo it to 100 to generate a bucket in the [0, 100[ range:

bucket = int_value % 100


In theory you can convert the whole hash into a (very big) integer by interpreting it as a number : i = h[0] + 16*h[1]+16*16*h[2] ... + 16^31*h[31] (each letter represents an hexadecimal number). Then you could modulo this big number to project it to the bucket space. But it involves dealing with potential overflows and should not give additional precision since any two letters of the hash should be already uniformly distributed.

-
Any improvements to this answer are welcome. –  oDDsKooL Sep 24 at 8:53