セット (抽象データ型)

セット（集合）とは

セット（set）とは、コンピュータプログラミングにおいて、順序を持たないデータの集まりを表現するための抽象データ型です。数学における集合の概念をモデルにしたもので、セットに格納されるデータは重複が許されないという特徴があります。つまり、同じデータが複数存在することはありません。

重複データの扱い

セットに重複したデータを挿入しようとした場合、その処理方法は実装によって異なります。データの同一性は、与えられた比較関数に基づいて判断されるため、外部の文脈によって同一とみなすかどうかが変化します。例えば、文字列の比較では、大文字と小文字を区別するかしないかで、同一のデータとみなすかどうかが変わります。

重複データの挿入に対する主な処理方法は以下の3つです。

無視する: 既にセットに存在するデータと同じデータは挿入しない。
置き換える: 新しいデータで、既存のデータを置き換える。
多重化する: 同じデータを複数格納する（マルチセットとして扱う）。

狭義のセットでは、重複データは無視されるか、新しいデータで置き換えられるかのいずれかの処理が行われます。もし多重化を実装する場合は、データを削除する際に複数回の操作が必要となります。

実装方法とアクセス速度

セットのアクセス速度は、実装方法によって大きく異なります。一般的には、二分木（TreeSet）やハッシュテーブル（HashSet）などのデータ構造を用いて高速化が図られます。

二分木（TreeSet）: データの順序を維持したまま格納できるため、順序が必要な場合に有効です。探索、挿入、削除の平均計算量はO(log n)となります。
ハッシュテーブル（HashSet）: データの検索速度が速く、挿入、削除の平均計算量はO(1)となります。ただし、データの順序は保証されません。

他の抽象データ型との違い

セットは、他の抽象データ型と比較すると、以下のような違いがあります。

リスト: リストはデータの順序が定義されており、重複したデータを格納できます。
配列: 配列はデータの順序が定義されており、静的配列では格納可能な要素数が固定されています。
マルチセット: マルチセット（bagとも呼ばれる）は、同じデータを複数格納できる点がセットとは異なります。

各プログラミング言語におけるセットの実装例

以下に、主要なプログラミング言語におけるセットの実装例を挙げます。

C++: 標準テンプレートライブラリ（STL）に`std::set`（重複を許さない）と`std::multiset`（重複を許容する）が用意されています。C++11では、`std::unordered_set`と`std::unordered_multiset`も追加されました。
Java: インターフェース`java.util.Set`を実装するクラスとして、`java.util.TreeSet`や`java.util.HashSet`などが提供されています。
.NET Framework: `System.Collections.Generic.ISet`インターフェースを実装するクラスとして、`.NET 4`以降では`System.Collections.Generic.SortedSet`が、`.NET 3.5 SP1`以降では`System.Collections.Generic.HashSet`が利用可能です。
Python: ミュータブルな`set`型と、イミュータブルな`frozenset`型が用意されています。
Ruby: 標準添付の`set`ライブラリに`Set`クラスと、ソートされた順序で取り出される`SortedSet`クラスがあります。

参照

集合
* 素集合データ構造

もう一度検索