8
$\begingroup$

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 !

$\endgroup$
  • 3
    $\begingroup$ A real hash should not give such non-uniform results. Are you sure the hash algorithm is correctly implemented? $\endgroup$ – whuber Apr 12 '12 at 16:57
  • $\begingroup$ 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. $\endgroup$ – oDDsKooL Apr 13 '12 at 8:32
  • 1
    $\begingroup$ 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. $\endgroup$ – whuber Apr 13 '12 at 13:29
  • 1
    $\begingroup$ The first character of the Md5 hash should be uniform. But you'd get only 16 values (it's an hexadecimal encoding) $\endgroup$ – leonbloy Apr 13 '12 at 19:42
  • 1
    $\begingroup$ 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 ;) ? $\endgroup$ – oDDsKooL Apr 16 '12 at 12:35
11
$\begingroup$

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

(updated version)

Suppose we have a source generating independent events that we want to distribute uniformly into $B$ buckets.

The key steps are:

  1. hash each event $e$ to an integer $i$ of size $2^N$
  2. project onto $\mathcal{R} \times [0, 1[$ as $p = \frac{i}{2^N}$
  3. find matching bucket $b_i$ so that $\frac{b_i}{B} \le p \lt \frac{b_{i+1}}{B}$

For 1. a popular solution is to use MurmurHash to generate a 64 or 128 bits integer.

For 3. a simple solution is to iterate on $j = 1..B$ and check that $p$ is in $[\frac{b_j}{B}, \frac{b_{j+1}}{B}[$

In (python) pseudo-code the overall procedure could be:

def hash_to_bucket(e, B):
    i = murmurhash3.to_long128(str(e))
    p = i / float(2**128)
    for j in range(0, B):
        if j/float(B) <= p and (j+1)/float(B) > p:
            return j+1
    return B

(previous version, really not optimal)

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])+16*int(hash[1])

This value lives in the range [0,16+(16-1)*16[, hence we just have to modulo it to 100 to generate a bucket in the [0, 100[ range: As pointed out in the comments, doing so impact the uniformity of the distribution since the first letter is more influential than the second.

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. One can then note that taking the modulo of i can be decomposed into a distributive and additive operation:

\begin{align} i \mod N = (&\\ &(h_0 \mod N) \\ &+ (16 \mod N \times h_1 \mod N) \\ &+ ... \\ &+ (16^{31} \mod N \times h_{31} \mod N)\\ &) \mod N \end{align}

$\endgroup$
  • $\begingroup$ Any improvements to this answer are welcome. $\endgroup$ – oDDsKooL Sep 24 '13 at 8:53
  • $\begingroup$ This doesn't look like a good solution because when "any two letters" are "uniformly distributed," the buckets from $0$ through $55$ will typically get 50% more hits per bucket than the buckets from $56$ through $99$. In effect, you are using a terrible hash function in attempt to hash the hash itself into 100 buckets. Why not just use a known good hash function for that purpose? $\endgroup$ – whuber May 12 '15 at 17:10
  • $\begingroup$ I agree. A better hand-rolled solution would be to take a chunk of the hex string that could translate into say an integer of 16 bits space. Then divide the actual value by the maximal 16 bits integer value, multiply by hundred and round. $\endgroup$ – spdrnl May 12 '15 at 17:36
  • $\begingroup$ If you use a number of buckets in the form of $2^n$, you can take only the last $n$ bits of the hash (and it's equivalent in hex characters). This way the result of the modulo operation will be exactly the same as when calculating it on the full conversion to integer. It may also work OK if you use a number of buckets that is not a power of $2$. $\endgroup$ – alesc May 12 '15 at 17:37
  • $\begingroup$ @whuber I agree this is not quite optimal and projecting to a continuous [0,1[ interval is much better. I've verified that experimentally too. I will edit the answer to reflect that view. $\endgroup$ – oDDsKooL May 19 '15 at 9:05
0
$\begingroup$

I had a similar problem and came up with a different solution which may be faster and more easily implemented in any language.

My first thought was to dispatch items quickly and uniformly in a fixed number of buckets, and also to be scalable, I should mimic randomness.

So I coded this little function returning a float number in [0, 1[ given a string (or any kind of data in fact).

Here in Python:

import math
def pseudo_random_checksum(s, precision=10000):
    x = sum([ord(c) * math.sin(i + 1) for i,c in enumerate(s)]) * precision
    return x - math.floor(x)

Off course it's not random, in fact it's not even pseudo random, the same data will always return the same checksum. But it acts like random and it's pretty fast.

You can easily dispatch and later retrieve items in N buckets by simply assigning each item to bucket number math.floor(N * pseudo_random_checksum(item)).

$\endgroup$
  • $\begingroup$ Do you have an intuition or proof that it will place the samples uniformly in [0,1]? $\endgroup$ – sud_ Jun 12 '18 at 14:29
  • $\begingroup$ @sud_ This function is discussed here: stackoverflow.com/a/19303725/1608467 $\endgroup$ – fbparis Jun 14 '18 at 0:06
  • $\begingroup$ @sud_ Also, I've run some tests to compare it with a legit random number generator and it was OK in every cases I've tested. $\endgroup$ – fbparis Jun 14 '18 at 2:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.