Go并发Map适配int64键时哈希函数报错，求正确实现方案

我用了一个仅支持string类型键的并发Map，为了适配int64类型键，我把所有string替换成int64并修改了哈希函数。

以下是我实现的int64键分片逻辑：

// GetShard returns shard under given key
func (m ConcurrentMap[V]) GetShard(key int64) *ConcurrentMapShared[V] {
    // 我认为Go原生map的哈希函数足够好用
    return m[key%int64(SHARD_COUNT)]
}

运行时在return行触发了panic: runtime error: index out of range [-7]错误。

我的哈希函数实现有问题吗？能否提供合适的哈希算法示例？是否需要先用murmurhash3处理键再取模？如果需要请给出示例。

更新 #

我是否应该把GetShard改成下面这样？

// GetShard returns shard under given key
func (m ConcurrentMap) GetShard(key int64) *ConcurrentMapShared {
    var h maphash.Hash
    // 这里应该传入什么seed值？
    h.SetSeed(seed)
    binary.Write(&h, binary.LittleEndian, key)
    return m[h.Sum64()%uint64(SHARD_COUNT)]
}

另外，这里的seed值应该怎么选？

1. 最初实现的问题 #

你遇到的索引越界错误，核心原因是Go语言中负数取模的结果仍是负数。比如当key为负数时，key%int64(SHARD_COUNT)会得到负数，而数组索引不允许为负，直接用这个结果访问分片数组自然会panic。

2. 简单修正方案 #

只需要把取模后的结果转为非负数即可，比如先将key转为无符号整数再取模：

func (m ConcurrentMap[V]) GetShard(key int64) *ConcurrentMapShared[V] {
    // 将int64转为uint64，避免负数取模问题
    return m[uint64(key)%uint64(SHARD_COUNT)]
}

或者手动处理负数结果：

func (m ConcurrentMap[V]) GetShard(key int64) *ConcurrentMapShared[V] {
    idx := key % int64(SHARD_COUNT)
    if idx < 0 {
        idx += int64(SHARD_COUNT)
    }
    return m[idx]
}

3. 关于哈希算法的选择 #

• 如果你的键分布比较均匀（比如没有大量连续的负数或正数），上面的简单取模方案足够用，不需要额外的哈希函数。
• 如果键的分布存在明显偏斜（比如集中在某一段整数范围），可以使用更均匀的哈希算法，比如murmurhash3或者Go标准库的maphash。

使用murmurhash3的示例

先引入murmurhash3库，然后实现分片逻辑：

import "github.com/spaolacci/murmur3"

func (m ConcurrentMap[V]) GetShard(key int64) *ConcurrentMapShared[V] {
    var b [8]byte
    binary.LittleEndian.PutUint64(b[:], uint64(key))
    // 用murmurhash3计算哈希值，seed可自定义（比如1）
    hash := murmur3.Sum64WithSeed(b[:], 1)
    return m[hash%uint64(SHARD_COUNT)]
}

使用标准库maphash的正确方式

你更新后的代码思路是对的，maphash是Go标准库中专门用于哈希的工具，随机性和均匀性都很好。关于seed的选择：

• 可以使用一个固定的随机值（比如123456），只要保证整个程序运行期间seed不变即可；
• 也可以用maphash.MakeSeed()生成一个随机seed，确保每次程序启动的哈希结果不同，避免固定哈希可能带来的碰撞问题。

修正后的maphash实现：

import (
    "encoding/binary"
    "hash/maphash"
)

// 全局定义seed，用maphash.MakeSeed()生成随机值
var seed = maphash.MakeSeed()

func (m ConcurrentMap[V]) GetShard(key int64) *ConcurrentMapShared[V] {
    var h maphash.Hash
    h.SetSeed(seed)
    // 写入int64的字节表示
    binary.Write(&h, binary.LittleEndian, key)
    // 取模得到分片索引
    idx := h.Sum64() % uint64(SHARD_COUNT)
    return m[idx]
}

总结 #

• 优先用简单的无符号转换取模解决当前panic问题；
• 若键分布不均，再考虑用murmurhash3或maphash优化分片均匀性；
• maphash的seed可以固定或随机生成，只要全局一致即可。

内容的提问来源于stack exchange，提问作者john