概要

hash/maphashパッケージに、ハッシュベースのデータ構造(ハッシュテーブルやBloomフィルタなど)とその要素の型との間の契約を定めるHasher[T]インターフェースが追加された。

type Hasher[T any] interface {
	Hash(*Hash, T)
	Equal(x, y T) bool
}

Hasherはハッシュ関数(Hash)と同値関係(Equal)を1つの型にまとめたものであり、Goの組み込みmapでは扱えない非比較可能型をハッシュテーブルのキーとして使えるようにするほか、比較可能型に対しても==とは異なる同値関係(大文字小文字を無視した文字列比較など)を定義できるようにする。あわせて、比較可能型向けの標準実装であるComparableHasher[T comparable]も追加され、Equal(x, y)はx == yと、Hashは既存のWriteComparableと整合するように定義されている。

Hasherはステートレスでなければならず、そのゼロ値も有効でなければならない(典型的には空структのようになる)。

導入経緯

本提案は、go/types.Hash関数の提案がきっかけとなった。types.Type向けのカスタムハッシュ関数を用意する際に、「Goにおけるカスタムハッシュ関数のシグネチャの将来的な規約は何か」という問いが持ち上がり、それを独立した提案として切り出したのが本issue(golang/go#70471)である。

ハッシュテーブルが単一の(予測可能な)ハッシュ関数しか持たない場合、攻撃者が同じハッシュ値に衝突する入力を大量に送り込む「ハッシュフラッディング」というDoS攻撃に弱くなる。hash/maphashパッケージ自体が、ランダムなSeedによってハッシュ関数を変化させることでこれに対処しているため、議論は「カスタムハッシュ関数もこのmaphashの考え方に乗せるにはどうすればよいか」という方向で進んだ。

議論のハイライト

• 当初検討されたtype HashFunc[T any] func(T) uint64のような素朴な関数型は、シードを組み込む余地がなく「不十分」との指摘をすぐに受けた。
• ハッシュとイコールをまとめたHasher[T] interface { Hash(T) uint64; Equal(T, T) bool }という案が示された後、シードの受け渡し方法について長い議論が続いた。maphash.Seedを引数に取る案は、再帰的なハッシュ計算(構造体の中の構造体をハッシュする場合など)がしづらいという理由から、最終的に*maphash.Hashを直接渡す案(いわゆる「option 2b」)に落ち着いた。
• ハッシュテーブル側がHasherをどう保持するかについても議論があった。フィールドとして動的に持つ案(インターフェース経由の呼び出し)は、Getのたびに*maphash.Hashがヒープにエスケープしてしまう問題が指摘され、Hasherを型パラメータとして静的に持つ案(HashTable[T any, H Hasher[T]])が比較検討された。
• 一度は動的インターフェース版として受理されたが、型パラメータを1つ増やす必要があることへの懸念から議論が再開され、@adonovanによるベンチマーク測定の結果、静的な型パラメータ版の方がアロケーションを大きく減らせることが確認され、最終的に型パラメータとして持つ設計に回帰した。
• 「素の型自身にHash/Equalメソッドを持たせる」案(sort.Interfaceに似た設計)も検討されたが、型を制御できない場合やインターフェース型・複数の同値関係を持つ型(まさにtypes.Type)への対応が難しいという理由で見送られた。
• 比較可能型向けの標準実装の命名はDefault→BasicHasher→最終的にComparableHasherと変遷した。
• 提案自体は複数回「accepted」となった後に再オープンされる展開を経ており、最終的にHasher[T]とComparableHasher[T comparable]の組み合わせで受理された。

使用例

Before

package main

import (
	"fmt"
	"hash/maphash"
)

type Point struct {
	X, Y int
}

// 共通のインターフェースがなかったため、型ごとに独自のハッシュ関数を用意していた。
func hashPoint(seed maphash.Seed, p Point) uint64 {
	var h maphash.Hash
	h.SetSeed(seed)
	maphash.WriteComparable(&h, p.X)
	maphash.WriteComparable(&h, p.Y)
	return h.Sum64()
}

func main() {
	seed := maphash.MakeSeed()
	p := Point{X: 1, Y: 2}
	fmt.Println(hashPoint(seed, p))
}

After

package main

import (
	"fmt"
	"hash/maphash"
)

type Point struct {
	X, Y int
}

// PointHasher は maphash.Hasher[Point] を実装する。
type PointHasher struct{}

func (PointHasher) Hash(h *maphash.Hash, p Point) {
	maphash.WriteComparable(h, p.X)
	maphash.WriteComparable(h, p.Y)
}

func (PointHasher) Equal(a, b Point) bool {
	return a == b
}

func main() {
	var h maphash.Hash
	h.SetSeed(maphash.MakeSeed())

	var hasher PointHasher
	p := Point{X: 1, Y: 2}
	hasher.Hash(&h, p)
	fmt.Println(h.Sum64())

	// 比較可能型であれば ComparableHasher をそのまま利用できる。
	var ch maphash.ComparableHasher[int]
	var h2 maphash.Hash
	h2.SetSeed(maphash.MakeSeed())
	ch.Hash(&h2, 42)
	fmt.Println(ch.Equal(42, 42))
}

実装解説

実装はsrc/hash/maphash/hasher.goにある。Hasher[T any]はHash(*Hash, T)とEqual(x, y T) boolの2メソッドのみを持つ小さなインターフェースとして定義されている。

標準実装ComparableHasher[T comparable]は同じファイルのhasher.go:134にあり、フィールドとして_ [0]func(T)を持つのみの空struct相当の型である。このフィールドは実データを持たず、ComparableHasher[X]同士の比較やインスタンス化を禁止し、またComparableHasher[X]からComparableHasher[Y]への変換を妨げるための工夫である。そのHash/Equalメソッドの実体は、既存のWriteComparable関数と==演算子への単純な委譲になっている。

Hasherのドキュメントコメント自体にも、集合のような順序のないデータ型を子ハッシュのSeedを揃えつつXORで合成してハッシュする例など、良いハッシュ関数を書くための指針が詳しく書かれている点が特徴的である。