Murmur3 Shard Hashing

package main

import (
	"encoding/binary"
	"fmt"
	"math/bits"
)

func Murmur3(data []byte, seed uint32) uint32 {
	const (
		c1 = 0xcc9e2d51
		c2 = 0x1b873593
	)
	h := seed
	blocks := len(data) / 4
	for i := 0; i < blocks; i++ {
		k := binary.LittleEndian.Uint32(data[i*4:])
		k *= c1
		k = bits.RotateLeft32(k, 15)
		k *= c2
		h ^= k
		h = bits.RotateLeft32(h, 13)
		h = h*5 + 0xe6546b64
	}
	tail := data[blocks*4:]
	var k uint32
	switch len(tail) {
	case 3:
		k ^= uint32(tail[2]) << 16
		fallthrough
	case 2:
		k ^= uint32(tail[1]) << 8
		fallthrough
	case 1:
		k ^= uint32(tail[0])
		k *= c1
		k = bits.RotateLeft32(k, 15)
		k *= c2
		h ^= k
	}
	h ^= uint32(len(data))
	h ^= h >> 16
	h *= 0x85ebca6b
	h ^= h >> 13
	h *= 0xc2b2ae35
	h ^= h >> 16
	return h
}

func Shard(key string, shards int) int {
	if shards <= 0 {
		panic("shards must be positive")
	}
	return int(Murmur3([]byte(key), 0) % uint32(shards))
}

func main() {
	fmt.Printf("hash(abc)=%08x shard=%d\n", Murmur3([]byte("abc"), 0), Shard("abc", 16))
	counts := make([]int, 16)
	for i := 0; i < 10000; i++ {
		counts[Shard(fmt.Sprintf("user:%d", i), 16)]++
	}
	minimum, maximum := counts[0], counts[0]
	for _, count := range counts {
		if count < minimum {
			minimum = count
		}
		if count > maximum {
			maximum = count
		}
	}
	fmt.Println("buckets:", counts)
	fmt.Printf("min=%d max=%d\n", minimum, maximum)
}