Hash functions and incomplete consistent hashing.

hash_func_and_stuff.go

package main

import (
	"fmt"
	"hash/adler32"
	"hash/crc32"
	"hash/fnv"

	"github.com/spaolacci/murmur3"
)

func genKeyFnv(value string) uint32 {
	fnv32 := fnv.New32()
	fnv32.Write([]byte(value))
	return fnv32.Sum32()
}

func genKeyCrc(value string) uint32 {
	return crc32.ChecksumIEEE([]byte(value))
}

func getKeyAdler(value string) uint32 {
	return adler32.Checksum([]byte(value))
}

func getKeyMurmur(value string) uint32 {
	return murmur3.Sum32([]byte(value))
}

func getPosition(sum uint32, size int) int {
	return int(sum % uint32(size))
}

func contains(ints []int, i int) bool {
	for _, j := range ints {
		if j == i {
			return true
		}
	}
	return false
}

func main() {
	size := 10

	for i := 1; i <= 5; i++ {
		serverName := fmt.Sprintf("server-%d", i)
		serverPositions := []int{}
		pos := getPosition(genKeyFnv(serverName), size)
		if !contains(serverPositions, pos) {
			serverPositions = append(serverPositions, pos)
		}

		pos = getPosition(genKeyCrc(serverName), size)
		if !contains(serverPositions, pos) {
			serverPositions = append(serverPositions, pos)
		}

		pos = getPosition(getKeyAdler(serverName), size)
		if !contains(serverPositions, pos) {
			serverPositions = append(serverPositions, pos)
		}

		pos = getPosition(getKeyMurmur(serverName), size)
		if !contains(serverPositions, pos) {
			serverPositions = append(serverPositions, pos)
		}
		fmt.Println(serverName, ":", serverPositions)
	}

	fmt.Println("")
	for i := 1; i <= 5; i++ {
		key := fmt.Sprintf("cache-key-%d", i)
		fmt.Println(key, ":", getPosition(genKeyFnv(key), size))
	}
}