集合

Qxw大约 7 分钟

集合

使用 Capacity 属性可以获取和设置集合容量，每次集合的 Size 达到 Capacity 时，集合容量会自动扩容为原来的 2 被倍
创建集合时指点容量能够节省时间

集合和列表实现的接口

接口	说明	方法和属性
IEnumerable`<T>`	可枚举的，可以用 foreach 遍历	GetEnumerator()
ICollection`<T>`	泛型集合类	Count , CopyTo() , Add() , Remove() , Clear()
IList`<T>`	通过位置访问元素列表，派生自 ICollection`<T>`	Insert() , RemoveAt()
ISet`<T>`	提供集的操作派生自 ICollection`<T>`, IEnumerable`<T>`, IEnumerable	ExceptWith() , IntersectWith() , UnionWith() , SymmetricExceptWith() IsProperSubsetOf() , IsProperSupersetOf() , IsSubsetOf() , IsSupersetOf() Overlaps() , SetEquals()
IDictionary<TKey,TValue>	包含键和值的泛型字典派生自 ICollection<KeyValuePair<TKey, TValue>>, IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable	Keys , Values , IsReadOnly , IsFixedSize Add() , Clear() , Contains() , Remove() , GetEnumerator()
ILookup<TKey,TValue>	类似 IDictionary 的键和值，且一个键可以包含多个值派生自 IEnumerable<IGrouping<TKey, TElement>>, IEnumerable	Count ， Contains
IComparer`<T>`	比较器，可以通过 Compare() 方法对元素排序	Compare
IEqualityComparer`<T>`	可用于字典的比较器，可以对对象进行相等性比较	Equals() , GetHashCode()

性能对比

集合	添加：Add、Push、Enqueue	插入：Insert	移除：Remove、pop、Dequeue	Item	Sort	Find
List	如果必须重置大小 O(1) 或 O(n)	O(n)	O(n)	O(1)	O(nlogn) 最坏情况为 O(n^2)	O(n)
Stack	如果必须重置大小 O(1) 或 O(n)	/	O(1)	/	/	/
Queue	如果必须重置大小 O(1) 或 O(n)	/	O(1)	/	/	/
HashSet	如果必须重置大小 O(1) 或 O(n)	Add O(1) 或 O(n)	O(1)	/	/	/
SortedSet	如果必须重置大小 O(1) 或 O(n)	Add O(1) 或 O(n)	O(1)	/	/	/
LinkedList	AddLast O(1)	AddAfter O(1)	O(1)	/	/	/
Dictionary	O(1) 或 O(n)	/	O(1)	O(1)	/	/
SortedDictionary	O(logn)	/	O(logn)	O(logn)	/	/
SortedList	无序数据为 O(n) 如果必须重置大小 O(n) 到列表尾部 O(logn)	/	O(n)	读写 O(logn) 如果键在列表中 O(logn) 如果键不再列表中 O(n)	/	/

列表 List<T>

实现了 IList<T> , ICollection<T> , Ienumerable<T>

创建、初始化

// 创建列表
List<int> list = new List<>();
// 使用初始化器
var list = new List<int>(){1,2,3};

添加、插入、访问、删除元素

// 添加
list.Add(100);
// 添加多个元素
list.AddRange(110,120);
list.AddRange(new int[]{130,140,150});

// 插入
// 如果超出集合元素个数抛出 ArgumentOutOfRangeException 异常
list.Insert(0,123);

// 访问
list[1];
foreach(var itm in list )
    ...;

// 删除
RemoveAt(0);

查找元素

IndexOf();
LastIndexOf();
FindIndex();
FindLastIndexOf();
Find();
FindLast();

Exists();

排序 sort

只有集合中的元素已经实现了 IComparable 接口，才能直接调用不带参数的 Sort() 方法
否则需要传入一个 IComparable 匿名类或者 Lambda 函数
Compare 如果返回值小于0 表示第一个参数小于第二个参数

队列 `Queue\<T>`

FIFO , Firstin-Firstout

实现了 ICollection , IEnumerable\<T> , 没有实现 ICollection<T>

成员	说明
Count	元素个数
Enqueue	在队列一段添加一个元素
Dequeue	在队列头部读取并删除一个元素，如果队列没有元素则抛出异常 InvalidOperationException
Peek	从队列头部读取一个元素，但不删除它
TrimExcess	重新设置队列的容量。Dequeue 取出元素后不会重新设置队列容量，需要使用 TrimExcess 去除头部的空元素

栈 `Stack\<T>`

LIFO , Lastin-Firstout

实现了 ICollection , IEnumerable\<T> , 没有实现 ICollection<T>

成员	说明
Count	元素个数
Push	在栈顶添加一个元素
Pop	在栈顶读取并删除一个元素，如果栈中没有元素则抛出异常 InvalidOperationException
Peek	从栈顶读取一个元素，但不删除它
Contains	确定某个元素是否在栈中

链表 `LinkedList\<T>`

