C# Array、List、ArrayList、HashSet、SortedSet

1 Array 数组

1.1 数组定义和初始化的几种方法：

//1.
int[] stuScore = new int[2];
stuScore[0] = 11; 
stuScore[1] = 12;
stuScore[2] = 13;
//2.
int [] stuScore = new int[2]{11,12,13};
//3.
int[] stuScore = new int[]{11,12,13};
//4.
int[] stuScore = {11,12,13};	

1.2 数组常见方法：

Array.Sort(array);//对数组进行排序
Array.Reverse(array);//对数组进行反转
int maxNum = array.Max();//求数组中元素的最大值
int minNum = array.Min();//求数组中元素的最小值
if(array.Contains(20))//判断元素中是否包含40这个元素
foreach(int item in array)//遍历数组

int [] newArray = new int[array.Length];
array.CoptTo(newArray,0);//将array中的所有元素赋值给newArray，0代表从第0个元素开始拷贝
Array.clear(newArray,0,newArray.Length);//从第0个元素开始清除

1.3 数组中的浅拷贝问题

int[] newArray = array;//把数组array赋值给newArray,这是一个浅拷贝的问题，就是把
//栈中指向堆中的地址赋值给新数组，C#中的数组元素存在堆中，newArray和array指
//向的是同一个数组，如果改变了array中的值，newArray中的值也会改变。
//如果想实现真正的拷贝，深拷贝用CopyTo,  
array.CopyTo(newArray,0);
//就是把array中的值拷贝给newArray，实现深拷贝。

1.4 二维数组

//二维数组的定义及初始化
//1.
int[ , ] array = new int[2,3];	 
//2.
int[ , ] array = new int[2,3]{{0,1,2},{3,4,5}};
//3.
int[ , ]array = new int[ , ]{{0,1,2},{3,4,5}};
//4.
int[ , ]array = {{0,1,2},{3,4,5}};
//二维数组中不支持foreach

1.5 交错数组

//交错数组又称锯齿数组，是一种特殊的二维数组，每一行的元素都可以不一样。
//交错组的定义及其初始化
int[][] array = new int[3][];//3行n列
array[0] = new int[4]{1,2,3,4}
array[1] = new int[2]{0,1};
array[2] = new int[6]{1,2,3,4,5,6,};
//二维数组的行数为array.Length
//每一行的长度为array[i].Length

2 ArrayList

ArrayList 是一个特殊数组，它提供了动态的增加和减少元素，实现了 ICollection 和 IList 接口,灵活的设置数组的大小等好处;。
ArrayList 集合相对于数组的优点：支持自动改变大小，可以灵活的插入元素，可以灵活的删除元素，可以灵活的访问元素，但是 ArrayList只支持一维，并且查询和检索的速度比较慢。
在 C# 中数据类型分为两类：值类型和引用类型。int bool char double enum struct DateTime等都是值类型（值类型和引用类型的重要特征在于，值类型的长度固定，而引用类型的长度不固定），string Array class 集合等都是引用类型。如果是值类型直接存储在栈中（局部变量），如果是引用类型，先把数据存储在堆中，然后把堆的地址存储在栈中。
object 类是所有类的基类，所有的数据类型都可以转换成 object 类，这就是为什么 ArrayList 可以存储值类型和引用类型，因为在存储的时候全被转换成 object 类型存储这也是 ArrayList 的一个缺点，就是存储的时候需要把值类型封装成 object 类型，取出来的时候需要再把 object 类型再转换成值类型，这一装箱和拆箱的过程非常消耗性能。
装箱：如果往 ArrayList 中存储值类型的数据，在存储的时候需要转换成 object 类型存储，由值类型封装成 object 类型的过程称为装箱。
拆箱：由 object 类型转换成值类型的过程称为拆箱。

