Ridiculously Simple Google Hash Function

A Go implementation based on the paper “A Fast, Minimal Memory, Consistent Hash Algorithm”, describing an evenly distributed hashing function called the “Jump” algorithm:

func Hash(key uint64, numBuckets int) int32 {
    var b int64 = -1
    var j int64

    for j < int64(numBuckets) {
        b = j
        key = key*2862933555777941757 + 1
        j = int64(float64(b+1) * (float64(int64(1)<<31) / float64((key>>33)+1)))
    }

    return int32(b)
}

If you’re curious about that constant, it is “known to produce a good random number list” for 64-bit generators:

Advertisements