LinkedList 是双向链表，其元素指向它前面和后面一个元素
优点：在链表中插入一个元素非常快，只需要修改其前一个元素的 next 和下一个元素的 previous
缺点：查找元素需要较长时间，需要一个接一个的遍历
LinkedList 中的元素为 LinkedListNode<T> 对象，包含：Next , Previous , Value , List 属性
LinkedList 方法：
- 添加：AddAfter，AddBefore，AddFirst，AddLast
- 删除：Remove，RemoveFirst，RemoveLast
- 查找：Find，FindLast

有序列表 SortedList<TKey,TValue>

有序列表按照键给元素排序
每一个键只允许有一个值

字典 Dictionary<Tkey,TValue>

字典也称为映射或散列表
主要特点是能根据键快速查找值

初始化

var dict = new Dictionary<int, string>()
{
    [1] = "a",
    [100] = "abc"
};
// 键需要放在 [] 中

键的类型

键的数据类型必须重写了 GetHashCode() 方法和 Equeals() 方法或实现 IEquatable 接口。
字典根据 GetHashCode 返回的 int 值计算对应位置的元素索引
字典的容量是一个素数
字段得性能取决于 GetHashCode 的代码
GetHashCode 需要满足：
- 相同对象的哈希值应该相同
- 不同对象可以返回相同的哈希值
- 不能抛出异常
- 应至少使用一个字段
- 散列对象最好在对象的生存期不发生变化
- 应该执行得比较快，开销小
- 散列值应平均分布在 int 可储存得范围
Equeals 方法用于检查相同对象时 GetHashCode 是否相等

Lookup 类

需要使用实现了 IEnumerable 的类的扩展方法 ToLookup 获取 Lookup 类

static void Main(string[] args)
{
    var list = new List<Person>() 
    {
        new Person("zhangsan",18),
        new Person("lisi",20),
        new Person("Tom",18)
    };
    var lookup = list.ToLookup(t => t.age);

    foreach (var tmp in lookup)
    {
        Console.WriteLine("*******{0}******",tmp.Key);
        foreach (var item in tmp)
        {
            Console.WriteLine(item);
        }
    }
    Console.Read();
}

/*
*******18******
name:zhangsan   age:18
name:Tom        age:18
*******20******
name:lisi       age:20
*/

有序字典 `SortedDictionary<Tkey,TValue>`

SortedDictionary 是一个二叉搜索树，其中的元素根据键来排序
键类型必须实现 IComparable\<TKey> 接口，否则需要在构造函数中传入 IComparer\<TKey> 比较器
SortedList 和 SortedDictionary 比较：
- SortedList 的实现是基于数组的列表，SortedDictionay 实现为一个字典
- SortedList 使用的内存比 SortedDictionary 少
- SortedDictinary 的元素插入和删除更快

集 `HashSet\<T> 、SortedSet\<T>`

集中的元素都不重复
实现了 ISet 接口

处理位的集合 BitArray 类、BitVector32 结构

BitArray 可以重新设置大小
BitVector32 结构是基于栈的，速度快，包含32位

BitArray 类

成员	说明
Count / Length	获取数组中的位数 Length 可以定义新的数组大小
Item / Get / Set	可以使用索引器读写数组中的位
SetAll	设置所有的值
Not / And / Or / Xor	取反 / 与 / 或 / 异或

BitVector32 结构

成员	说明
Data	将数据按一个整数返回
Item	获取值
CreateMask	静态方法，为访问特定位创建掩码
CreateSection	静态方法，创建32位中的几个片段

`可观察的集合 ObservableCollection\<T>`

可以获取集合中的元素在何时被添加或删除
SetItem 和 RemoveItem 将触发CollectionChanged 事件

不可变的集合

使用 System.Collection.Immutable 中的集合类

集合类型	说明
ImmutableArrary`<T>`	内部使用了数组类型，实现了IImmutableList`<T>`
ImmutableList`<T>`	内部使用了二叉树来映射对象，实现了IImmutableList`<T>`
ImmutableStack`<T>`	实现了IImmutableStack`<T>`
ImmutableDictionary<TKey,TValue>	无序键值对，实现了IImmutableDictionary<TKey,TValue>
ImmutableSortedDictionary<TKey,TValue>	有序键值对，实现了IImmutableDictionary<TKey,TValue>
ImmutableHashSet`<T>`	不可变无序散列集合，实现了IImmutableSet<TKey,TValue>
ImmutableSortedSet`<T>`	不可变有序散列集合，实现了IImmutableSet<TKey,TValue>

并发集合

如果在多线程使用可以改变的集合，可以用 System.COllections.ConCurrent 中提供的线程安全的集合

线程安全的集合实现了 IProducerConsunerCollection<T> 接口，包括 TryAdd 和 TryTake 方法

集合类型	说明
ConcurrentQueue`<T>`	使用免锁定算法实现
ConcurrentStack`<T>`	在内部使用其元素的链表
ConcurrentBag`<T>`	使用把线程映射到内部使用的数组的概念
ConcurrentDictionary<TKey,TValue>	线程安全的键值集合
BlockingCollection`<T>`	在可以添加或提前元素前会一直阻塞线程