C#(.NET)コレクションの使い分けヒント

# 概要

.NETには多数のコレクションが用意されている。

データが少ないうちは全部List&lt;T&gt;でも何とかなるが、データの数が1000個、10000個、100000個、と大きくなるにつれ、使用するコレクションによってパフォーマンスに大きな差が出てくる。

パフォーマンス特性を理解するには内部データ構造や計算量を知るのが一番よいが、まずはざっくり検討できるようヒントを作ってみた。

※内部データ構造や計算量については [C#(.NET)コレクションの使い方と計算量](http://qiita.com/takutoy/items/37e81b916271bf43b527) に書いた。

# Genericコレクションの分類と使い分け

## List：データの順番が重要
|型|適する用途|
|:--|:--|
|[List&lt;T&gt;](https://msdn.microsoft.com/ja-jp/library/6sh2ey19(v=vs.110).aspx)|インデックスによる要素の取得・変更が多い|
|[LinkedList&lt;T&gt;](https://msdn.microsoft.com/ja-jp/library/he2s3bh7(v=vs.110).aspx)|要素の追加、削除が多い|
|[Queue&lt;T&gt;](https://msdn.microsoft.com/ja-jp/library/7977ey2c(v=vs.110).aspx)|FIFO, 待ち行列とか|
|[Stack&lt;T&gt;](https://msdn.microsoft.com/ja-jp/library/3278tedw(v=vs.110).aspx)|LIFO, Undo/Redoの実装とか|

## Dictionaty：高速な索引が必要
|型|適する用途|
|:--|:--|
|[Dictionary&lt;TKey, TValue&gt;](https://msdn.microsoft.com/ja-jp/library/xfhwa508(v=vs.110).aspx)|・メモリ使用量を問わない<br>・参照が多い<BR>・列挙しないか、列挙順序を問わない|
|[SortedDictionary&lt;TKey, TValue&gt;](https://msdn.microsoft.com/ja-jp/library/f7fta44c(v=vs.110).aspx)|・メモリ使用量を抑えたい<br>・要素の追加、削除が多い<br>|
|[SortedList&lt;TKey, TValue&gt;](https://msdn.microsoft.com/ja-jp/library/ms132319(v=vs.110).aspx)|・メモリ使用量をもっと抑えたい<br>・Key/Valueをindexでもアクセスしたい|

## Set：重複の排除や集合演算をしたい
|型|適する用途|
|:--|:--|
|[HashSet&lt;T&gt;](https://msdn.microsoft.com/ja-jp/library/bb359438(v=vs.110).aspx)|メモリ使用量を問わない|
|[SortedSet&lt;T&gt;](https://msdn.microsoft.com/ja-jp/library/dd412070(v=vs.110).aspx)|順序を意識した列挙が多い|



# 参考：.NETの主なコレクション

## [System.Collections.Generic](https://msdn.microsoft.com/ja-jp/library/system.collections.generic(v=vs.110).aspx)：Genericコレクション
通常のプログラムであれば、主にこの名前空間のAPIを使うことになるはず。
- [Dictionary&lt;TKey, TValue&gt;](https://msdn.microsoft.com/ja-jp/library/xfhwa508(v=vs.110).aspx)
- [HashSet&lt;T&gt;](https://msdn.microsoft.com/ja-jp/library/bb359438(v=vs.110).aspx)
- [LinkedList&lt;T&gt;](https://msdn.microsoft.com/ja-jp/library/he2s3bh7(v=vs.110).aspx)
- [List&lt;T&gt;](https://msdn.microsoft.com/ja-jp/library/6sh2ey19(v=vs.110).aspx)
- [Queue&lt;T&gt;](https://msdn.microsoft.com/ja-jp/library/7977ey2c(v=vs.110).aspx)
- [SortedDictionary&lt;TKey, TValue&gt;](https://msdn.microsoft.com/ja-jp/library/f7fta44c(v=vs.110).aspx)
- [SortedList&lt;TKey, TValue&gt;](https://msdn.microsoft.com/ja-jp/library/ms132319(v=vs.110).aspx)
- [SortedSet&lt;T&gt;](https://msdn.microsoft.com/ja-jp/library/dd412070(v=vs.110).aspx)
- [Stack&lt;T&gt;](https://msdn.microsoft.com/ja-jp/library/3278tedw(v=vs.110).aspx)

## [System.Collections.Concurrent](https://msdn.microsoft.com/ja-jp/library/system.collections.concurrent(v=vs.110).aspx)：Concurrentコレクション
マルチスレッドに特化したコレクション。
- [BlockingCollection&lt;T&gt;](https://msdn.microsoft.com/ja-jp/library/dd267312(v=vs.110).aspx)
- [ConcurrentBag&lt;T&gt;](https://msdn.microsoft.com/ja-jp/library/dd381779(v=vs.110).aspx)
- [ConcurrentQueue&lt;T&gt;](https://msdn.microsoft.com/ja-jp/library/dd267265(v=vs.110).aspx)
- [ConcurrentStack&lt;T&gt;](https://msdn.microsoft.com/ja-jp/library/dd267331(v=vs.110).aspx)
- [ConcurrentDictionary&lt;TKey, TValue&gt;](https://msdn.microsoft.com/ja-jp/library/dd287191(v=vs.110).aspx)

<!--
## [System.Collections.Immutable](https://docs.microsoft.com/ja-jp/dotnet/api/system.collections.immutable)：Immutableコレクション
変更できないコレクション。
-->

## [System.Collections.ObjectModel](https://msdn.microsoft.com/ja-jp/library/system.collections.objectmodel(v=vs.110).aspx)：ObjectModelコレクション
特定の用途で使用する。XAMLアプリを作ったことがある人にはおなじみ。
- [ObservableCollection&lt;T&gt;](https://msdn.microsoft.com/ja-jp/library/ms668604(v=vs.110).aspx)
- [ReadOnlyDictionary&lt;TKey, TValue&gt;](https://msdn.microsoft.com/ja-jp/library/gg712875(v=vs.110).aspx)
- [ReadOnlyObservableCollection&lt;T&gt;](https://msdn.microsoft.com/ja-jp/library/ms668620(v=vs.110).aspx)

## [System.Collections.Specialized](https://msdn.microsoft.com/ja-jp/library/system.collections.specialized(v=vs.110).aspx)：Specializedコレクション
こちらも特定の用途でしか使わない。
- [NameValueCollection](https://msdn.microsoft.com/ja-jp/library/system.collections.specialized.namevaluecollection(v=vs.110).aspx)
- 他にもいくつかあるが見たことないのて省略

## [System.Collections](https://msdn.microsoft.com/ja-jp/library/system.collections(v=vs.110).aspx)：レガシーなコレクション
産廃。使うな。
- [BitArray](https://msdn.microsoft.com/ja-jp/library/system.collections.bitarray(v=vs.110).aspx) ※これだけは使うかも
- [ArrayList](https://msdn.microsoft.com/ja-jp/library/system.collections.arraylist(v=vs.110).aspx)
- [Hashtable](https://msdn.microsoft.com/ja-jp/library/system.collections.hashtable(v=vs.110).aspx)
- [Queue](https://msdn.microsoft.com/ja-jp/library/system.collections.queue(v=vs.110).aspx)
- [SortedList](https://msdn.microsoft.com/ja-jp/library/system.collections.sortedlist(v=vs.110).aspx)
- [Stack](https://msdn.microsoft.com/ja-jp/library/system.collections.stack(v=vs.110).aspx)