使用Go泛型的哈希函数

huangapple go评论81阅读模式
英文:

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&lt;type&gt;{}(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 (
&quot;hash/fnv&quot;
)
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(&quot;hash function of this type not implemented&quot;)
}
}
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 (
&quot;testing&quot;
)
func BenchmarkHashStringTypeSwitch(b *testing.B) {
s := &quot;func (this *LRUCache) Get(key int) int {&quot;
for i := 0; i &lt; b.N; i++ {
Hash(s)
}
}
func BenchmarkHashString(b *testing.B) {
s := &quot;func (this *LRUCache) Get(key int) int {&quot;
for i := 0; i &lt; b.N; i++ {
stringHash(s)
}
}
func BenchmarkHashIntTypeSwitch(b *testing.B) {
n := 123456
for i := 0; i &lt; b.N; i++ {
Hash(n)
}
}
func BenchmarkHashInt(b *testing.B) {
n := 123456
for i := 0; i &lt; b.N; i++ {
intHash(n)
}
}
func BenchmarkGetHashInt(b *testing.B) {
n := 123456
for i := 0; i &lt; b.N; i++ {
GetHash(Hint(n))
}
}
func BenchmarkGetHashIntHalfConvert(b *testing.B) {
var n Hint = 123456
for i := 0; i &lt; b.N; i++ {
GetHash(n)
}
}
func BenchmarkGetHashIntMethod(b *testing.B) {
n := 123456
for i := 0; i &lt; b.N; i++ {
Hint(n).Hash()
}
}
func BenchmarkGetHashIntNoInfer(b *testing.B) {
n := 123456
f := GetHash[Hint]
for i := 0; i &lt; b.N; i++ {
f(Hint(n))
}
}
func BenchmarkGetHashString(b *testing.B) {
s := &quot;func (this *LRUCache) Get(key int) int {&quot;
for i := 0; i &lt; 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 &quot;fmt&quot;
type hint int
type hstring string
type Hasher interface {
Hash() []byte
}
func (h hint) Hash() []byte {
return []byte(&quot;hint&quot;)
}
func (h hstring) Hash() []byte {
return []byte(&quot;hstring&quot;)
}
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 = &quot;111111&quot;
fmt.Printf(&quot;%s\n&quot;, GetHash(a))
fmt.Printf(&quot;%s\n&quot;, GetHash(b))
}

huangapple
  • 本文由 发表于 2023年1月6日 10:05:13
  • 转载请务必保留本文链接:https://go.coder-hub.com/75026231.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定