英文:
Hash function with Go generics
问题
我正在学习Go语言1.18版本引入的泛型,并且想要实现一个返回任何可哈希对象的哈希函数。理想情况下,它应该与C++中的std::hash
模板类似,例如std::hash<type>{}(x)
。
我已经定义了一个Hashable接口:
type Hashable interface {int | string}
然而,我不知道接下来该怎么做。因为我希望不同类型(如int和string)有不同的行为,并且我希望实现在编译时确定,以避免任何运行时类型检查的开销。有没有办法可以使用Go泛型来实现这一点,就像在C++ STL中一样?
编辑:
我对@Para发布的解决方案进行了基准测试,并发现它比使用类型切换的实现效率低,即使禁用了类型推断。我猜在Go中调用泛型函数会有一些运行时开销。以下是基准测试的代码。
hash.go
package hash
import (
"hash/fnv"
)
type Hashable interface {
int | string
}
func Hash(x any) int {
switch v := x.(type) {
case int:
return v
case string:
return stringHash(v)
default:
panic("hash function of this type not implemented")
}
}
func intHash(x int) int {
return x
}
func stringHash(x string) int {
h := fnv.New32a()
h.Write([]byte(x))
return int(h.Sum32())
}
type Hint int
type Hstring string
type Hasher interface {
Hash() int
}
func (x Hint) Hash() int {
return int(x)
}
func (x Hstring) Hash() int {
h := fnv.New32a()
h.Write([]byte(x))
return int(h.Sum32())
}
type HashableAlias interface {
Hint | Hstring
Hasher
}
func GetHash[T HashableAlias](h T) int {
return h.Hash()
}
hash_test.go
package hash
import (
"testing"
)
func BenchmarkHashStringTypeSwitch(b *testing.B) {
s := "func (this *LRUCache) Get(key int) int {"
for i := 0; i < b.N; i++ {
Hash(s)
}
}
func BenchmarkHashString(b *testing.B) {
s := "func (this *LRUCache) Get(key int) int {"
for i := 0; i < b.N; i++ {
stringHash(s)
}
}
func BenchmarkHashIntTypeSwitch(b *testing.B) {
n := 123456
for i := 0; i < b.N; i++ {
Hash(n)
}
}
func BenchmarkHashInt(b *testing.B) {
n := 123456
for i := 0; i < b.N; i++ {
intHash(n)
}
}
func BenchmarkGetHashInt(b *testing.B) {
n := 123456
for i := 0; i < b.N; i++ {
GetHash(Hint(n))
}
}
func BenchmarkGetHashIntHalfConvert(b *testing.B) {
var n Hint = 123456
for i := 0; i < b.N; i++ {
GetHash(n)
}
}
func BenchmarkGetHashIntMethod(b *testing.B) {
n := 123456
for i := 0; i < b.N; i++ {
Hint(n).Hash()
}
}
func BenchmarkGetHashIntNoInfer(b *testing.B) {
n := 123456
f := GetHash[Hint]
for i := 0; i < b.N; i++ {
f(Hint(n))
}
}
func BenchmarkGetHashString(b *testing.B) {
s := "func (this *LRUCache) Get(key int) int {"
for i := 0; i < b.N; i++ {
GetHash(Hstring(s))
}
}
基准测试输出(go version go1.19.4 darwin/arm64)
BenchmarkExtendibleHashTable-10 9066850 148.8 ns/op
BenchmarkHashStringTypeSwitch-10 26299448 43.56 ns/op
BenchmarkHashString-10 25259280 43.05 ns/op
BenchmarkHashIntTypeSwitch-10 1000000000 0.6236 ns/op
BenchmarkHashInt-10 1000000000 0.3114 ns/op
BenchmarkGetHashInt-10 552110401 2.109 ns/op
BenchmarkGetHashIntHalfConvert-10 576661430 2.125 ns/op
BenchmarkGetHashIntMethod-10 1000000000 0.3118 ns/op
BenchmarkGetHashIntNoInfer-10 560186821 2.119 ns/op
BenchmarkGetHashString-10 26585163 44.29 ns/op
英文:
I'm learning Go generics introduced in version 1.18 and want to implement a hash function that returns a hash value of any hashable object. Ideally it would work similarly as the std::hash
template in C++, like std::hash<type>{}(x)
.
I already defined a Hashable interface:
type Hashable interface {int | string}
However, I don't know how to proceed next. Since I want different behaviors for different types such as int and string, and I want the implementation to be determined in compile-time to avoid any runtime type-checking overhead. Is there any way I can do this using Go generics just like in C++ STL?
EDIT:
I benchmarked the solution posted by @Para, and I found it less efficient than a type-switch implementation, even when type inference is disabled. I guess there is some runtime overhead calling generic functions in Go. Here is the code for benchmark.
hash.go
package hash
import (
"hash/fnv"
)
type Hashable interface {
int | string
}
func Hash(x any) int {
switch v := x.(type) {
case int:
return v
case string:
return stringHash(v)
default:
panic("hash function of this type not implemented")
}
}
func intHash(x int) int {
return x
}
func stringHash(x string) int {
h := fnv.New32a()
h.Write([]byte(x))
return int(h.Sum32())
}
type Hint int
type Hstring string
type Hasher interface {
Hash() int
}
func (x Hint) Hash() int {
return int(x)
}
func (x Hstring) Hash() int {
h := fnv.New32a()
h.Write([]byte(x))
return int(h.Sum32())
}
type HashableAlias interface {
Hint | Hstring
Hasher
}
func GetHash[T HashableAlias](h T) int {
return h.Hash()
}
hash_test.go
package hash
import (
"testing"
)
func BenchmarkHashStringTypeSwitch(b *testing.B) {
s := "func (this *LRUCache) Get(key int) int {"
for i := 0; i < b.N; i++ {
Hash(s)
}
}
func BenchmarkHashString(b *testing.B) {
s := "func (this *LRUCache) Get(key int) int {"
for i := 0; i < b.N; i++ {
stringHash(s)
}
}
func BenchmarkHashIntTypeSwitch(b *testing.B) {
n := 123456
for i := 0; i < b.N; i++ {
Hash(n)
}
}
func BenchmarkHashInt(b *testing.B) {
n := 123456
for i := 0; i < b.N; i++ {
intHash(n)
}
}
func BenchmarkGetHashInt(b *testing.B) {
n := 123456
for i := 0; i < b.N; i++ {
GetHash(Hint(n))
}
}
func BenchmarkGetHashIntHalfConvert(b *testing.B) {
var n Hint = 123456
for i := 0; i < b.N; i++ {
GetHash(n)
}
}
func BenchmarkGetHashIntMethod(b *testing.B) {
n := 123456
for i := 0; i < b.N; i++ {
Hint(n).Hash()
}
}
func BenchmarkGetHashIntNoInfer(b *testing.B) {
n := 123456
f := GetHash[Hint]
for i := 0; i < b.N; i++ {
f(Hint(n))
}
}
func BenchmarkGetHashString(b *testing.B) {
s := "func (this *LRUCache) Get(key int) int {"
for i := 0; i < b.N; i++ {
GetHash(Hstring(s))
}
}
benchmark output (go version go1.19.4 darwin/arm64)
BenchmarkExtendibleHashTable-10 9066850 148.8 ns/op
BenchmarkHashStringTypeSwitch-10 26299448 43.56 ns/op
BenchmarkHashString-10 25259280 43.05 ns/op
BenchmarkHashIntTypeSwitch-10 1000000000 0.6236 ns/op
BenchmarkHashInt-10 1000000000 0.3114 ns/op
BenchmarkGetHashInt-10 552110401 2.109 ns/op
BenchmarkGetHashIntHalfConvert-10 576661430 2.125 ns/op
BenchmarkGetHashIntMethod-10 1000000000 0.3118 ns/op
BenchmarkGetHashIntNoInfer-10 560186821 2.119 ns/op
BenchmarkGetHashString-10 26585163 44.29 ns/op
答案1
得分: 3
package main
import "fmt"
type hint int
type hstring string
type Hasher interface {
Hash() []byte
}
func (h hint) Hash() []byte {
return []byte("hint")
}
func (h hstring) Hash() []byte {
return []byte("hstring")
}
type Hashable interface {
hint | hstring
Hasher
}
func GetHash[T Hashable](h T) []byte {
return h.Hash()
}
func main() {
var a hint = 1
var b hstring = "111111"
fmt.Printf("%s\n", GetHash(a))
fmt.Printf("%s\n", GetHash(b))
}
package main
import "fmt"
type hint int
type hstring string
type Hasher interface {
Hash() []byte
}
func (h hint) Hash() []byte {
return []byte("hint")
}
func (h hstring) Hash() []byte {
return []byte("hstring")
}
type Hashable interface {
hint | hstring
Hasher
}
func GetHash[T Hashable](h T) []byte {
return h.Hash()
}
func main() {
var a hint = 1
var b hstring = "111111"
fmt.Printf("%s\n", GetHash(a))
fmt.Printf("%s\n", GetHash(b))
}
英文:
package main
import "fmt"
type hint int
type hstring string
type Hasher interface {
Hash() []byte
}
func (h hint) Hash() []byte {
return []byte("hint")
}
func (h hstring) Hash() []byte {
return []byte("hstring")
}
type Hashable interface {
hint | hstring
Hasher
}
func GetHash[T Hashable](h T) []byte {
return h.Hash()
}
func main() {
var a hint = 1
var b hstring = "111111"
fmt.Printf("%s\n", GetHash(a))
fmt.Printf("%s\n", GetHash(b))
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论