Go
by Andy Arthur

机智！生抠 map的哈希函数

前一段时间我尝试为orcaman/concurrent-map实现泛型的支持时，遭遇到为任意类型计算哈希值的问题，现在这个库也自己实现了泛型支持，你也可以看到它的哈希也没有好的办法，只能提供出一个函数对象让用户自己实现。当然你也可以参考[cornelk/hashmap/blob/36b3b9c2b7ec993f1ef12a6957d45826aca726e6/util_hash.go#L49)中的实现，但是它的实现既不全面也不高效？

我们经常会在一些场景，比如特定的数据结构、cache等场景中使用这样一个哈希函数，那么如何为任务类型实现一个优雅高效的hash函数呢？其实Go运行时中map中就实现了。回想一下内建的map是不是支持泛型的？它的key可以是comparable类型(包括接口类型),内部实现中会把此类型的key计算一个哈希值，能不能吧它的hash函数拿出来使用？很遗憾，Go官方并没有想暴露出来这样的hasher的想法，它的代码也是不容易抽取整理成一个hasher函数。

今天看到一篇文章Hacking Go's Runtime with Generics,提供了一种方法，脑洞大开。没看之前确实没想到，看到之后才发觉这么简单有效，接下来我翻译了这么文章，赶快学习吧。

今天的博客是关于maphash的，这是一个用于哈希任意Go类型(comparable)。我们将深入探讨它是如何实现的，以及一些有趣的 Golang 运行时花絮。

散列所有类型

maphash是一个超级小的库，旨在达到一个目的：将 Golang 内置哈希的强大功能交到开发人员手中。 任意 Golang 类型可以使用maphash.Hasher进行哈希处理。 API 如下：

1
2
3
4
5
6
7
8
9
10
11
type Hasher[K comparable] struct {
    ...
}
func NewHasher[K comparable]() Hasher[K] {
    ...
}
func (h Hasher[K]) Hash(key K) uint64 {
    ...
}

在Go语言中，comparable类型约束是所有实现了操作符==和!=类型的集合(接口类型目前还不在这个集合中，但是后续的Go版本接口也很快满足comparable类型约束了)，这包括所有scalar 类型、channel、接口、数组和字段类型是comparable的结构。基本上maphash中你可以用任何类型作为map的key。

那么有什么意义呢？这个包的动机来自于为 Dolt 实现并发的、stripe-locked的缓存。设计看起来像这样：

1
2
3
4
type Cache[K comparable, V any] struct {
    stripes [64]map[K]V
    locks   [64]sync.RWLock
}

使用泛型，我们可以创建一个由内置map支持的灵活的容器类。但是，当我们尝试实现这个类的访问器方法时，我们陷入了编写泛型函数来选择每个键所属的stripe的困境：

1
2
3
4
// getStripe returns the stripe that |key| belongs to.
func (c Cache[K, V]) getStripe(key K) int8 {
    ???
}

我们这里需要的是泛型的哈希函数,为comparable类型K提供哈希算法。

背景

希望Go标准库提供一个公开的通用哈希函数的想法由来已久。 Golang团队的Byran Mills 2017年最早就提出了这个想法#21195， 建议添加一个内置函数去哈希comparable类型，方便实现自定义容器和数据结构。该提案认为，Golang开发人员在编写基于哈希的数据结构(Tries、concurrent hash map)时， 被迫多大量的额外的工作。 想要高效的基于哈希数据结构的开发人员只有使用内置的map。

当这个问题最初在 2017 年创建时，Golang 没有泛型，因此提议的接口缺少具体类型：

1
func Local(interface{}) uintptr

这个 API 起初似乎是合理的，但是因为没有具体的类型信息，编译器没法高效的实现它。Go内建map能够高效实现的秘密在于它为各种类型产生了定制的哈希函数custom hash functions。产生的哈希函数知道怎么去遍历指定的类型，并能利用硬件支持的 AES指令加速哈希。不幸的是，所有的模仿都隐藏在运行时中，编译器在编译的时候才去处理。

在 Go 1.19 中，标准库增加了maphash包，核暴露了哈希字符串和字节切片的能力，可以利用AES指令加速。这些添加当然是好事，但是它们仍然缺乏编写通用容器类型所需的灵活性，今年早些时候#54670提议扩展这个包支持任意的comparable类型，但是依照Go团队的风格，"不是我的提案都不高优，我的提案最高优"，这个提案就一直挂在哪里。目前我们只有一个选择，通过黑客的方式自己实现。

破解运行时

我们已经知道，编译器有能力生成这样一个哈希函数，更进一步，我们知道使用map[T]V会触发编译器生成一个为类型T哈希的函数，这个哈希函数可以通过maptype类型得到:

1
2
3
4
5
6
7
8
9
10
11
12
type maptype struct {
    typ    _type
    key    *_type
    elem   *_type
    bucket *_type // internal type representing a hash bucket
    // function for hashing keys (ptr to key, seed) -> hash
    hasher     func(unsafe.Pointer, uintptr) uintptr
    keysize    uint8  // size of key slot
    elemsize   uint8  // size of elem slot
    bucketsize uint16 // size of bucket
    flags      uint32
}

使用map时会传入*maptype和*hmap实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// v := map[k]
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
}
// v, ok := map[k]
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
    ...
}
// delete(map, k)
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
    ...
}