ArrayList arrayLists =new ArrayList();
//增加元素
arrayLists.AddRange();//将ICollection元素添加到ArrayList的末尾
arrayLists.Add();//将对象添加到ArrayList的结尾处
//删除元素
arrayLists.RemoveAt();//移除索引处的元素
arrayLists.Remove();//移除特定对象的第一个匹配项
arrayLists.RemoveRange();//移除一定的范围内的元素
arrayLists.Clear();//从ArrayList中移除所有的元素
//获取元素
arrayLists.Count.ToString();//获取ArrayList中包含的元素数
//插入元素
arrayLists.Insert();//将元素插入ArrayList的指定的索引处
arrayLists.InsertRange();//将集合中的元素插入到ArrayList指定的索引处

3 List

List类是 ArrayList 类的泛型等效类。该类使用大小可按需动态增加的数组实现 IList 泛型接口。

泛型的好处： 它为使用c#语言编写面向对象程序增加了极大的效力和灵活性。不会强行对值类型进行装箱和拆箱，或对引用类型进行向下强制类型转换，所以性能得到提高。

3.1 性能注意事项：

在决定使用IList还是使用ArrayList类（两者具有类似的功能）时，记住IList 类在大多数情况下执行得更好并且是类型安全的。

如果对IList 类的类型 T 使用引用类型，则两个类的行为是完全相同的。但是，如果对类型 T 使用值类型，则需要考虑实现和装箱问题。

添加到 ArrayList 中的任何引用或值类型都将隐式地向上强制转换为 Object。如果项是值类型，则必须在将其添加到列表中时进行装箱操作，在检索时进行取消装箱操作。强制转换以及装箱和取消装箱操作都会降低性能；在必须对大型集合进行循环访问的情况下，装箱和取消装箱的影响非常明显。

3.3 一般用法

//声明
//1.
List<string> mList = new List<string>(); 
//2.以一个集合作为参数创建List
string[] temArr = { “Ha”, “Hunter”, “Tom”, “Lily”, “Jay”, “Jim”, “Kuku”, “Locu” };
List mList = new List(temArr);
//添加一个元素
mList.Add("John");
//添加一组元素
string[] temArr = { “Ha”,“Hunter”, “Tom”, “Lily”, “Jay”, “Jim”, “Kuku”, “Locu” };
mList.AddRange(temArr);
//在index位置添加一个元素
mList.Insert(int index, “Hei”);
//遍历List中元素
foreach (string item in mList) {} 
//删除一个值
mList.Remove("Hunter");
//删除下标为index的元素
mList.RemoveAt(0);
//从下标 3 开始，删除 2 个元素
mList.RemoveRange(3, 2);
//判断某个元素是否在该List中
mList.Contains("Hunter");
//给List里面元素排序
mList.Sort(); 
//给List里面元素顺序反转
mList.Reverse();
//清空
mList.Clear();
//获得List中元素数目
int count = mList.Count();

3.3 List的进阶方法

string[] temArr = { "Ha","Hunter", "Tom", "Lily", "Jay", "Jim", "Kuku", "Locu" };
mList.AddRange(temArr);

//public T Find(Predicate<T> match);
//搜索与指定谓词所定义的条件相匹配的元素，并返回整个 List 中的第一个匹配元素。
//Predicate是对方法的委托，如果传递给它的对象与委托中定义的条件匹配，则该方法返回 true。
//当前 List 的元素被逐个传递给Predicate委托，并在 List 中向前移动，从第一个元素开始，到最后一个元素结束。
//当找到匹配项时处理即停止。
//Predicate 可以委托给一个函数或者一个拉姆达表达式:
//1. 委托给拉姆达表达式：
string listFind = mList.Find(name =>  //name是变量，代表的是mList中元素，自己设定
{                           
	if (name.Length > 3)
	{
		return true;
	}
    return false;
});
Console.WriteLine(listFind);     //输出是Hunter

//2. 委托给一个函数：
string listFind1 = mList.Find(ListFind);  //委托给ListFind函数
Console.WriteLine(listFind);           //输出是Hunter
public bool ListFind(string name)
{
	if (name.Length > 3)
	{
		return true;
	}
		return false;
}

