メインコンテンツへスキップ

Go Proposal Weekly Digest

Go言語のproposal更新を毎週お届け

#69559likely_accept

golang.org/x/exp/collection/hashed: Map, a generic hash table with custom hash function and equivalence relation

ステータス変更: active likely_accept

要約

AIによる要約であり、誤りを含む場合があります。

概要

golang.org/x/exp/collection/hashed パッケージに、汎用のハッシュテーブル型 Map[K, V] を追加する提案です。組み込みの map はキーを == でしか比較できませんが、Map ではハッシュ関数とキーの同値関係（どのキー同士を「同じ」とみなすか）を利用者が指定できます。

ステータス変更

active → likely_accept
2024年9月に始まった議論は、Collections ワーキンググループ（umbrella issue #80590）でまとめられました。API は段階的に絞り込まれ、2026年10月7日に @jba が最終版を提示しています。配置先は当初案の標準ライブラリ container/hash から x/exp に移り、SetAll・ContainsAll・DeleteAll は削除されました。名前は At が Get に、旧 Get が Lookup に変わっています。直前の指摘は、ドキュメントにある「set 操作は collection/set パッケージのヘルパーを使え」という記述が古いのではないか（@aclements）という点だけでした。@adonovan もこれを誤記と認めています。これ以上の大きな反対がないことから、@aclements がレビューグループを代表して likely accept を宣言しました。

技術的背景

現状の問題点

組み込みの map[K]V は、K が comparable（== で比較できる型）で、比較方法も == である場合しか使えません。次のようなケースには対応できません。

  • go/types の types.Type。構造的に同一な型でも別のポインタになるため、== では比較できず types.Identical で比べる必要があります。
  • 大文字・小文字を区別しない文字列キー
  • スライスを含む構造体など、comparable でないキー
    これまでは x/tools/go/types/typeutil.Map のような専用実装を作るか、キーを正規化した文字列に変換して map に入れるしかありませんでした（#69420 が出発点）。

提案された解決策

package hashed // golang.org/x/exp/collection/hashed
func NewMap[K, V any](hasher maphash.Hasher[K]) *Map[K, V]
func (m *Map[K, V]) All() iter.Seq2[K, V]
func (m *Map[K, V]) Clear()
func (m *Map[K, V]) Clone() *Map[K, V]
func (m *Map[K, V]) Contains(key K) bool
func (m *Map[K, V]) Delete(key K) (prev V, deleted bool)
func (m *Map[K, V]) DeleteFunc(del func(K, V) bool) bool
func (m *Map[K, V]) Get(key K) V
func (m *Map[K, V]) Keys() iter.Seq[K]
func (m *Map[K, V]) Len() int
func (m *Map[K, V]) Lookup(key K) (V, bool)
func (m *Map[K, V]) Set(key K, value V) (prev V, present bool)
func (m *Map[K, V]) String() string
func (m *Map[K, V]) Values() iter.Seq[V]
  • ハッシュ関数と同値関係は、#70471 で標準化された maphash.Hasher[K] インターフェース（Hash(*maphash.Hash, K) と Equal(K, K) bool）で渡します。シードは Map 側が管理するため、ハッシュフラッディング攻撃（同じハッシュ値になるキーを大量に送り込んで性能を落とす DoS 攻撃）への耐性があります。
  • NewMap で作成する必要があります。ゼロ値や nil ポインタは使えず、コピーには Clone を使います。
  • 反復順序は組み込み map と同じくランダムであることが保証されます。反復中の変更も組み込み map と同じ意味論で許されます。一方、並行アクセスは禁止です。
  • String だけは、順序は規定しないものの、決定的な（毎回同じ）順序で出力します。

これによって何ができるようになるか

  • 型チェッカーやツールの開発: types.Type をキーにした表を、types.Identical に沿って扱えます。typeutil.Map を汎用の部品で置き換えられます。
  • 独自の同値関係を持つキー: 大文字・小文字を無視する文字列、正規化したパス、浮動小数点の誤差を許容する座標などをキーにできます。
  • comparable でないキー: スライスを含む構造体なども、Hasher を書けばキーとして使えます。
    なお、ドキュメントには「通常の comparable 型と == で済むなら組み込み map を使うこと」と明記されています。

コード例

// Before: キーを正規化した文字列に変換して組み込み map に入れる
m := map[string]int{}
m[strings.ToLower("Foo")] = 1
_, ok := m[strings.ToLower("FOO")] // 毎回の変換が必要で、元のキーも失われる
// After: 同値関係を Hasher として定義する
type foldHasher struct{}
func (foldHasher) Hash(h *maphash.Hash, s string) { h.WriteString(strings.ToLower(s)) }
func (foldHasher) Equal(a, b string) bool         { return strings.EqualFold(a, b) }
m := hashed.NewMap[string, int](foldHasher{})
m.Set("Foo", 1)
v, ok := m.Lookup("FOO") // v == 1, ok == true
for k, v := range m.All() {
	fmt.Println(k, v) // 元のキー "Foo" を保持している
}

議論のハイライト

  • 第3の型パラメータ H の却下: 当初は Map[K, V, H Hasher[K]] として静的に呼び出す案がありました。目的は、152バイトの maphash.Hash がエスケープして毎回ヒープ確保されるのを避けることです。しかし、Go のジェネリクス実装（stenciling）ではこの方法でも解決しませんでした。さらに、実装の詳細が型に漏れて C++ の allocator 引数のように煩雑になる、という理由で却下されました。sync.Pool で Hash を再利用すれば、型特化した実装との性能差は10%以内に収まることも確認されています。
  • Hasher をゼロ値にしない理由: @cherrymui が、Hasher が初期化時に状態を持つべきケースを示しました。そのため Hasher は値としてコンストラクタに渡す設計になり、Map のゼロ値は無効になりました。
  • メソッド名: @benhoyt らの提案に従い、reflect.StructTag の Get/Lookup や os.Getenv/LookupEnv にならって、ゼロ値を返す Get と ok も返す Lookup のペアにしました。
  • ヘルパーの削減: SetAll/ContainsAll/DeleteAll は普通の for ループで代替できるという指摘を受けて削除されました。NewMap のサイズヒントも「たいてい間違っている」という理由で採用されていません。Grow(n) メソッドの追加案（#81698 との整合）は提案されましたが、未解決です。
  • JSON 対応: json.Marshaler を実装するか、reflect.DeepEqual にどう対応するかも議論されました。結論としては、今回のスコープには含まれていません。

関連リンク