golang 线程安全哈希表github.com/tidwall/shardmap

测试代码：

package main

import (
	"fmt"
	"github.com/tidwall/shardmap"
	"math/rand"
	"strconv"
	"sync"
	"time"
)

func main() {
	SynTest()
	ConCurrentMap()
}

func SynTest() {
	var m sync.Map
	m.Store("count", 0)

	var wg sync.WaitGroup
	start := time.Now()

	ranRange := 10 * 1000000
	rand.Seed(time.Now().UnixNano())

	for numOfThread := 0; numOfThread < 10; numOfThread++ {
		wg.Add(1)
		go func() {
			defer wg.Done()
			for i := 0; i < 1000000; i++ {
				randomNum := rand.Intn(ranRange)
				val := strconv.Itoa(randomNum)

				m.Store(val, val)
				randomNum = rand.Intn(ranRange)
				val = strconv.Itoa(randomNum)
				m.Load(val)
			}
		}()
	}
	wg.Wait()

	t := time.Now()
	elapsed := t.Sub(start)
	fmt.Println("sync map elapsed :", elapsed)

}

func  ConCurrentMap() {
	 m := shardmap.New(1000000 )

	var wg sync.WaitGroup
	start := time.Now()

	ranRange := 10 * 1000000
	rand.Seed(time.Now().UnixNano())

	for numOfThread := 0; numOfThread < 10; numOfThread++ {
		wg.Add(1)
		go func() {
			defer wg.Done()
			for i := 0; i < 1000000; i++ {
				randomNum := rand.Intn(ranRange)
				val := strconv.Itoa(randomNum)

				m.Set(val, val)
				randomNum = rand.Intn(ranRange)
				val = strconv.Itoa(randomNum)
				m.Get(val)
			}
		}()
	}
	wg.Wait()

	t := time.Now()
	elapsed := t.Sub(start)
	fmt.Println("ConCurrent Map elapsed :", elapsed)

}

与sync.Map对比结果如下：

sync map elapsed : 14.6189622s
ConCurrent Map elapsed : 4.8839917s

Process finished with the exit code 0

shardmap的性能比golang自带的性能高2倍左右。

其关键实现主要在initDo函数的实现：

源码如下：

func (m *Map) initDo() {
	m.init.Do(func() {//这里函数只会执行一次，主要是初始化
		m.shards = 1
		for m.shards < runtime.NumCPU()*16 {//获取运行时的CPU数量，我的测试机是8，也就是m.shards最终为128
			m.shards *= 2
		}
		scap := m.cap / m.shards//根据这个数值，计算每个哈希表的容量，7812
		m.mus = make([]sync.RWMutex, m.shards)//为每个哈希表分配一把读写锁
		m.maps = make([]*rhh.Map, m.shards)//分配128个哈希表
		for i := 0; i < len(m.maps); i++ {
			m.maps[i] = rhh.New(scap)//根据前面的计算，为这128个哈希表分配7812的容量，以2的倍数向上取整，最小为8，运行期间，如果空间不够，会自动扩容，2倍的方式增加
		}
	})
}

//map结构定义
// Map is a hashmap. Like map[string]interface{}, but sharded and thread-safe.
type Map struct {
	init   sync.Once//只会执行一次
	cap    int
	shards int
	seed   uint32
	mus    []sync.RWMutex
	maps   []*rhh.Map
}

我们来看下set的实现：

// Set assigns a value to a key.
// Returns the previous value, or false when no value was assigned.
func (m *Map) Set(key string, value interface{}) (prev interface{}, replaced bool) {
	m.initDo()//只会执行一次，
	shard := m.choose(key)//计算当前的key倍映射到那个子哈希表中，
	m.mus[shard].Lock()//使用对应子哈希表的读写锁进行并发控制
	prev, replaced = m.maps[shard].Set(key, value)//插入或替换之前的内容，如果空间不够，执行resize
	m.mus[shard].Unlock()//解锁
	return prev, replaced//返回旧值
}

上面的分析，可以看到，同一个CPU冲突的概率为1/16，大大减小了锁的争抢。性能会高于sync.Map。这个库的代码比较简单，如果需要，定制开发，改起来也比较容易。如果想缩小概率也很容易修改。