Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.

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 ?

[Edit] 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 !

share|improve this question
3  
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
1  
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
1  
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

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.