英文:
Integer hash function for concurrent map implementation golang
问题
我正在使用这个仓库中的并发映射repo，它只使用字符串作为键，并且没有针对整数键的任何实现，所以我尝试通过将所有的string替换为int64并修改哈希函数来实现它。
这是用整数作为键的gist。下面是我如何对int64键进行哈希的方式。这种方式是正确的吗，可以得到正确的分片？
// GetShard returns shard under given key
func (m ConcurrentMap[V]) GetShard(key int64) *ConcurrentMapShared[V] {
// 我假设Go的映射哈希函数已经足够好了
return m[key%int64(SHARD_COUNT)]
}
当我运行这段代码时，在GetShard函数中的返回行上出现了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
// 在这里我应该传递什么种子值？
h.SetSeed(seed)
binary.Write(&h, binary.LittleEndian, key)
return m[h.Sum64()%uint64(SHARD_COUNT)]
}
英文:
I am using concurrent map from this repo which only uses string as the key and it doesn't have any implementation for key as integer so I tried implementing it by just replacing all string into int64 and modify the hashing function.
Here is the gist for that where key is integer. Below is how I am hashing int64 keys. Is this the right way to hash an int64 to get the right shard?
// GetShard returns shard under given key
func (m ConcurrentMap[V]) GetShard(key int64) *ConcurrentMapShared[V] {
// I assume the hashing function of Go's map is good enough
return m[key%int64(SHARD_COUNT)]
}
When I run this code I am getting - panic: runtime error: index out of range [-7] on my above return line in GetShard function.
Is there anything wrong in my hashing function implementation? Any example on what hashing algorithm to use here with my code will help me understand better.
Do I need to use murmurhash3 here on the key and then do mod on that? If yes, any example will be appreciated.
Update
So I should change my above GetShard method to like this -
// GetShard returns shard under given key
func (m ConcurrentMap) GetShard(key int64) *ConcurrentMapShared {
var h maphash.Hash
// what is the seed value I should pass here?
h.SetSeed(seed)
binary.Write(&h, binary.LittleEndian, key)
return m[h.Sum64()%uint64(SHARD_COUNT)]
}
答案1
得分: 4
你可以查看puzpuzpuz/xsync#Map进行比较。
m := xsync.NewMapOf[int64]()
m.Store(1, "bar")
v, ok := m.Load(1)
其中的hashUint64使用给定的种子计算K（IntegerConstraint）的哈希值。
// hashUint64使用给定的种子计算v的哈希值。
//
//lint:ignore U1000 在MapOf中使用
func hashUint64[K IntegerConstraint](seed maphash.Seed, k K) uint64 {
n := uint64(k)
// Java的Long标准哈希函数。
n = n ^ (n >> 32)
nseed := *(*uint64)(unsafe.Pointer(&seed))
// boost的hash_combine的64位变体。
nseed ^= n + 0x9e3779b97f4a7c15 + (nseed << 12) + (nseed >> 4)
return nseed
}
被NewTypedMapOf[K comparable, V any](hasher func(maphash.Seed, K) uint64) *MapOf[K, V]使用。
> 键使用hasher函数哈希为uint64。
> 强烈建议使用hash/maphash包来实现哈希函数。
> 参见示例。
英文:
You can check out for comparison puzpuzpuz/xsync#Map
m := xsync.NewMapOf[int64]()
m.Store(1, "bar")
v, ok := m.Load(1)
Its hashUint64 calculates a hash of K (IntegerConstraint) with the given seed.
// hashUint64 calculates a hash of v with the given seed.
//
//lint:ignore U1000 used in MapOf
func hashUint64[K IntegerConstraint](seed maphash.Seed, k K) uint64 {
n := uint64(k)
// Java's Long standard hash function.
n = n ^ (n >> 32)
nseed := *(*uint64)(unsafe.Pointer(&seed))
// 64-bit variation of boost's hash_combine.
nseed ^= n + 0x9e3779b97f4a7c15 + (nseed << 12) + (nseed >> 4)
return nseed
}
Used by NewTypedMapOf[K comparable, V any](hasher func(maphash.Seed, K) uint64) *MapOf[K, V]
> Keys are hashed to uint64 using the hasher function.
> It is strongly recommended to use the hash/maphash package to implement hasher.
> See example.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论