//public T FindLast(Predicate<T> match);
//搜索与指定谓词所定义的条件相匹配的元素，并返回整个 List 中的最后一个匹配元素
//用法与List.Find相同

//public bool TrueForAll(Predicate<T> match);
//确定是否 List 中的每个元素都与指定的谓词所定义的条件相匹配。
//委托给拉姆达表达式：
bool flag = mList.TrueForAll(name =>
{
	if (name.Length > 3)
	{
		return true;
	}
	else
	{
		return false;
	}
});
Console.WriteLine("True for all:  "+flag);  //flag值为false

//public IEnumerable<T> List.Take(int n)：
//获得前n行 返回值为IEnumetable，T的类型与List的类型一样
IEnumerable<string> takeList=  mList.Take(5);
foreach (string s in takeList)
{
	Console.WriteLine("element in takeList: " + s);
}     //这时takeList存放的元素就是mList中的前5个

//public static IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate);
//基于谓词筛选值序列。
IEnumerable<string> whereList = mList.Where(name =>
{
	if (name.Length > 3)
	{
		return true;
	}
	else
	{
		return false;
	}
});
foreach (string s in subList)
{
	Console.WriteLine("element in subList: " + s); //这时subList存储的就是所有长度大于3的元素
}

//public int RemoveAll(Predicate<T> match);
//移除与指定的谓词所定义的条件相匹配的所有元素。
mList.RemoveAll(name =>
	{
	if (name.Length > 3)
	{
		return true;
	}
	else
	{
		return false;
	}
});
foreach (string s in mList)
{
	Console.WriteLine("element in mList: " + s); //这时mList存储的就是移除长度大于3之后的元素。
}

3.4 List和Array之间的相互转换

1. 从System.String[]转到List<System.String>

List<System.String> List = new List<System.String>(); string[] str={“1”,“2”,“3”}; 
List = new List<System.String>(str);

2. 从List<System.String>转到System.String[]

List<System.String> List = new List<System.String>(); 
List.Add(“1”); List.Add(“2”); List.Add(“3”); 
System.String[] str = List.ToArray();

4 HashSet

HashSet 是 System.Collections.Generic 命名空间下的 HashSet 类，是一个高性能且无序的集合。

因为HashSet是无序的，所以它既不能做排序操作，又不能像数组那样索引。在 HashSet 上只能使用foreach来进行迭代，而无法使用for循环。

HashSet中的元素不重复（可以存放单一的null），即具有元素唯一性，若向 HashSet 中插入重复元素，其内部会忽视此次操作，不会报出异常。因此若想拥有一个具有唯一值的集合，HashSet将会是一个具有超高效检索性能的极佳选择（例子：见Leecode刷题第三题）。

HashSet是基于哈希表的原理实现的，学习HashSet首先要了解下哈希表。

哈希表（hash table, 也叫散列表）是根据key直接访问存储位置的数据结构，它通过一个键值的函数，将所需查询的数据映射到表中一个位置来访问，加快了查找速度。

上述函数即为哈希函数，哈希函数应尽量计算简单以提高插入、检索效率；计算得到的地址应尽量分布均匀，以降低哈希冲突；应具有较大的压缩性，以节省内存。常见的哈希函数构造方法有直接定址法、除留余数法、数字分析法等。HashSet采用除留余数法，将元素的HashCode除以某个常数（哈希表Size）的余数作为地址，常数通常选取一个素数。

两个相等的对象的哈希值相同，但两个不等的对象的哈希值是有可能相同的，这就是哈希冲突。处理冲突的方法有开放定址法、链表法、双散列法等。HashSet使用链表法，将冲突元素放在链表中。

哈希表是一种用于高性能集合操作的数据结构，它有如下特点：

• 无序、不重复；
• 插入、查找时间复杂度为O(1)；
• 不使用索引；
• 容量不足时自动扩容，但扩容成本高；
• 可提供很多高性能集合操作，如合并、裁剪等；

HashSet实现