So how can we get access to this? Using Golang's unsafe package, we can work around the type system and get access to the private fields within t找到，hese runtime types. This is what it looks like in our new maphash package:

妥了，目标已经找到，下一步是我们如何才能获得这个哈希函数呢？使用 Golang 的unsafe包，下面的代码就是我们的maphash库中的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func getRuntimeHasher[K comparable]() (h hashfn, seed uintptr) {
    a := any(make(map[K]struct{}))
    i := (*mapiface)(unsafe.Pointer(&a))
    h, seed = i.typ.hasher, uintptr(i.val.hash0)
    return
}
type hashfn func(unsafe.Pointer, uintptr) uintptr
type mapiface struct {
    typ *maptype
    val *hmap
}
// mirrors go/src/runtime/type.go
type maptype struct {
    typ    _type
    key    *_type
    elem   *_type
    bucket *_type
    // function for hashing keys (ptr to key, seed) -> hash
    hasher     func(unsafe.Pointer, uintptr) uintptr
    keysize    uint8
    elemsize   uint8
    bucketsize uint16
    flags      uint32
}

In getRuntimeHasherK comparable, start by declaring a map[K]struct{}. This declaration makes the compiler create the hash function we want. Next we cast our map to type any, forcing the compiler to add additional metadata do describe the dynamic type of the variable a. For maps, this metadata is a pointer to a maptype object, which is just what we need to access the hash function! Using an unsafe.Pointer we can cast a to mapiface (a runtime type), get our hasher, and construct a maphash.Hasher:

在getRuntimeHasher[K comparable]()的开始部分，声明了一个map[K]struct{}。这个声明促使编译器创建我们所需要的哈希函数。下一步我们把这个map转换成any类型，强制编译器增加一些元数据信息。对于map类型，这些元数据是一个指针，指向 maptype类型，这个类型正式我们能拿到哈希函数的类型!

1
2
3
4
5
6
7
8
9
type Hasher[K comparable] struct {
    hash hashfn
    seed uintptr
}
func NewHasher[K comparable]() Hasher[K] {
    h, s := getRuntimeHasher[K]()
    return Hasher[K]{hash: h, seed: s}
}

Using a maphash.Hasher we can create hash-based datastructures keyed by UUIDs, time.Time, or any other comparable type. And thanks to the compiler, Hasher is able to take advantage of optimized AES instructions. Hashing a string with maphash is just as fast as the standard library version!

使用maphash.Hasher我们可以创建基于哈希的数据结构，key可以是 UUID、time.Time或者其它comparable类型。借助于编译器，这个Hasher还能充分利用 AES 指令，哈希字符串的性能和标准库的一样快:

1
2
3
4
5
6
7
8
9
10
goos: darwin
goarch: amd64
pkg: github.com/dolthub/maphash
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkCompareStringHasher
BenchmarkCompareStringHasher/string_hasher
BenchmarkCompareStringHasher/string_hasher-12         	237970230	         5.341 ns/op	       0 B/op	       0 allocs/op
BenchmarkCompareStringHasher/std_string_hasher
BenchmarkCompareStringHasher/std_string_hasher-12     	207972664	         5.759 ns/op	       0 B/op	       0 allocs/op
PASS

一个虚心的请求

如果你认为这段代码是对Golang的滥用，我同意你的看法。maphash的实现，就像map一样，是和运行时紧紧耦合的。虽然最近几个Go的版本中，map类型相对稳定，但是任何有影响的改变都得移植到maphash库中。相当脆弱！maphash使用build tags限制此库使用的Go版本为Go 1.18和 Go 1.19，未来的版本我们也会扩展支持。

如果您认为有更好的方法可以做到这一点，我再次同意您的看法！我虚心的提出一个要求，希望你能到#54670评论，并upvote支持一下：

1
2
3
4
// Comparable returns the hash of comparable value v with the given seed
// such that Comparable(s, v1) == Comparable(s, v2) if v1 == v2.
// If v contains a floating-point NaN, then the hash is non-deterministically random.
func Comparable[T comparable](seed Seed, v T) uint64