関連記事
GitHub - devlights/blog-summary: ブログ「いろいろ備忘録日記」のまとめ
概要
以下、自分用のメモです。
Goには、C#とかJavaのようにHashSetの実装は用意されていません。基本的にmapがあるので、それのキーだけ利用してしまえば済むというのもあります。
基本こんな感じですね。
set := map[int]struct{} set[1] = struct{}{} set[2] = struct{}{}
Value側をstruct{}にしたりboolにしたりは好みの問題。実際にはちゃんとAdd関数とか用意したりする。
ただ、何度もこんな感じで書いてると流石に面倒くさくなってくるので、自分用ですがリポジトリ作ってアップしておきました。
GitHub - devlights/hashset: Go言語用の汎用的なHashSet実装です。
まあ、世の中もっと便利な実装もありますが、自分で利用する分にはこれで充分です。
サンプル
hashset.go
package hashset import "iter" type ( // Set は Go の map 型を使用したハッシュ集合データ構造を表します。 // ゼロ値は使用可能ではありません。新しい Set を作成するには New() を使用してください。 Set[T comparable] map[T]struct{} ) // New は新しい空の Set を作成して返します。 func New[T comparable]() Set[T] { return make(Set[T]) } // NewWithCapacity は指定された初期容量で新しい空の Set を作成して返します。 // 概算サイズが分かっている場合、メモリ割り当てを削減するのに役立ちます。 func NewWithCapacity[T comparable](capacity int) Set[T] { return make(Set[T], capacity) } // NewFromSlice は指定されたスライスから一意の要素をすべて含む新しい Set を作成して返します。 func NewFromSlice[T comparable](items []T) Set[T] { set := make(Set[T], len(items)) for _, item := range items { set[item] = struct{}{} } return set } // Add は集合に要素を挿入します。 func (s Set[T]) Add(item T) { s[item] = struct{}{} } // AddAll は指定されたスライスのすべての要素を集合に挿入します。 func (s Set[T]) AddAll(items []T) { for _, item := range items { s[item] = struct{}{} } } // Remove は集合から要素を削除します。 func (s Set[T]) Remove(item T) { delete(s, item) } // RemoveAll は指定されたスライスのすべての要素を集合から削除します。 func (s Set[T]) RemoveAll(items []T) { for _, item := range items { delete(s, item) } } // Contains は要素が集合に存在するかどうかを報告します。 func (s Set[T]) Contains(item T) bool { _, exists := s[item] return exists } // ContainsAll は指定されたスライスのすべての要素が集合に存在するかどうかを報告します。 // すべての要素が存在する場合は true、そうでなければ false を返します。 func (s Set[T]) ContainsAll(items []T) bool { for _, item := range items { if !s.Contains(item) { return false } } return true } // ContainsAny は指定されたスライスのいずれかの要素が集合に存在するかどうかを報告します。 // 少なくとも一つの要素が存在する場合は true、そうでなければ false を返します。 func (s Set[T]) ContainsAny(items []T) bool { for _, item := range items { if s.Contains(item) { return true } } return false } // Size は集合内の要素数を返します。 func (s Set[T]) Size() int { return len(s) } // IsEmpty は集合が要素を含んでいないかどうかを報告します。 func (s Set[T]) IsEmpty() bool { return len(s) == 0 } // Clear は集合からすべての要素を削除し、空にします。 func (s Set[T]) Clear() { for k := range s { delete(s, k) } } // ToSlice は集合内のすべての要素を含むスライスを返します。 // 要素の順序は保証されません。 func (s Set[T]) ToSlice() []T { result := make([]T, 0, len(s)) for item := range s { result = append(result, item) } return result } // Clone は集合の浅いコピーを作成して返します。 func (s Set[T]) Clone() Set[T] { clone := make(Set[T], len(s)) for item := range s { clone[item] = struct{}{} } return clone } // Union は和集合を返します。 // 元の集合は変更されません。 func (s Set[T]) Union(other Set[T]) Set[T] { result := make(Set[T], len(s)+len(other)) // 現在の集合からすべての要素を追加 for item := range s { result[item] = struct{}{} } // 他の集合からすべての要素を追加 for item := range other { result[item] = struct{}{} } return result } // Intersection は積集合を返します。 // 元の集合は変更されません。 func (s Set[T]) Intersection(other Set[T]) Set[T] { result := New[T]() // パフォーマンス向上のため、小さい方の集合で反復 smaller, larger := s, other if len(other) < len(s) { smaller, larger = other, s } for item := range smaller { if larger.Contains(item) { result.Add(item) } } return result } // Difference は差集合を返します。 // 元の集合は変更されません。 func (s Set[T]) Difference(other Set[T]) Set[T] { result := New[T]() for item := range s { if !other.Contains(item) { result.Add(item) } } return result } // SymmetricDifference は対称差集合を返します。 // 元の集合は変更されません。 func (s Set[T]) SymmetricDifference(other Set[T]) Set[T] { result := New[T]() // s にあるが other にない要素を追加 for item := range s { if !other.Contains(item) { result.Add(item) } } // other にあるが s にない要素を追加 for item := range other { if !s.Contains(item) { result.Add(item) } } return result } // IsSubsetOf はこの集合が他の集合の部分集合かどうかを報告します。 // この集合のすべての要素が他の集合にも存在する場合は true を返します。 func (s Set[T]) IsSubsetOf(other Set[T]) bool { // 空集合はあらゆる集合の部分集合です if len(s) == 0 { return true } // この集合の方が大きい場合、部分集合になり得ません if len(s) > len(other) { return false } for item := range s { if !other.Contains(item) { return false } } return true } // IsSupersetOf はこの集合が他の集合の上位集合かどうかを報告します。 // 他の集合のすべての要素がこの集合にも存在する場合は true を返します。 func (s Set[T]) IsSupersetOf(other Set[T]) bool { return other.IsSubsetOf(s) } // IsDisjoint はこの集合と他の集合が共通要素を持たないかどうかを報告します。 func (s Set[T]) IsDisjoint(other Set[T]) bool { // パフォーマンス向上のため、小さい方の集合で反復 smaller, larger := s, other if len(other) < len(s) { smaller, larger = other, s } for item := range smaller { if larger.Contains(item) { return false } } return true } // Equal はこの集合と他の集合が完全に同じ要素を含んでいるかどうかを報告します。 // 両方の集合が同じサイズで同じ要素を含む場合は true を返します。 func (s Set[T]) Equal(other Set[T]) bool { // サイズが異なる集合は等しくありません if len(s) != len(other) { return false } // s のすべての要素が other にあるかチェック for item := range s { if !other.Contains(item) { return false } } return true } // All は集合のすべての要素を反復処理するための iter.Seq[T] を返します。 // これにより、for range ループで Set を直接反復処理できます。 // 例: for item := range mySet.All() { ... } func (s Set[T]) All() iter.Seq[T] { return func(yield func(T) bool) { for item := range s { if !yield(item) { return } } } }
Go 1.23でiterパッケージが導入されたので、ループさせる際に便利になりましたね。
使い方
リポジトリのREADMEをそのまま持ってきてますが、こんな感じ。
作成
// 空の集合を作成 set := hashset.New[string]() // 初期容量を指定して作成（パフォーマンス最適化のため） set := hashset.NewWithCapacity[string](100) // スライスから作成 items := []string{"apple", "banana", "orange"} set := hashset.NewFromSlice(items)
基本操作
// 単一要素を追加 set.Add("apple") // 複数要素を追加 set.AddAll([]string{"banana", "orange"}) // 単一要素を削除 set.Remove("apple") // 複数要素を削除 set.RemoveAll([]string{"banana", "orange"}) // 存在確認 exists := set.Contains("apple") // 複数要素の確認 allExist := set.ContainsAll([]string{"apple", "banana"}) anyExist := set.ContainsAny([]string{"apple", "grape"}) // サイズ取得と空かどうかの確認 size := set.Size() empty := set.IsEmpty() // すべての要素をクリア set.Clear()
変換と複製
// スライスに変換 slice := set.ToSlice() // コピーを作成 clone := set.Clone()
集合演算
set1 := hashset.NewFromSlice([]string{"apple", "banana"}) set2 := hashset.NewFromSlice([]string{"banana", "orange"}) // 和集合 (A ∪ B) union := set1.Union(set2) // {"apple", "banana", "orange"} // 積集合 (A ∩ B) intersection := set1.Intersection(set2) // {"banana"} // 差集合 (A - B) difference := set1.Difference(set2) // {"apple"} // 対称差集合 ((A ∪ B) - (A ∩ B)) symDiff := set1.SymmetricDifference(set2) // {"apple", "orange"}
集合関係
set1 := hashset.NewFromSlice([]string{"apple", "banana"}) set2 := hashset.NewFromSlice([]string{"apple", "banana", "orange"}) // set1がset2の部分集合かどうかを確認 isSubset := set1.IsSubsetOf(set2) // true // set2がset1の上位集合かどうかを確認 isSuperset := set2.IsSupersetOf(set1) // true // 集合が共通要素を持たないかどうかを確認 disjoint := set1.IsDisjoint(hashset.NewFromSlice([]string{"grape", "kiwi"})) // true // 集合が等しいかどうかを確認 equal := set1.Equal(set1.Clone()) // true
反復処理
// 要素を反復処理 for item := range set.All() { fmt.Println(item) }
共通要素の検索
users1 := hashset.NewFromSlice([]string{"alice", "bob", "charlie"}) users2 := hashset.NewFromSlice([]string{"bob", "david", "eve"}) users3 := hashset.NewFromSlice([]string{"bob", "frank", "grace"}) // 3つすべての集合に共通するユーザーを検索 common := users1.Intersection(users2).Intersection(users3) fmt.Println("共通ユーザー:", common.ToSlice()) // [bob]
スライスから重複を除去
func removeDuplicates[T comparable](slice []T) []T { set := hashset.NewFromSlice(slice) return set.ToSlice() } // 使用例 numbers := []int{1, 2, 2, 3, 3, 3, 4, 5} unique := removeDuplicates(numbers) // unique には [1, 2, 3, 4, 5] が含まれます（順序は保証されません）
集合ベースのデータ処理
// ユーザー権限の処理 adminUsers := hashset.NewFromSlice([]string{"alice", "bob"}) activeUsers := hashset.NewFromSlice([]string{"alice", "charlie", "david"}) bannedUsers := hashset.NewFromSlice([]string{"eve", "frank", "charlie"}) // アクティブな管理者ユーザーを検索 activeAdmins := adminUsers.Intersection(activeUsers) // システムにアクセス可能なユーザーを検索（アクティブでかつ禁止されていない） allowedUsers := activeUsers.Difference(bannedUsers) // いずれかのカテゴリに言及されているすべてのユーザーを検索 allUsers := adminUsers.Union(activeUsers).Union(bannedUsers)
参考情報
Goのおすすめ書籍
過去の記事については、以下のページからご参照下さい。
サンプルコードは、以下の場所で公開しています。