HashSet内置了两个数组，如下。_buckets中存放由哈希函数计算得到的索引值，_buckets中的值从1开始，因此在使用时需要-1。该值即为_entries数组的相对索引，若未发生冲突，指向的值即为待查找元素的相对索引。如果发生了冲突，根据冲突链表也可以快速定位到元素。_entries存放的是Entry对象，Entry类型如下所示。HashCode为元素的哈希值，在查找、插入、删除、扩容等操作时都会用到。Value存储数据。Next在不同时刻有不同的作用，当Entry在列表中时，形成冲突链表，其Next指向冲突链表的下一元素，链表最后一个元素的Next值为-1；若Entry已被列表删除，形成空位链表，其Next指向空位链表的下一元素，空位链表的最后一个元素值为-2。

HashSet还有几个关键成员：_count、_freeList、_freeCount。_count表示添加元素数量，注意它并不是实际存储的元素数量，因为在删除元素时未更新它。_freeList为空位链表头，其值指向被删除的_entries索引，_entries[_freeList].Next指向下一空位的相对位置。_freeCount表示空位数量，列表实际存储的元素数量为_count - _freeCount。

HashSet提供了多个构造函数重载，如果不传任何参数，不会初始化_buckets和_entries。当添元素时，会调用Initialize(0)。Initialize方法接受一个int参数，该参数表示需要初始化的列表容量。实际初始化的列表容量为大于等于该值的最小素数。取素数作为列表长度是因为该值作为使用除留余数法构造的哈希函数的除数，对素数求余结果分布更均匀，减少了冲突的发生。

查找元素时，首先调用元素的GetHashCode方法计算哈希值，然后调用GetBucketRef方法执行哈希函数运算，获得索引。GetBucketRef的返回值-1为真实索引i，若i为-1，则未找到元素。若i>=0，表示列表中存在与待查找元素哈希值相同的元素，但相等的哈希值并不一定表示元素相等，还要进一步判断HashCode，若HashCode相等，再判断元素是否相等，满足则查找到元素，返回_entries的索引i。

插入元素时，首先会查找待插入的元素是否存在，HashSet是不重复的，因此若插入元素已存在会直接返回false。若不存在元素，则会寻找存放元素的index。如果存在删除后的空位，则会将元素放到_freeList指向的空位上；如果不存在空位，则按_entries顺序插入元素。找到index后，即可将元素的HashCode及元素赋值到_entries[index]对应字段，当没有冲突时，Next值为-1；若存在冲突，则形成链表，将其添加到链表头，Next指向冲突的下一位置。

插入时若列表容量不足，会调用Resize方法进行扩容。扩容后的大小为大于等于原大小2倍的最小素数。获取待扩容的大小后，以新大小重新分配entries内存，并调用Array.Copy方法将原内容拷贝到新位置。由于列表长度变了，因此哈希值会变，因此需要更新_buckets的内容(_entries索引)，同理entry.Next的值也要更新。

当删除元素时，首先查找待删除元素是否存在。若哈希值存在冲突，会记录冲突链表的上一索引。查找到元素后，需要更新冲突链表的指针。删除元素后，会更新_freeCount空位数量，并将删除元素索引赋值给_freeList，记录删除空位，添加到空位链表头，其Next指向下一空位的相对位置。插入元素时，会将元素插入到_freeList记录的空位索引处，并根据该空位的Next更新_freeList的值。

总结

通过上文分析可以看出HashSet是个设计巧妙，使用灵活的数据结构。基于哈希表的思想，HashSet的插入、查找速度很快，只需要简单的计算。基于此，HashSet也具备了高性能集合运算的条件，可以高效执行合并、裁剪等运算。但这也导致了HashSet无法存储重复元素。删除时空位链表的设计非常巧妙，但也导致了HashSet无序，也就无法使用索引。因此，当选择数据结构时，如果需要包含重复元素，或者需要有序，则应考虑使用其它数据结构，如List。

另外，Dictionary与HashSet原理相同，只是HashSet只有Key，没有Value。

5 SortedSet

tedSet