- ジェネリックコレクション ページ一覧
HashSetとSortedSet
System.Collections.Generic.HashSetクラスとSystem.Collections.Generic.SortedSetクラスは、数学における集合の概念を表すコレクションクラスです。 HashSetは.NET Framework 3.5 SP1、SortedSetは.NET Framework 4より提供されています。
HashSetクラス・SortedSetクラスを使うことで、一方のコレクションが他方のコレクションと重複する部分を持つか、あるいは完全に異なるか、他方を内包するか、といったコレクション同士の包含関係を調べることができます。 (§.包含関係の検証) また、コレクション同士の和(OR)を求めて二つのコレクションをマージしたり、積(AND)を求めて共通する要素だけを残したりすることができます。 (§.集合演算)
HashSet・SortedSetでは、要素は重複することなく格納されます。 Listなどとは異なり既に追加されている要素を追加しようとしても重複して格納されることなく、常に単一の要素として扱われます。 そのため、HashSet・SortedSetはキーだけを扱う一種のDictionaryのようなコレクションと見ることもできます。 一方、Add/Remove/Clearなど要素を動的に追加・削除するメソッドや、foreachによる列挙などもサポートされているため、その点ではList等の他のコレクションと同様に扱うこともできます。 (§.基本操作)
SortedSetクラスは、名前のとおりHashSetクラスに並べ替えの機能を追加したクラスで、要素を追加したり列挙したりする際には自動的にソートされます。 ほかにも、集合内における最大値・最小値の取得ができるなど、SortedSetでのみ提供される機能も存在します。
.NET Framework 4以降ではHashSet・SortedSetはともにISet<T>インターフェイスを実装しています。 .NET Framework 3.5ではISet<T>は存在せず、そのためHashSetもISet<T>を実装していないので注意してください。 また.NET 5以降では、ISet<T>に対応する読み取り専用インターフェイスIReadOnlySet<T>インターフェイスが新たに導入されるため、HashSet・SortedSetを含むISetを読み取り専用で扱うことができるようになります。
System.Collections名前空間ではHashSetクラス・SortedSetクラスに相当するクラス、集合の概念を表す非ジェネリックなコレクションクラスは提供されていません。
基本操作
HashSetクラス・SortedSetクラスともに、Listなどの他のコレクションクラスと共通するAdd, Remove, Contains, Clearなどのメソッドが用意されています。 IEnumerable<T>インターフェイスを実装しているため、foreach/For Eachステートメントで要素を列挙することもできます。
そのため、重複する値が単一の要素として扱われる以外は、他のコレクションクラスと同様に扱うことができます。 また、SortedSetでは自動的に並べ替えが行われる点を除けば、動作と結果もHashSetと同じです。
列挙操作
HashSet・SortedSetともに、foreach/For Eachステートメントで要素を列挙することができます。 HashSetでは、Listと同様に要素を追加した順に列挙されますが、SortedSetでは値の大小関係に従って小さい順に列挙されます。
Reverseメソッドを使うと、逆順(値の大きい順)で列挙することができます。
重複する要素の追加
HashSet・SortedSetでは同じ値の要素を複数回格納しようとしても重複して格納されることはなく、常に1つだけが格納されます。 この点はDictionaryのキーと似た動作と言えますが、すでに存在する状態で追加しようとしても例外がスローされることはありません。
HashSet・SortedSetともに同じ要素が重複した状態になることはありませんが、HashSetでは格納した時の順序は維持されます(最初に格納された順になります)。
要素取得の試行・実際の値の取得 (TryGetValue)
HashSet・SortedSetに特定の要素が含まれているかどうかを調べるにはContainsメソッドを使うことができます。 このほかに、.NET Standard 2.1/.NET Framework 4.7.2/.NET Core 2.0以降では、TryGetValueメソッドを使うこともできます。
TryGetValueメソッドでは、HashSet・SortedSetに指定した値の要素があるかどうかを調べ、ある場合はその値を取得することができます。
ContainsメソッドとTryGetValueメソッドは、どちらもHashSet・SortedSet内に指定した値の要素があるかどうかを調べるという点では同じです。 一方TryGetValueメソッドは、要素がある場合には実際にHashSet・SortedSet内に格納されている値を取得できる点が異なります。
TryGetValueメソッドは、IEqualtyComparer<T>を指定してHashSetを構築した場合、またはIComparer<T>を指定してSortedSetを構築した場合などにおいて、単に値が含まれているかどうかだけでなく、実際に格納されている値を知りたい場合に有効に機能します。
例えば、大文字小文字の違いを無視するHashSet・SortedSetを構築したときに、HashSet・SortedSetにALICE
という値が含まれているか調べつつ、実際に格納されている値が何なのか(Alice
またはalice
、もしくはそれ以外なのか)を知りたい、といった場合には、ContainsメソッドではなくTryGetValueメソッドを使うことができます。
HashSetにIEqualtyComparer<T>を指定して構築する例については§.HashSetでの等価性比較のカスタマイズ、SortedSetにIComparer<T>を指定して構築する例については§.SortedSetでの大小比較のカスタマイズを参照してください。
集合演算
HashSetクラス・SortedSetクラスには集合演算を行うメソッドとして次のメソッドが用意されています。 いずれも引数としてIEnumerable<T>を取り、戻り値はありません(void)。 したがって、これらのメソッドでは引数に指定された配列やコレクションなどとの演算結果をインスタンス自身に反映します。
メソッド | 動作 |
---|---|
HashSet.IntersectWith
SortedSet.IntersectWith |
現在の集合と引数で指定されたIEnumerable<T>との積集合を求める (引数の集合と共通する要素のみを残す) |
HashSet.UnionWith
SortedSet.UnionWith |
現在の集合と引数で指定されたIEnumerable<T>との和集合を求める (引数の集合の要素をマージする) |
HashSet.ExceptWith
SortedSet.ExceptWith |
現在の集合と引数で指定されたIEnumerable<T>との差集合を求める (引数の集合の要素を除外する) |
HashSet.SymmetricExceptWith
SortedSet.SymmetricExceptWith |
現在の集合と引数で指定されたIEnumerable<T>との対称差を求める (引数の集合と共通する要素のみを除外する) |
以下は、上記の集合演算を使った例です。
SortedSetで並べ替えが行われる以外は、結果は同じです。
以下の図は、上記のHashSet・SortedSetの集合演算メソッドの実行結果を図式化したものです。
LINQの拡張メソッドを使った集合演算
LINQの拡張メソッドを使うことでも、HashSet・SortedSetと同様の集合演算を行うことができます。 それぞれ対応するメソッドは次のとおりです。
演算 | HashSet/SortedSetのメソッド | LINQの拡張メソッド |
---|---|---|
積集合 | IntersectWith | Intersect |
和集合 | UnionWith | Union |
差集合 | ExceptWith | Except |
対象差 | SymmetricExceptWith | - |
以下の例はこれらのメソッドを使ってHashSet・SortedSetと同様の集合演算を行う例です。 LINQでは、SymmetricExceptWithに相当するような対象差を求めるメソッドは直接提供されませんが、以下の例のように差集合同士の和集合を求めることで対象差を求めることができます。
包含関係の検証
HashSetクラス・SortedSetクラスには包含関係の検証を行うメソッドとして次のメソッドが用意されています。 いずれも引数としてIEnumerable<T>を取り、戻り値は真偽値(boolean)です。 なお、要素の並びが異なっていても包含関係には影響しません。 これらのメソッドでは順序にかかわらずどのような要素が含まれているかどうかのみが検証されます。
メソッド | 動作 |
---|---|
HashSet.SetEquals
SortedSet.SetEquals |
現在の集合と引数で指定されたIEnumerable<T>が等しいかどうか調べる (現在の集合と引数の集合がすべて同じ要素で構成されている場合はtrue) |
HashSet.Overlaps
SortedSet.Overlaps |
現在の集合と引数で指定されたIEnumerable<T>が共通する要素を持つかどうか調べる (現在の集合と引数の集合が一つでも同じ要素を持つ場合はtrue) |
HashSet.IsSubsetOf
SortedSet.IsSubsetOf |
現在の集合が引数で指定されたIEnumerable<T>の部分集合かどうか調べる (現在の集合が引数の集合に含まれる場合はtrue) |
HashSet.IsProperSubsetOf
SortedSet.IsProperSubsetOf |
現在の集合が引数で指定されたIEnumerable<T>の真部分集合かどうか調べる (現在の集合が引数の集合に含まれ、かつ両者が等しくない場合はtrue) |
HashSet.IsSupersetOf
SortedSet.IsSupersetOf |
現在の集合が引数で指定されたIEnumerable<T>の上位集合かどうか調べる (現在の集合が引数の集合を含む場合はtrue) |
HashSet.IsProperSupersetOf
SortedSet.IsProperSupersetOf |
現在の集合が引数で指定されたIEnumerable<T>の真上位集合かどうか調べる (現在の集合が引数の集合を含み、かつ両者が等しくない場合はtrue) |
以下は、上記のメソッドを使った例です。 SortedSetでは並べ替えが行われる以外は、結果は同じです。
HashSetでの等価性比較のカスタマイズ
HashSetのコンストラクタで適切なIEqualityComparer<T>インターフェイスを指定することで、要素の等価性比較時の動作をカスタマイズ出来ます。 例えば、比較の際に大文字小文字の違いを無視するようにするといったことが出来ます。 以下は、StringComparerクラスを使って、大文字小文字の違いを無視するHashSetを作成する例です。
IEqualityComparer<T>インターフェイスや実装例については等価性の定義と比較、StringComparerについては文字列と比較オプション・カルチャの並べ替え規則 §.StringComparison列挙型とStringComparerクラスを参照してください。
SortedSetでは等価性比較だけではなく大小関係の比較も行うため、IEqualityComparer<T>インターフェイスではなくIComparer<T>インターフェイスを要求します。
HashSetでKeyValuePairを扱う
等価性比較のカスタマイズ例として、HashSetでKeyValuePairを扱う例をみてみます。 次の例では、KeyValuePairからKeyの値を取得して比較を行うクラスKeyValuePairEqualityComparerを作成し、それをHashSetのコンストラクタに渡しています。 これによりKeyValuePair同士の比較ができるようになり、HashSetでKeyValuePairを扱うことができるようになります。
この例のKeyValuePairEqualityComparerではKeyの値のみを比較しているため、Valueにどのような値が格納されているかといったことは一切考慮されません。 Keyの値が同一であれば、Valueの値に関わらず同一の要素とみなされます。
SortedSetでの大小比較のカスタマイズ
SortedSetのコンストラクタで適切なIComparer<T>インターフェイスを指定することで、要素の大小関係比較時の動作をカスタマイズ出来ます。 例えば、比較の際に大文字小文字の違いを無視するようにするといったことが出来ます。
以下は、大文字小文字を無視し、アルファベット順とは逆順(Z-Aの順)になるようにソートするIComparer<string>を実装し、SortedSetでの並べ替え順をカスタマイズする例です。
IComparer<T>インターフェイスや実装例については大小関係の定義と比較を参照してください。
文字列の大小関係、StringComparerについて詳しくは文字列と比較オプション・カルチャの並べ替え規則を参照してください。
SortedSetのみで提供される操作
以下の操作はHashSetには用意されておらず、SortedSetのみで提供される操作です。
最小値・最大値
SortedSetのコンストラクタでIComparer<T>を明示的に指定しない場合、最小値・最大値はデフォルトのソート順(大小関係)に従って求められます。 一方、コンストラクタでIComparer<T>を指定した場合は、そのIComparer<T>で定義される大小関係に従って最小値・最大値が求められることになります。
つまり、Minプロパティ・Maxプロパティは、IComparer<T>で定義されるソート順でSortedSetをソート(あるいは列挙)したときの、最初または最後の要素を取得するプロパティとなります。 このため、Minプロパティ・Maxプロパティで取得できる値が、常に値としての最小値・最大値になるとは限りません。
デフォルトとは逆順に並べ替えるIComparer<T>を指定してSortedSetを作成し、Minプロパティ・Maxプロパティが返す値の違いを見ると次のようになります。
HashSetでの最小値・最大値の取得
SortedSetと異なり、HashSetからは直接最小値・最大値を取得することはできませんが、LINQの拡張メソッドであるMinメソッドとMaxメソッドを使うことで求めることができます。
LINQのMinメソッド・Maxメソッドでは全要素を走査した上で最大・最小の要素を返します。 このメソッドをSortedSetに対しても用いることはできますが、無駄が多く、SortedListのMinプロパティ・Maxプロパティの代わりとしてMinメソッド・Maxメソッドを用いる利点はありません。
逆順での列挙
Reverseメソッドは、SortedSetを通常とは逆順に列挙する列挙子(IEnumerator<T>)を返します。 つまり、Reverseメソッドを使うと、SortedSet内の要素を逆の順序で列挙することができます。
Reverseメソッドは、Array.ReverseメソッドやList.Reverseメソッドとは異なり、SortedSet内の要素の並びを変更しない、非破壊的なメソッドです。 Reverseメソッドを呼び出してもSortedSet内の要素は逆順にはならず、あくまで逆順で列挙する列挙子を返すだけという点に注意してください。
Reverseメソッドは列挙だけでなく、IEnumerator<T>を引数にとるメソッドやLINQのメソッドに渡して使うこともできます。
部分集合(サブセット)の取得
GetViewBetweenメソッドを使うと、指定した範囲に該当する部分集合をSortedSet<T>として取得出来ます。
部分集合のSortedSetと元のSortedSetに対する変更
GetViewBetweenメソッドは、引数で指定した範囲に該当する部分のビューを返します。 SortedSetの一部をコピーしたものが返されるわけではないため、元になったSortedSetに変更を加えると、GetViewBetweenメソッドで取得したサブセットにも反映されます。
また逆に、GetViewBetweenメソッドで取得したサブセットに変更を加えることもでき、この変更は元になったSortedSetにも反映されます。
SortedSetには、そのSortedSetがGetViewBetweenメソッドによって取得されたビューなのかどうかを判断するプロパティやメソッドは用意されていません。 そのため、GetViewBetweenメソッドによって取得したSortedSetに対して変更を行う際には、影響範囲に注意する必要があります。
.NET 5以降では、IReadOnlySet<T>インターフェイスが新たに導入されるため、GetViewBetweenメソッドで取得したSortedSetをIReadOnlySet<T>にキャストすることにより、読み取り専用のビューとして扱うことができるようになります。
GetViewBetweenメソッドで指定した範囲外の値をサブセットに対して追加しようとした場合、ArgumentOutOfRangeExceptionがスローされます。 GetViewBetweenメソッドで取得したサブセットに対しては、その範囲内に対する変更のみが行えます。
容量
HashSet・SortedSetでは、それ以上要素の追加や削除をする必要がなくなった場合に、TrimExcessメソッドを呼び出すことによって、HashSet・SortedSetが内部的に確保しているバッファを最小化することができ、不要な容量を減らすことができます。
また、HashSet・SortedSetに格納する最大要素数を事前に見積もれる場合は、EnsureCapacityメソッドを呼び出すことによって、あらかじめ指定したサイズのバッファを確保させておくことができます。 これにより、要素の追加に伴うバッファの再割当てとコピーを減らすことができます。 EnsureCapacityメソッドは、.NET Standard 2.1/.NET Core 2.1以降で利用できます。
容量と容量の縮小・確保について詳しくは、Listでの例を参照してください。