分片锁 Map

难度：⭐⭐⭐ 困难

考点

• 降低锁粒度提高并发性能
• hash 分片策略
• 与单锁 map 的性能对比

题目描述

实现一个分片锁 Map（ShardedMap），通过将数据分散到多个分片（每个分片独立加锁）来减少锁竞争。

要求：

1. 固定 16 个分片
2. 用 key 的 hash 决定分片
3. 支持 Set、Get、Delete、Len 操作
4. 并发安全

函数签名

type ShardedMap struct { ... }

func NewShardedMap() *ShardedMap
func (m *ShardedMap) Set(key string, value interface{})
func (m *ShardedMap) Get(key string) (interface{}, bool)
func (m *ShardedMap) Delete(key string)
func (m *ShardedMap) Len() int

提示

1. 16 个 shard，每个 shard 有自己的 sync.RWMutex + map
2. hash 函数可以用 fnv32：hash/fnv 包
3. 分片索引 = hash(key) % numShards
4. Len() 需要遍历所有分片加锁求和

---

参考答案（Go）

点击展开参考答案

//go:build ignore

package answer

import (
	"hash/fnv"
	"sync"
)

const numShards = 16

type shard struct {
	mu   sync.RWMutex
	data map[string]interface{}
}

type ShardedMap struct {
	shards [numShards]*shard
}

func NewShardedMap() *ShardedMap {
	m := &ShardedMap{}
	for i := range m.shards {
		m.shards[i] = &shard{data: make(map[string]interface{})}
	}
	return m
}

func (m *ShardedMap) getShard(key string) *shard {
	h := fnv.New32a()
	h.Write([]byte(key))
	return m.shards[h.Sum32()%numShards]
}

func (m *ShardedMap) Set(key string, value interface{}) {
	s := m.getShard(key)
	s.mu.Lock()
	s.data[key] = value
	s.mu.Unlock()
}

func (m *ShardedMap) Get(key string) (interface{}, bool) {
	s := m.getShard(key)
	s.mu.RLock()
	v, ok := s.data[key]
	s.mu.RUnlock()
	return v, ok
}

func (m *ShardedMap) Delete(key string) {
	s := m.getShard(key)
	s.mu.Lock()
	delete(s.data, key)
	s.mu.Unlock()
}

func (m *ShardedMap) Len() int {
	total := 0
	for _, s := range m.shards {
		s.mu.RLock()
		total += len(s.data)
		s.mu.RUnlock()
	}
	return total
}