golang 一致哈希

 golang 实现一致哈希

package consistenthash

import (
	"hash/crc32"
	"sort"
	"strconv"
)

type Hash func(data []byte) uint32

type Map struct {
	hash        Hash
	replication int
	keys        []int
	hashMap     map[int]string
}

func New(replication int, fn Hash) *Map {

	m := &Map{
		replication: replication,
		hashMap:     make(map[int]string),
		hash:        fn,
	}

	if m.hash == nil {
		m.hash = crc32.ChecksumIEEE
	}
	return m

}

func (m *Map) Add(keys ...string) {

	for _, key := range keys {

		for i := 0; i < m.replication; i++ {

			hs := int(m.hash([]byte(key + strconv.Itoa(i))))
			m.keys = append(m.keys, hs)
			m.hashMap[hs] = key

		}
	}

	sort.Ints(m.keys)

}

func (m *Map) Get(key string) string {

	if m.IsEmpty() {
		return ""
	}

	hs := int(m.hash([]byte(key)))

	ind := sort.Search(len(m.keys), func(n int) bool {

		return m.keys[n] >= hs

	})

	if ind == len(m.keys) {
		ind = 0
	}

	return m.hashMap[m.keys[ind]]

}

func (m *Map) IsEmpty() bool {

	return len(m.keys) == 0
}

 

package main

import (
	"consistenthash"
	"fmt"
)

func main() {
	hash := consistenthash.New(10, nil)
	hash.Add("192.168.1.101", "192.168.1.102", "192.168.1.103", "192.168.1.104", "192.168.1.105")

	fmt.Println(hash.Get("dongtian"))
	fmt.Println(hash.Get("dongtian1"))
	fmt.Println(hash.Get("dongtian2"))
	fmt.Println(hash.Get("dongtian2"))
	fmt.Println(hash.Get("dongtian2"))
	fmt.Println(hash.Get("dongtian2"))
	fmt.Println(hash.Get("dongtian2"))
	fmt.Println(hash.Get("dongtian2"))
	fmt.Println(hash.Get("11"))
	fmt.Println(hash.Get("12"))
	fmt.Println(hash.Get("13"))
}

 

/Users/dongtian/Desktop/soft/wp/golang/go/bin/go build -i [/Users/dongtian/Desktop/soft/wp/golang/stu/src/te]
成功: 进程退出代码 0.
/Users/dongtian/Desktop/soft/wp/golang/stu/src/te/te  [/Users/dongtian/Desktop/soft/wp/golang/stu/src/te]
192.168.1.103
192.168.1.101
192.168.1.101
192.168.1.101
192.168.1.101
192.168.1.101
192.168.1.101
192.168.1.101
192.168.1.102
192.168.1.103
192.168.1.102
成功: 进程退出代码 0.